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

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

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

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

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

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

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

@Mr.X · 05.01.2016, 14:13

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

— Стек пуст? Добавляем скобку.

Не из нашего случая. Мы правые скобки в пустой стек не добавляем.

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

— Скобки на вершине стека и очередная на входе — парные? Если да, снимаем скобку со стека, если нет — помещаем текущую на стек.

Ну, это вы что-то поспешили. Как раз невалидный случай, когда рядом левая и правая скобки, но не парные.

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

try_to_continue_brackets_sequence_on_bot h_sides — ну просто бесчеловечно длинное название для функции.

Ну, я бесчеловечно длинные предпочитаю бесчеловечно непонятным. Работал с одним товарищем, так тот в ста процентах случаев придумывал такие названия для функций, что понять что она делает можно было только прочитав ее определение.

@0x10 · 05.01.2016, 15:19

Дисклеймер: код ниже приведен исключительно для демонстрации. Может содержать ошибки, проблемы с производительностью и наверняка его можно сделать лучше.

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

Не из нашего случая.

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

Ну, это вы что-то поспешили.

Мы сейчас думаем о разных вариантах решения задачи, отсюда недопонимание. Код приведу ниже.

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

Ну, я бесчеловечно длинные предпочитаю бесчеловечно непонятным. Работал с одним товарищем, так тот в ста процентах случаев придумывал такие названия для функций, что понять что она делает можно было только прочитав ее определение.

У функции помимо названия есть сигнатура, которая также помогает понять ее назначение.
Ваша функция делает слишком много: и вычисления, и ввод-вывод. Я согласился бы даже на название fill, если функция вернет объект, по виду или документации которого будет понятно: что и где им нужно заполнить.

Введем такое определение:

C++
1
2
3
// Первый элемент — дополнение с головы,
// Второй элемент — дополнение с хвоста.
typedef std::pair<std::string, std::string> Complement;

Можно было бы написать свою структуру с более доменно-специфичными полями, чем first и second, но мне было лень.

Для хранения пар скобок будем использовать вектор пар:

C++
1
2
3
4
5
6
7
typedef std::pair<char, char> BracePair;
typedef std::vector<BracePair> BracePairs;
BracePairs bps = {
    {'(', ')'},
    {'{', '}'},
    {'[', ']'}
};

Да, поиск по нему будет линейный. Как было сказано выше, я не стремлюсь сделать самое оптимальное решение: тысячи разных скобок нам не грозят.

Итак, функция fill принимает на вход:
— Входную строку
— Допустимые пары скобок
Возвращает:
— Либо Complement
— Либо ошибку (пусть в виде исключения).

Сигнатура функции получается такой:

C++
1
Complement fill(const std::string& input, const BracePairs& bps)

Не нужно читать тело функции, чтобы понять что она делает. Понятно, что в коде, выполняющем вывод результатов, достаточно вывести конкатенацию строк: complement.first + input + complement.second, чтобы получить валидную последовательность. Это понятно из введенных типов и их документации.

Ок, что будет внутри функции? Выше я уже написал, что она должна делать:

Возвращает:
— Либо Complement
— Либо ошибку (пусть в виде исключения).

Пусть это и делает:

C++
1
2
3
4
5
6
7
8
9
10
Complement fill(const std::string& input, const BracePairs& bps) {
    BraceSequence unparsed_braces = parse(input, bps);
    const Complement complement = build_complement(unparsed_braces, bps);
 
    if (!unparsed_braces.empty()) {
        throw std::runtime_error("Impossible");
    }
 
    return complement;
}

Чтобы понять как функция выполняет свою работу, достаточно перейти к реализации parse и build_complement.

Функция parse, очевидно, парсит входную последовательность. Возвращает оставшиеся непарные скобки. Ради которых нужно делать дополнение. Это тоже понятно уже в точке использования, и не нужно закапываться в реализацию. Но она короткая:

C++
1
2
3
4
5
6
7
8
9
BraceSequence parse(const std::string& input, const BracePairs& bps) {
    BraceSequence seq;
 
    for (const auto& ch : input) {
        feed(seq, ch, bps);
    }
 
    return seq;
}

Как будем «скармливать» скобки? Опять же: функция короткая и выполняет только свою задачу:

C++
1
2
3
4
5
6
7
8
9
10
11
12
void feed(BraceSequence& seq, char ch, const BracePairs& bps) {
    if (seq.empty()) {
        seq.push_back(ch);
        return;
    }
 
    if (match(bps, seq.back(), ch)) {
        seq.pop_back();
    } else {
        seq.push_back(ch);
    }
}

Функция build_complement тоже очень лаконичная. Из чего состоит дополнение? Из скобок, которые нужно добавить слева и скобок, которые нужно добавить справа. Смотрим в реализацию и видим именно это:

C++
1
2
3
4
5
Complement build_complement(BraceSequence& seq, const BracePairs& bps) {
    return Complement(
        build_left_complement(seq, bps),
        build_right_complement(seq, bps));
}

Что я хочу этим сказать. Со сложностью нужно бороться не форматированием с вертикальным выравниванием и не огромными якобы читаемыми именами идентификаторов. Лучше декомпозировать задачу на множество небольших функций с понятным назначением, продумать сигнатуры, ввести доменно-специфичные типы.

Да, сложность субъективна. Но балки комментариев, разбивающих код на блоки, закрывающие теги вида "// for", разнесение широко используемых однострочных операций на десяток строк и прочие меры никак не помогают справиться со сложностью структуры, а только добавляют визуальный шум.

Я не призываю менять свои убеждения. Просто высказал свои мысли, чтобы больше к этому вопросу не возвращаться.

Полный код

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
#include <algorithm>
#include <deque>
#include <iostream>
#include <stdexcept>
#include <vector>
 
typedef std::pair<char, char> BracePair;
typedef std::vector<BracePair> BracePairs;
 
// Первый элемент — дополнение с головы,
// Второй элемент — дополнение с хвоста.
typedef std::pair<std::string, std::string> Complement;
 
typedef std::deque<char> BraceSequence;
 
BracePairs::const_iterator find_by_left(const BracePairs& bps, char left) {
    return std::find_if(
        bps.begin(), bps.end(),
        [left](const BracePair& bp) {
            return bp.first == left;
        });
}
 
BracePairs::const_iterator find_by_right(const BracePairs& bps, char right) {
    return std::find_if(
        bps.begin(), bps.end(),
        [right](const BracePair& bp) {
            return bp.second == right;
        });
}
 
bool match(const BracePairs& bps, char left, char right) {
    const auto it = find_by_left(bps, left);
    return it != bps.end() && it->second == right;
}
 
void feed(BraceSequence& seq, char ch, const BracePairs& bps) {
    if (seq.empty()) {
        seq.push_back(ch);
        return;
    }
 
    if (match(bps, seq.back(), ch)) {
        seq.pop_back();
    } else {
        seq.push_back(ch);
    }
}
 
BraceSequence parse(const std::string& input, const BracePairs& bps) {
    BraceSequence seq;
 
    for (const auto& ch : input) {
        feed(seq, ch, bps);
    }
 
    return seq;
}
 
std::string build_left_complement(BraceSequence& seq, const BracePairs& bps) {
    std::string complement;
 
    while (true) {
        if (seq.empty()) {
            break;
        }
        const auto it = find_by_right(bps, seq.front());
        if (it == bps.end()) {
            break;
        }
        seq.pop_front();
        complement += it->first;
    }
 
    return complement;
}
 
std::string build_right_complement(BraceSequence& seq, const BracePairs& bps) {
    std::string complement;
 
    while (true) {
        if (seq.empty()) {
            break;
        }
        const auto it = find_by_left(bps, seq.back());
        if (it == bps.end()) {
            break;
        }
        seq.pop_back();
        complement += it->second;
    }
 
    return complement;
}
 
Complement build_complement(BraceSequence& seq, const BracePairs& bps) {
    return Complement(
        build_left_complement(seq, bps),
        build_right_complement(seq, bps));
}
 
Complement fill(const std::string& input, const BracePairs& bps) {
    BraceSequence unparsed_braces = parse(input, bps);
    const Complement complement = build_complement(unparsed_braces, bps);
 
    if (!unparsed_braces.empty()) {
        throw std::runtime_error("Impossible");
    }
 
    return complement;
}
 
void run_test(const std::string& input) {
    try {
        BracePairs bps = {
            {'(', ')'},
            {'{', '}'},
            {'[', ']'}
        };
 
        const Complement complement = fill(input, bps);
 
        std::cout << std::string(complement.first.size(), ' ') << input << std::endl;
        std::cout << complement.first << input << complement.second << std::endl;
    } catch (const std::runtime_error& ex) {
        std::cout << input << std::endl;
        std::cout << ex.what() << std::endl;
    }
    std::cout << std::endl;
}
 
int main() {
    const std::vector<std::string> inputs = {
        "}[[([{[]}",
        "{][[[[{}[]"
    };
 
    for (const auto& input : inputs) {
        run_test(input);
    }
}

@Mr.X · 05.01.2016, 21:51

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

Mr.X, все равно сложно.

Ну, моя программа просто детская игрушка по сравнению с вашей. Классический пример усложнения в целях упрощения.

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

1. Из-за неудобного способа хранения всех скобок (одна строка) наружу вылезла вся работа с индексами.

Не знаю, мне кажется, что в плюсах плюсовая строка - самый простой и удобный контейнер, который и задавать и обрабатывать легко. У сишников вон вместо строк вообще сплошная порнография, а вовсю пользуются, сердешные.
Я еще думал что же вы взамен предложите. Ваш вариант показался мне сложным и непрактичным.
Ну и названия функций. У вас они, как у дипломатов, предназначены, чтобы скрывать ваши мысли.
Ну и программа работает с ошибками. Вот несколько примеров неправильно обрабатываемых строк:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int main()
{
    const std::vector<std::string> inputs
        =   {
                "}]{{{{",
                "])){[",
                "}]{",
                "})]",
                "])){[[]",
                "]}}("
            };
 
    for (
            const   auto    &   input
            :
            inputs
         )
    {
        run_test( input );
    }
}

Добавлено через 7 минут
Ну, я уж не говорю про форматирование. Никогда ни понимал в чем прикол кернигановской несимметричной расстановки скобок. Если бы начальником был я, то давал бы за это не меньше пяти лет расстрела.

@0x10 · 05.01.2016, 23:24

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

Ну и программа работает с ошибками.

Замечание принимается. Все примеры демонстрируют единственную ошибку: символы слева добавляются в обратном порядке. В качестве быстрого исправления добавил reverse.

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

Если подходить к вопросу формально, то все определяется проектом и компанией. В конкретной компании, в конкретном проекте есть соглашения о кодировании, которые нужно соблюдать. Плюс, может быть принята процедура ревью кода. Все это направлено на то, чтобы код выглядел единообразно и был понятен другим людям. Здесь, в теме на форуме, нет проектных требований, поэтому писать можно как угодно.

Код с исправлением ошибки и симметричными скобочками

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
#include <algorithm>
#include <deque>
#include <iostream>
#include <stdexcept>
#include <vector>
 
typedef std::pair<char, char> BracePair;
typedef std::vector<BracePair> BracePairs;
 
// Первый элемент — дополнение с головы,
// Второй элемент — дополнение с хвоста.
typedef std::pair<std::string, std::string> Complement;
 
typedef std::deque<char> BraceSequence;
 
BracePairs::const_iterator find_by_left(const BracePairs& bps, char left)
{
    return std::find_if(
        bps.begin(), bps.end(),
        [left](const BracePair& bp) {
            return bp.first == left;
        });
}
 
BracePairs::const_iterator find_by_right(const BracePairs& bps, char right)
{
    return std::find_if(
        bps.begin(), bps.end(),
        [right](const BracePair& bp) {
            return bp.second == right;
        });
}
 
bool match(const BracePairs& bps, char left, char right)
{
    const auto it = find_by_left(bps, left);
    return it != bps.end() && it->second == right;
}
 
void feed(BraceSequence& seq, char ch, const BracePairs& bps)
{
    if (seq.empty())
    {
        seq.push_back(ch);
        return;
    }
 
    if (match(bps, seq.back(), ch))
    {
        seq.pop_back();
    }
    else
    {
        seq.push_back(ch);
    }
}
 
BraceSequence parse(const std::string& input, const BracePairs& bps)
{
    BraceSequence seq;
 
    for (const auto& ch : input)
    {
        feed(seq, ch, bps);
    }
 
    return seq;
}
 
std::string build_left_complement(BraceSequence& seq, const BracePairs& bps)
{
    std::string complement;
 
    while (true)
    {
        if (seq.empty())
        {
            break;
        }
        const auto it = find_by_right(bps, seq.front());
        if (it == bps.end())
        {
            break;
        }
        seq.pop_front();
        complement += it->first;
    }
 
    std::reverse(complement.begin(), complement.end());
 
    return complement;
}
 
std::string build_right_complement(BraceSequence& seq, const BracePairs& bps)
{
    std::string complement;
 
    while (true)
    {
        if (seq.empty())
        {
            break;
        }
        const auto it = find_by_left(bps, seq.back());
        if (it == bps.end())
        {
            break;
        }
        seq.pop_back();
        complement += it->second;
    }
 
    return complement;
}
 
Complement build_complement(BraceSequence& seq, const BracePairs& bps)
{
    return Complement(
        build_left_complement(seq, bps),
        build_right_complement(seq, bps));
}
 
Complement fill(const std::string& input, const BracePairs& bps)
{
    BraceSequence unparsed_braces = parse(input, bps);
    const Complement complement = build_complement(unparsed_braces, bps);
 
    if (!unparsed_braces.empty())
    {
        throw std::runtime_error("Impossible");
    }
 
    return complement;
}
 
void run_test(const std::string& input)
{
    try
    {
        BracePairs bps = {
            {'(', ')'},
            {'{', '}'},
            {'[', ']'}
        };
 
        const Complement complement = fill(input, bps);
 
        std::cout << std::string(complement.first.size(), ' ') << input << std::endl;
 
        std::cout << complement.first << input << complement.second << std::endl;
    }
    catch (const std::runtime_error& ex)
    {
        std::cout << input << std::endl;
        std::cout << ex.what() << std::endl;
    }
    std::cout << std::endl;
}
 
int main()
{
    const std::vector<std::string> inputs = {
        "}[[([{[]}",
        "{][[[[{}[]",
        "}]{{{{"
    };
 
    for (const auto& input : inputs)
    {
        run_test(input);
    }
}

@Mr.X · 06.01.2016, 19:08

0x10, прочитал вашу программу и понял, что мою вы таки не дочитали и в алгоритм мой не въехали, иначе бы не сочинили сами такой неэффективный. Моя программа как только встречает невалидное сочетание соседних скобок, так заканчивает работу. А ваша даже невалидную строку парсит до конца (а строка по условию может содержать до миллиона символов), а потом еще пытается к ней голову и хвост пришпандорить.
Ежели продолжить соревнование упрощенцев, то еще такой вариант пришел на ум, с классами:

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
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
/*
Дан фрагмент последовательности скобок, состоящей из символов (){}[].
Требуется определить, возможно ли продолжить фрагмент в обе стороны, получив корректную
последовательность.
Если возможно - выведите минимальную корректную последовательность, иначе - напечатайте
"IMPOSSIBLE".
Максимальная длина строки 10^6 символов.
 
Sample Input 1:
}[[([{[]}
Sample Output 1:
{}[[([{[]}])]]
 
Sample Input 2:
{][[[[{}[]
Sample Output 2:
IMPOSSIBLE
*/
///////////////////////////////////////////////////////////////////////////////
#include <algorithm>
#include <ctime>
#include <functional>
#include <iostream>
#include <iterator>
#include <map>
#include <random>
#include <set>
#include <string>
///////////////////////////////////////////////////////////////////////////////
typedef std::string                             T_str;
typedef std::set        < char  >               T_symb_set;
typedef std::map        < char,     char    >   T_match_bracket_of;
///////////////////////////////////////////////////////////////////////////////
class   T_bracket_parser
{
    //-------------------------------------------------------------------------
    T_symb_set          left_brackets_;
    T_match_bracket_of  mirror_bracket_of;
    //-------------------------------------------------------------------------
public:
    //-------------------------------------------------------------------------
    void    add_brackets( T_str   const   &   brackets )
    {
        for (
                auto
                L_it    =   brackets.begin  ();
                L_it    !=  brackets.end    ();
                ++++L_it
            )
        {
            auto    R_it    =   L_it + 1;
            left_brackets_.insert( *L_it );
            mirror_bracket_of[ *L_it    ]   =   *R_it;
            mirror_bracket_of[ *R_it    ]   =   *L_it;
        }//for
    }
    //-------------------------------------------------------------------------
    void    clear()
    {
        left_brackets_      .clear();
        mirror_bracket_of   .clear();
    }
    //-------------------------------------------------------------------------
    bool    successfully_set_correct_head_and_tail
        (
            T_str   const   &   brackets,
            T_str           &   head,
            T_str           &   tail
        )                                                               const
    {
        bool    bool_res    =   true;
 
        for     (
                    auto    symb
                    :
                    brackets
                )
        {
            if  (
                    is_left_bracket( symb )
                )
            {
                tail.push_back( symb );
            }
            else
            {
                if  (
                        tail.empty()
                    )
                {
                    head.push_back( symb );
                }
                else
                {
                    if  (
                            are_matching_brackets
                                (
                                    tail.back(),
                                    symb
                                )
                        )
                    {
                        tail.pop_back();
                    }
                    else
                    {
                        bool_res    =   false;
                        break;
                    }
                }//else
            }//else
        }//for
 
        if( bool_res )
        {
            reflect_mirror( head );
            reflect_mirror( tail );
        }
 
        return  bool_res;
    }
    //-------------------------------------------------------------------------
    T_str   get_rand_brackets_sequens_with_len_in_segment
        (
            int     len_min,
            int     len_max
        )                                                               const
    {
        static  std::default_random_engine      gen(unsigned(time(0)));
 
        std::uniform_int_distribution< int >    distr_len   (
                                                                len_min,
                                                                len_max
                                                            );
 
        auto    str_len     =   distr_len( gen );
        T_str   s_res( str_len, 0 );
 
        std::uniform_int_distribution< size_t >     distr_ind   (
                                                                    0,
                                                                    mirror_bracket_of.size() - 1
                                                                );
 
        std::generate
            (
                s_res.begin     (),
                s_res.end       (),
 
                [&]
                {
                    auto    ind     =   distr_ind( gen );
                    return  bracket_of_ind( ind );
                }
            );
 
        return  s_res;
    }
    //-------------------------------------------------------------------------
private:
    //-------------------------------------------------------------------------
    char    bracket_of_ind( size_t  ind )
    {
        auto    it      =   mirror_bracket_of.begin();
 
        std::advance
            (
                it,
                ind
            );
 
        return  it->first;
    }
    //-------------------------------------------------------------------------
    bool    is_left_bracket( char   symb )                              const
    {
        return  left_brackets_.count( symb )    !=  0;
    }
    //-------------------------------------------------------------------------
    bool    are_matching_brackets
        (
            char    L,
            char    R
        )                                                               const
    {
        return      is_left_bracket ( L )
                &&  mirror_bracket  ( L )   ==  R;
    }
    //-------------------------------------------------------------------------
    void    reflect_mirror( T_str  &   s )                              const
    {
        T_str   res_s;
 
        std::transform
            (
                s.rbegin                (),
                s.rend                  (),
                std::back_inserter      ( res_s ),
 
                [&]                     ( auto  symb )
                {
                    return  this->mirror_bracket( symb );
                }
            );
 
        s   =   res_s;
    }
    //-------------------------------------------------------------------------
    char    mirror_bracket( char    symb )                              const
    {
        return  mirror_bracket_of.at( symb );
    }
    //-------------------------------------------------------------------------
};
///////////////////////////////////////////////////////////////////////////////
int     main()
{
    T_bracket_parser            bracket_parser;
    bracket_parser.add_brackets("()[]{}");
 
    for(;;)
    {
        auto    brackets
                =   bracket_parser.get_rand_brackets_sequens_with_len_in_segment( 1, 10 );
 
        T_str   head;
        T_str   tail;
        T_str   res_s   =   "IMPOSSIBLE";
 
        if  (
                bracket_parser.successfully_set_correct_head_and_tail
                    (
                        brackets,
                        head,
                        tail
                    )
            )
        {
            res_s   =       head
                        +   brackets
                        +   tail;
 
            std::cout   <<  T_str   (
                                        head.size(),
                                        ' '
                                    );
        }
 
        std::cout   <<  brackets
                    <<  std::endl
                    <<  res_s
                    <<  std::endl;
 
        system("pause");
    }//for
}

@0x10 · 06.01.2016, 21:14

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

Моя программа как только встречает невалидное сочетание соседних скобок, так заканчивает работу. А ваша даже невалидную строку парсит до конца

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

Добавлено через 1 минуту
Раз уж на то пошло, то в моем случае не нужно переписывать весь код, чтобы прекратить разбор строки при нахождении невалидной пары. Переносим исключение из функции parse в функцию match, кидаем как только встречаем невалидную пару. Все остальные базовые функции остались без изменений.

Если остались ошибки — можно тестировать, искать, исправлять.

Кликните здесь для просмотра всего текста

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
#include <algorithm>
#include <deque>
#include <iostream>
#include <stdexcept>
#include <vector>
 
typedef std::pair<char, char> BracePair;
typedef std::vector<BracePair> BracePairs;
 
// Первый элемент — дополнение с головы,
// Второй элемент — дополнение с хвоста.
typedef std::pair<std::string, std::string> Complement;
 
typedef std::deque<char> BraceSequence;
 
BracePairs::const_iterator find_by_left(const BracePairs& bps, char left) {
    return std::find_if(
        bps.begin(), bps.end(),
        [left](const BracePair& bp) {
            return bp.first == left;
        });
}
 
BracePairs::const_iterator find_by_right(const BracePairs& bps, char right) {
    return std::find_if(
        bps.begin(), bps.end(),
        [right](const BracePair& bp) {
            return bp.second == right;
        });
}
 
bool match(const BracePairs& bps, char left, char right) {
    const auto it_left = find_by_left(bps, left);
    const auto it_right = find_by_right(bps, right);
 
    const bool res = it_left != bps.end() && it_left->second == right;
 
    if (!res && it_left != bps.end() && it_right != bps.end()) {
        throw std::runtime_error("Impossible");
    }
 
    return res;
}
 
void feed(BraceSequence& seq, char ch, const BracePairs& bps) {
    if (seq.empty()) {
        seq.push_back(ch);
        return;
    }
 
    if (match(bps, seq.back(), ch)) {
        seq.pop_back();
    } else {
        seq.push_back(ch);
    }
}
 
BraceSequence parse(const std::string& input, const BracePairs& bps) {
    BraceSequence seq;
 
    for (const auto& ch : input) {
        feed(seq, ch, bps);
    }
 
    return seq;
}
 
std::string build_left_complement(BraceSequence& seq, const BracePairs& bps) {
    std::string complement;
 
    while (true) {
        if (seq.empty()) {
            break;
        }
        const auto it = find_by_right(bps, seq.front());
        if (it == bps.end()) {
            break;
        }
        seq.pop_front();
        complement += it->first;
    }
 
    std::reverse(complement.begin(), complement.end());
 
    return complement;
}
 
std::string build_right_complement(BraceSequence& seq, const BracePairs& bps) {
    std::string complement;
 
    while (true) {
        if (seq.empty()) {
            break;
        }
        const auto it = find_by_left(bps, seq.back());
        if (it == bps.end()) {
            break;
        }
        seq.pop_back();
        complement += it->second;
    }
 
    return complement;
}
 
Complement build_complement(BraceSequence& seq, const BracePairs& bps) {
    return Complement(
        build_left_complement(seq, bps),
        build_right_complement(seq, bps));
}
 
Complement fill(const std::string& input, const BracePairs& bps) {
    BraceSequence unparsed_braces = parse(input, bps);
    const Complement complement = build_complement(unparsed_braces, bps);
 
    return complement;
}
 
void run_test(const std::string& input) {
    try {
        BracePairs bps = {
            {'(', ')'},
            {'{', '}'},
            {'[', ']'}
        };
 
        const Complement complement = fill(input, bps);
 
        std::cout << std::string(complement.first.size(), ' ') << input
            << std::endl;
 
        std::cout << complement.first << input << complement.second
            << std::endl;
    } catch (const std::runtime_error& ex) {
        std::cout << input << std::endl;
        std::cout << ex.what() << std::endl;
    }
    std::cout << std::endl;
}
 
int main() {
    const std::vector<std::string> inputs = {
        "}[[([{[]}",
        "{][[[[{}[]",
        "}]{{{{"
    };
 
    for (const auto& input : inputs) {
        run_test(input);
    }
}

Новые блоги и статьи Все статьи Все блоги /
Nekobox - outbounds[0].transport: unknown transport type: raw damix 01.10.2026 Фикс ошибки Правым кликом по серверу -> отладочная информация -> edit Заменить "net": "raw", на "net": "tcp", Нажать кнопку reload.	Программный домашний кинотеатр russiannick 27.09.2026 Сподобился на программный домашний кинотеатр. В качестве ЯВУ по традиции выбрал js. В помощники взял Яндекс-Алису. Было создано три зала на разные интересы. исторические и ретро сериал Хичкок. . .	Беседа с ИИ о программистах, недопускающих к созданию и правке кода генеративные ИИ и причины этого zorxor 21.09.2026 Раньше я радовался или получал некоторые эмоции, пусть небольшие, но всё же, от самого процесса написания кода, рекомпиляции и запуска, видя постепенное развитие программы и прочее. А теперь лень. . .	Мобильное приложение ColorStep pavlinmavlin 17.09.2026 Реализовал приложение Красный, Зеленый, Синий в Unity3d + c#. Название изменил на ColorStep. Приложение прошло модерацию и теперь доступно для скачивания. Делал его сам, шаг за шагом — и вот,. . .
Запрет дублирования строк в табличной части Maks 13.09.2026 Реализация из решения ниже выполнена на нетиповом справочнике "Нормы ТО" с табличной часть "Виды ТО", разработанного в КА2, со следующими реквизитами: - ВидТО (СправочникСсылка. ВидыТО); - ВидГСМ. . .	Скрипты Tampermonkey для CyberForum, ChatGPT, Claude и пр. Jin X 06.09.2026 Скрипты Tampermonkey для CyberForum, ChatGPT, Claude и пр. Работая с форумом и нейросетями в браузере часто хочется что-то подкорректировать или добавить какого-то функционала. Ниже прикреплён. . .	Программа опроса у.з. расходомера SLS-720F Argus19 02.09.2026 Программа опроса у. з. расходомера SLS-720F Программа опрашивает один раз в минуту три ультразвуковых расходомера SLS-720F через интерфейс RS-485 по протоколу Modbus RTU. Опрашиваются регистры. . .	Hyper-V: Компьютер должен поддерживать доверенный платформенный модуль 2.0. Maks 31.08.2026 При установке Windows 11 на виртуальную машину Hyper-V 2-го поколения вылезла такая ошибка: Решение: в параметрах виртуальной машины, в разделе "Безопасность" (Security) активировать флаг. . .

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

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

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

Решение