Парсер/счётчик строки на основе stack/deque

@andreyananas · Регистрация: 15.10.2013

Студворк — интернет-сервис помощи студентам

Дан фрагмент последовательности скобок, состоящей из символов (){}[].
Требуется определить, возможно ли продолжить фрагмент в обе стороны, получив корректную последовательность.
Если возможно - выведите минимальную корректную последовательность, иначе - напечатайте "IMPOSSIBLE".
Максимальная длина строки 10^6 символов.

Sample Input 1:
}[[([{[]}
Sample Output 1:
{}[[([{[]}])]]

Sample Input 2:
{][[[[{}[]
Sample Output 2:
IMPOSSIBLE

Добавлено через 5 часов 23 минуты
ап, все еще актуально

@Ника)) · 04.01.2016, 12:00

Может я чего не понимаю, но во тором случае разве нельзя сделать: [{][[[[{}[]]]]]}] ?

@andreyananas · 04.01.2016, 21:42 **[ТС]**

[{][[[[{}[]]]]]}]

видимо из-за этого правильный ответ IMPOSSIBLE

Добавлено через 8 часов 45 минут
ап все еще актуально

@Mr.X · 05.01.2016, 01:09

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
/*
Дан фрагмент последовательности скобок, состоящей из символов (){}[].
Требуется определить, возможно ли продолжить фрагмент в обе стороны, получив корректную
последовательность.
Если возможно - выведите минимальную корректную последовательность, иначе - напечатайте
"IMPOSSIBLE".
Максимальная длина строки 10^6 символов.
 
Sample Input 1:
}[[([{[]}
Sample Output 1:
{}[[([{[]}])]]
 
Sample Input 2:
{][[[[{}[]
Sample Output 2:
IMPOSSIBLE
*/
///////////////////////////////////////////////////////////////////////////////
#include <algorithm>
#include <cstdlib>
#include <ctime>
#include <iostream>
#include <iterator>
#include <string>
///////////////////////////////////////////////////////////////////////////////
typedef std::string     T_str;
///////////////////////////////////////////////////////////////////////////////
bool    eq_bracket
    (
        char    L,
        char    R
    )
{
    T_str   res_s;
    res_s.push_back(L);
    res_s.push_back(R);
 
    return      res_s     ==  "{}"
            ||  res_s     ==  "[]"
            ||  res_s     ==  "()";
}
///////////////////////////////////////////////////////////////////////////////
bool    is_left_bracket( char   symb )
{
    return      symb    ==  '{'
            ||  symb    ==  '['
            ||  symb    ==  '(';
}
///////////////////////////////////////////////////////////////////////////////
bool    is_right_bracket( char   symb )
{
    return      symb    ==  ')'
            ||  symb    ==  ']'
            ||  symb    ==  '}';
}
///////////////////////////////////////////////////////////////////////////////
char    mirror_bracket( char    symb )
{
    switch( symb )
    {
    case    '('     :   return  ')';
    case    '['     :   return  ']';
    case    '{'     :   return  '}';
 
    case    ')'     :   return  '(';
    case    ']'     :   return  '[';
    case    '}'     :   return  '{';
    default         :   return  0;
    }
}
///////////////////////////////////////////////////////////////////////////////
T_str   mirror_brackets_str( T_str  const   &   s )
{
    T_str   res_s;
 
    std::transform
        (
            s.rbegin            (),
            s.rend              (),
            std::back_inserter  ( res_s ),
            mirror_bracket
        );
 
    return  res_s;
}
///////////////////////////////////////////////////////////////////////////////
void    try_to_continue_brackets_sequence_on_both_sides( T_str  const   &  s )
{
    bool    bool_res    =   true;
    T_str   res_s("IMPOSSIBLE");
    T_str   symb_stack;
    T_str   left_s;
 
    for     (
                auto    symb
                :
                s
            )
    {
        if  (
                is_left_bracket( symb )
            )
        {
            symb_stack.push_back( symb );
        }
        else if     (
                        is_right_bracket( symb )
                    )
        {
            if  (
                    symb_stack.empty()
                )
            {
                left_s.push_back( symb );
            }
            else
            {
                if  (
                        eq_bracket
                            (
                                symb_stack.back(),
                                symb
                            )
                    )
                {
                    symb_stack.pop_back();
                }
                else
                {
                    bool_res    =   false;
                    break;
                }
            }//else
        }
        else
        {
            bool_res    =   false;
            break;
        }
    }//for
 
    if( bool_res )
    {
        res_s   =       mirror_brackets_str( left_s     )
                    +   s
                    +   mirror_brackets_str( symb_stack );
 
        std::cout   <<  T_str   (
                                    left_s.size(),
                                    ' '
                                );
    }
 
    std::cout   <<  s
                <<  std::endl
                <<  res_s
                <<  std::endl;
}
///////////////////////////////////////////////////////////////////////////////
int     main()
{
    srand(unsigned(time(0)));
    T_str   brackets    =   "{}[]()";
 
    for(;;)
    {
        auto    str_len     =   rand() % 10 + 1;
        T_str   s( str_len, 0 );
 
        std::generate
            (
                s.begin     (),
                s.end       (),
 
                [=]
                {
                    return  brackets
                                [
                                    rand() % brackets.size()
                                ];
                }
            );
 
        try_to_continue_brackets_sequence_on_both_sides( s );
        system("pause");
    }//for
}

@andreyananas · 05.01.2016, 09:23 **[ТС]**

Такой стиль оформления кода где то практикуется? По началу немного сбило с толку=)

Добавлено через 11 минут

Сообщение от Mr.X

int main()
{

C++
1
2
3
4
5
6
7
8
9
10
11
12
    srand(unsigned(time(0)));
    T_str brackets = "{}[]()";
 
    for (;;)
    {
        auto    str_len = rand() % 10 + 1;
        T_str   s(str_len, 0);
 
        std::generate(s.begin(), s.end(), [=] { return brackets [rand() % brackets.size()];});
        try_to_continue_brackets_sequence_on_both_sides(s);
        system("pause");
    }//for

}

Можете прокомментировать вот эту строку:

C++
1
        std::generate(s.begin(), s.end(), [=] { return brackets [rand() % brackets.size()];});

@Mr.X · 05.01.2016, 10:12

Сообщение от andreyananas

Можете прокомментировать вот эту строку:

C++
1
std::generate(s.begin(), s.end(), [=] { return brackets [rand() % brackets.size()];});

Не, вы реально можете это прочитать в таком виде или прикалываетесь?
Ну, здесь строка просто заполняется случайными скобками.

@andreyananas · 05.01.2016, 10:15 **[ТС]**

Сообщение от Mr.X

Не, вы реально можете это прочитать в таком виде или прикалываетесь?

Именно эту строку я ни в каком виде не смог прочитать.
А остальное привел в аналогичный вид и стало легче читать=)

@Mr.X · 05.01.2016, 10:23

Сообщение от andreyananas

А остальное привел в аналогичный вид и стало легче читать=)

Так это ж скобки замучаешься считать! И что, если где-то будет лишняя, вы это заметите?

@andreyananas · 05.01.2016, 10:24 **[ТС]**

Сообщение от Mr.X

Так это ж скобки замучаешься считать! И что, если где-то будет лишняя, вы это заметите?

Пока с этим проблем не было.

@Mr.X · 05.01.2016, 10:25

Сообщение от andreyananas

Пока с этим проблем не было.

Ну, не знаю. Ну тогда, если всю программу в одну строчку написать, вам наверно еще удобнее будет.

@0x10 · 05.01.2016, 10:26

Сообщение от Mr.X

Не, вы реально можете это прочитать в таком виде или прикалываетесь?

C++
1
2
3
4
5
6
7
8
9
10
auto get_random_bracket = [=] { return brackets[rand() % brackets.size()]; };
// ...
std::generate(s.begin(), s.end(), get_random_bracket);
 
// или
boost::range::generate(s, get_random_bracket);
 
// или
namespace br = boost::range;
br::generate(s, get_random_bracket);

@Somebody · 05.01.2016, 10:32

Сообщение от Mr.X

Так это ж скобки замучаешься считать! И что, если где-то будет лишняя, вы это заметите?

Парные скобочки-то в нормальных редакторах подсвечиваются. Пишут же люди на Лиспе как-то.

@Mr.X · 05.01.2016, 10:41

0x10, я все равно не понимаю зачем столько скобок в одной строке кода.
Вас же вроде бы никто к этому не принуждает!

Добавлено через 5 минут

Сообщение от Somebody

Парные скобочки-то в нормальных редакторах подсвечиваются. Пишут же люди на Лиспе как-то.

Сообщение от Mr.X

Ну, не знаю. Ну тогда, если всю программу в одну строчку написать, вам наверно еще удобнее будет.

Вот возьму и напишу здесь все что думаю!

@0x10 · 05.01.2016, 10:41

Mr.X, лямбду можете оформлять как угодно.

C++
1
2
3
4
// Пример субъективно простого оформления
auto get_random_bracket = [=] {
  return brackets[rand() % brackets.size()];
};

Я делаю акцент на уменьшении сложности (вложенности) в точке вызова за счет введения именованной переменной. Вызов простой функции в этом случае занимает одну строчку, а не двенадцать.

@Mr.X · 05.01.2016, 10:47

Сообщение от 0x10

Я делаю акцент на уменьшении сложности в точке вызова за счет введения именованной переменной.

Ну, при нормальном форматировании у меня вроде код несложный. А если все в одну строчку ссыпать, то конечно.
Именование лямбды - вопрос спорный. Если она один только раз используется, то это только усложняет код, по-моему.

@0x10 · 05.01.2016, 10:57

Mr.X, на правах наброса. Если потребуется в этот код добавить еще один тип обрамляющих символов (< >, \ /, ¿?, ¡!), код придется изменить в пяти (!) местах.

Добавлено через 33 секунды

Сообщение от Mr.X

Ну, при нормальном форматировании у меня вроде код несложный. А если все в одну строчку ссыпать, то конечно.
Именование лямбды - вопрос спорный. Если она один только раз используется, то это только усложняет код, по-моему.

Это все субъективно.

Добавлено через 5 минут

Не по теме:

Сообщение от andreyananas

По началу немного сбило с толку=)

clang-format приводит бо́льшую часть кода к традиционному виду.

@Mr.X · 05.01.2016, 11:39

Сообщение от 0x10

Mr.X, на правах наброса. Если потребуется в этот код добавить еще один тип обрамляющих символов (< >, \ /, ¿?, ¡!), код придется изменить в пяти (!) местах.

С критикой согласен. Ну тогда так как-то:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
/*
Дан фрагмент последовательности скобок, состоящей из символов (){}[].
Требуется определить, возможно ли продолжить фрагмент в обе стороны, получив корректную
последовательность.
Если возможно - выведите минимальную корректную последовательность, иначе - напечатайте
"IMPOSSIBLE".
Максимальная длина строки 10^6 символов.
 
Sample Input 1:
}[[([{[]}
Sample Output 1:
{}[[([{[]}])]]
 
Sample Input 2:
{][[[[{}[]
Sample Output 2:
IMPOSSIBLE
*/
///////////////////////////////////////////////////////////////////////////////
#include <algorithm>
#include <cstdlib>
#include <ctime>
#include <iostream>
#include <iterator>
#include <string>
///////////////////////////////////////////////////////////////////////////////
typedef std::string     T_str;
///////////////////////////////////////////////////////////////////////////////
T_str   const   BRACKETS_STR    =   "()[]{}";
///////////////////////////////////////////////////////////////////////////////
bool    is_left_bracket( char   symb )
{
    auto    ind     =   BRACKETS_STR.find( symb );
 
    return      ind         !=  T_str::npos
            &&  ind     %   2   ==  0;
}
///////////////////////////////////////////////////////////////////////////////
bool    is_right_bracket( char   symb )
{
    auto    ind     =   BRACKETS_STR.find( symb );
 
    return      ind         !=  T_str::npos
            &&  ind     %   2   ==  1;
}
///////////////////////////////////////////////////////////////////////////////
bool    eq_bracket
    (
        char    L,
        char    R
    )
{
    auto    L_ind   =   BRACKETS_STR.find( L );
    auto    R_ind   =   BRACKETS_STR.find( R );
 
    return      is_left_bracket( L )
            &&  R_ind   ==  L_ind + 1;
}
///////////////////////////////////////////////////////////////////////////////
char    mirror_bracket( char    symb )
{
    auto    ind     =   BRACKETS_STR.find( symb );
 
    is_left_bracket( symb )
        ?   ++ind
        :   --ind;
 
    return  BRACKETS_STR[ ind ];
}
///////////////////////////////////////////////////////////////////////////////
T_str   mirror_brackets_str( T_str  const   &   s )
{
    T_str   res_s;
 
    std::transform
        (
            s.rbegin            (),
            s.rend              (),
            std::back_inserter  ( res_s ),
            mirror_bracket
        );
 
    return  res_s;
}
///////////////////////////////////////////////////////////////////////////////
void    try_to_continue_brackets_sequence_on_both_sides( T_str  const   &  s )
{
    bool    bool_res    =   true;
    T_str   res_s("IMPOSSIBLE");
    T_str   symb_stack;
    T_str   left_s;
 
    for     (
                auto    symb
                :
                s
            )
    {
        if  (
                is_left_bracket( symb )
            )
        {
            symb_stack.push_back( symb );
        }
        else if     (
                        is_right_bracket( symb )
                    )
        {
            if  (
                    symb_stack.empty()
                )
            {
                left_s.push_back( symb );
            }
            else
            {
                if  (
                        eq_bracket
                            (
                                symb_stack.back(),
                                symb
                            )
                    )
                {
                    symb_stack.pop_back();
                }
                else
                {
                    bool_res    =   false;
                    break;
                }
            }//else
        }
        else
        {
            bool_res    =   false;
            break;
        }
    }//for
 
    if( bool_res )
    {
        res_s   =       mirror_brackets_str( left_s     )
                    +   s
                    +   mirror_brackets_str( symb_stack );
 
        std::cout   <<  T_str   (
                                    left_s.size(),
                                    ' '
                                );
    }
 
    std::cout   <<  s
                <<  std::endl
                <<  res_s
                <<  std::endl;
}
///////////////////////////////////////////////////////////////////////////////
int     main()
{
    srand(unsigned(time(0)));
 
    for(;;)
    {
        auto    str_len     =   rand() % 10 + 1;
        T_str   s( str_len, 0 );
 
        std::generate
            (
                s.begin     (),
                s.end       (),
 
                [=]
                {
                    return  BRACKETS_STR
                                [
                                    rand() % BRACKETS_STR.size()
                                ];
                }
            );
 
        try_to_continue_brackets_sequence_on_both_sides( s );
        system("pause");
    }//for
}

@andreyananas · 05.01.2016, 11:49 **[ТС]**

Лямбда-выражение это что то новенькое для меня

Я так понимаю это новшество из С++11. Существует книга по С++, в которой описаны все главные новшества С++11?

@Mr.X · 05.01.2016, 11:55

Сообщение от andreyananas

Существует книга по С++, в которой описаны все главные новшества С++11?

Ну, в одной книге они уже не умещаются. Вот здесь либо сами новшества, либо ссылки на другие источники.

@0x10 · 05.01.2016, 13:23

Mr.X, все равно сложно.
1. Из-за неудобного способа хранения всех скобок (одна строка) наружу вылезла вся работа с индексами.
2. В основной функции для добавления правой скобки выполняется куча проверок:
— Это левая скобка?
— Это правая скобка?
— А стек пустой?
Все это сводится к одному общему случаю:
— Стек пуст? Добавляем скобку.
— Скобки на вершине стека и очередная на входе — парные? Если да, снимаем скобку со стека, если нет — помещаем текущую на стек.
3. О стиле: try_to_continue_brackets_sequence_on_bot h_sides — ну просто бесчеловечно длинное название для функции.

Новые блоги и статьи Все статьи Все блоги /
Символьное дифференцирование igorrr37 13.02.2026 / * Логарифм записывается как: (x-2)log(x^2+2) - означает логарифм (x^2+2) по основанию (x-2). Унарный минус обозначается как ! */ #include <iostream> #include <stack> #include <cctype>. . .	Камера Toupcam IUA500KMA Eddy_Em 12.02.2026 Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .	И ясному Солнцу zbw 12.02.2026 И ясному Солнцу, и светлой Луне. В мире покоя нет и люди не могут жить в тишине. А жить им немного лет.	«Знание-Сила» zbw 12.02.2026 «Знание-Сила» «Время-Деньги» «Деньги -Пуля»
SDL3 для Web (WebAssembly): Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 12.02.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами и вызывать обработчики событий столкновения. . . .	SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 11.02.2026 Содержание блога Библиотека SDL3 содержит встроенные инструменты для базовой работы с изображениями - без использования библиотеки SDL3_image. Пошагово создадим проект для загрузки изображения. . .	SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL3_image 8Observer8 10.02.2026 Содержание блога Библиотека SDL3_image содержит инструменты для расширенной работы с изображениями. Пошагово создадим проект для загрузки изображения формата PNG с альфа-каналом (с прозрачным. . .	Установка Qt-версии Lazarus IDE в Debian Trixie Xfce volvo 10.02.2026 В общем, достали меня глюки IDE Лазаруса, собранной с использованием набора виджетов Gtk2 (конкретно: если набирать текст в редакторе и вызвать подсказку через Ctrl+Space, то после закрытия окошка. . .

@andreyananas 27 / 27 / 11 Регистрация: 15.10.2013 Сообщений: 880

	Парсер/счётчик строки на основе stack/deque 04.01.2016, 11:43. Показов 2378. Ответов 25 Метки нет (Все метки) Дан фрагмент последовательности скобок, состоящей из символов (){}[]. Требуется определить, возможно ли продолжить фрагмент в обе стороны, получив корректную последовательность. Если возможно - выведите минимальную корректную последовательность, иначе - напечатайте "IMPOSSIBLE". Максимальная длина строки 10^6 символов. Sample Input 1: }[[([{[]} Sample Output 1: {}[[([{[]}])]] Sample Input 2: {][[[[{}[] Sample Output 2: IMPOSSIBLE Добавлено через 5 часов 23 минуты ап, все еще актуально 0

@Ника)) 43 / 43 / 20 Регистрация: 08.12.2010 Сообщений: 342
	04.01.2016, 12:00
	Может я чего не понимаю, но во тором случае разве нельзя сделать: [{][[[[{}[]]]]]}] ? 0

@andreyananas 27 / 27 / 11 Регистрация: 15.10.2013 Сообщений: 880
	05.01.2016, 11:49 [ТС]
	Лямбда-выражение это что то новенькое для меня Я так понимаю это новшество из С++11. Существует книга по С++, в которой описаны все главные новшества С++11? 0

@0x10 3258 / 2060 / 351 Регистрация: 24.11.2012 Сообщений: 4,909
	05.01.2016, 13:23
	Mr.X, все равно сложно. 1. Из-за неудобного способа хранения всех скобок (одна строка) наружу вылезла вся работа с индексами. 2. В основной функции для добавления правой скобки выполняется куча проверок: — Это левая скобка? — Это правая скобка? — А стек пустой? Все это сводится к одному общему случаю: — Стек пуст? Добавляем скобку. — Скобки на вершине стека и очередная на входе — парные? Если да, снимаем скобку со стека, если нет — помещаем текущую на стек. 3. О стиле: try_to_continue_brackets_sequence_on_bot h_sides — ну просто бесчеловечно длинное название для функции. 0

Парсер/счётчик строки на основе stack/deque

Решение