Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
 
Рейтинг 4.60/5: Рейтинг темы: голосов - 5, средняя оценка - 4.60
andreyananas
22 / 22 / 11
Регистрация: 15.10.2013
Сообщений: 862
Завершенные тесты: 2
#1

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

04.01.2016, 11:43. Просмотров 938. Ответов 25
Метки с++ (Все метки)

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

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

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

Добавлено через 5 часов 23 минуты
ап, все еще актуально
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
04.01.2016, 11:43
Ответы с готовыми решениями:

Написать программу использующую пользовательские классы Stack, Queue, Deque
Добрый день) совсем иссякли идеи,что можно написать,чтобы программа включала в...

Написать парсер/счётчик строк (файловый ввод/вывод)
Ребята проблема такова , код ниже должен высчитывать количество логических...

На основе контейнера stack построить стек с информацией об успешности студентов
На основе контейнера stack построить стек с информацией об успешности студентов...

Есть ли связь между STL-stack и stack - высокопроизводительная память?
Куча источников, как всегда много отсебятины, в общем я запутался...

парсер строки
Народ, помогите, плиз! проблема такая : сперва считываю строку из файла ...

25
Ника))
41 / 41 / 20
Регистрация: 08.12.2010
Сообщений: 340
04.01.2016, 12:00 #2
Может я чего не понимаю, но во тором случае разве нельзя сделать: [{][[[[{}[]]]]]}] ?
0
andreyananas
22 / 22 / 11
Регистрация: 15.10.2013
Сообщений: 862
Завершенные тесты: 2
04.01.2016, 21:42  [ТС] #3
[{][[[[{}[]]]]]}]
видимо из-за этого правильный ответ IMPOSSIBLE

Добавлено через 8 часов 45 минут
ап все еще актуально
0
Mr.X
Эксперт С++
3178 / 1705 / 435
Регистрация: 03.05.2010
Сообщений: 3,867
05.01.2016, 01:09 #4
Лучший ответ Сообщение было отмечено andreyananas как решение

Решение

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
}
2
andreyananas
22 / 22 / 11
Регистрация: 15.10.2013
Сообщений: 862
Завершенные тесты: 2
05.01.2016, 09:23  [ТС] #5
Такой стиль оформления кода где то практикуется? По началу немного сбило с толку=)

Добавлено через 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()];});
0
Mr.X
Эксперт С++
3178 / 1705 / 435
Регистрация: 03.05.2010
Сообщений: 3,867
05.01.2016, 10:12 #6
Цитата Сообщение от andreyananas Посмотреть сообщение
Можете прокомментировать вот эту строку:
C++
1
std::generate(s.begin(), s.end(), [=] { return brackets [rand() % brackets.size()];});
Не, вы реально можете это прочитать в таком виде или прикалываетесь?
Ну, здесь строка просто заполняется случайными скобками.
1
andreyananas
22 / 22 / 11
Регистрация: 15.10.2013
Сообщений: 862
Завершенные тесты: 2
05.01.2016, 10:15  [ТС] #7
Цитата Сообщение от Mr.X Посмотреть сообщение
Не, вы реально можете это прочитать в таком виде или прикалываетесь?
Именно эту строку я ни в каком виде не смог прочитать.
А остальное привел в аналогичный вид и стало легче читать=)
0
Mr.X
Эксперт С++
3178 / 1705 / 435
Регистрация: 03.05.2010
Сообщений: 3,867
05.01.2016, 10:23 #8
Цитата Сообщение от andreyananas Посмотреть сообщение
А остальное привел в аналогичный вид и стало легче читать=)
Так это ж скобки замучаешься считать! И что, если где-то будет лишняя, вы это заметите?
0
andreyananas
22 / 22 / 11
Регистрация: 15.10.2013
Сообщений: 862
Завершенные тесты: 2
05.01.2016, 10:24  [ТС] #9
Цитата Сообщение от Mr.X Посмотреть сообщение
Так это ж скобки замучаешься считать! И что, если где-то будет лишняя, вы это заметите?
Пока с этим проблем не было.
0
Mr.X
Эксперт С++
3178 / 1705 / 435
Регистрация: 03.05.2010
Сообщений: 3,867
05.01.2016, 10:25 #10
Цитата Сообщение от andreyananas Посмотреть сообщение
Пока с этим проблем не было.
Ну, не знаю. Ну тогда, если всю программу в одну строчку написать, вам наверно еще удобнее будет.
0
0x10
2571 / 1751 / 288
Регистрация: 24.11.2012
Сообщений: 4,377
05.01.2016, 10:26 #11
Цитата Сообщение от 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);
1
Somebody
2799 / 1610 / 251
Регистрация: 03.12.2007
Сообщений: 4,213
Завершенные тесты: 3
05.01.2016, 10:32 #12
Цитата Сообщение от Mr.X Посмотреть сообщение
Так это ж скобки замучаешься считать! И что, если где-то будет лишняя, вы это заметите?
Парные скобочки-то в нормальных редакторах подсвечиваются. Пишут же люди на Лиспе как-то.
0
Mr.X
Эксперт С++
3178 / 1705 / 435
Регистрация: 03.05.2010
Сообщений: 3,867
05.01.2016, 10:41 #13
0x10, я все равно не понимаю зачем столько скобок в одной строке кода.
Вас же вроде бы никто к этому не принуждает!

Добавлено через 5 минут
Цитата Сообщение от Somebody Посмотреть сообщение
Парные скобочки-то в нормальных редакторах подсвечиваются. Пишут же люди на Лиспе как-то.
Цитата Сообщение от Mr.X Посмотреть сообщение
Ну, не знаю. Ну тогда, если всю программу в одну строчку написать, вам наверно еще удобнее будет.
Вот возьму и напишу здесь все что думаю!
0
0x10
2571 / 1751 / 288
Регистрация: 24.11.2012
Сообщений: 4,377
05.01.2016, 10:41 #14
Mr.X, лямбду можете оформлять как угодно.
C++
1
2
3
4
// Пример субъективно простого оформления
auto get_random_bracket = [=] {
  return brackets[rand() % brackets.size()];
};
Я делаю акцент на уменьшении сложности (вложенности) в точке вызова за счет введения именованной переменной. Вызов простой функции в этом случае занимает одну строчку, а не двенадцать.
0
Mr.X
Эксперт С++
3178 / 1705 / 435
Регистрация: 03.05.2010
Сообщений: 3,867
05.01.2016, 10:47 #15
Цитата Сообщение от 0x10 Посмотреть сообщение
Я делаю акцент на уменьшении сложности в точке вызова за счет введения именованной переменной.
Ну, при нормальном форматировании у меня вроде код несложный. А если все в одну строчку ссыпать, то конечно.
Именование лямбды - вопрос спорный. Если она один только раз используется, то это только усложняет код, по-моему.
0
0x10
2571 / 1751 / 288
Регистрация: 24.11.2012
Сообщений: 4,377
05.01.2016, 10:57 #16
Mr.X, на правах наброса. Если потребуется в этот код добавить еще один тип обрамляющих символов (< >, \ /, ¿?, ¡!), код придется изменить в пяти (!) местах.

Добавлено через 33 секунды
Цитата Сообщение от Mr.X Посмотреть сообщение
Ну, при нормальном форматировании у меня вроде код несложный. А если все в одну строчку ссыпать, то конечно.
Именование лямбды - вопрос спорный. Если она один только раз используется, то это только усложняет код, по-моему.
Это все субъективно.

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

Не по теме:

Цитата Сообщение от andreyananas Посмотреть сообщение
По началу немного сбило с толку=)
clang-format приводит бо́льшую часть кода к традиционному виду.

2
Mr.X
Эксперт С++
3178 / 1705 / 435
Регистрация: 03.05.2010
Сообщений: 3,867
05.01.2016, 11:39 #17
Цитата Сообщение от 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
}
1
andreyananas
22 / 22 / 11
Регистрация: 15.10.2013
Сообщений: 862
Завершенные тесты: 2
05.01.2016, 11:49  [ТС] #18
Лямбда-выражение это что то новенькое для меня
Я так понимаю это новшество из С++11. Существует книга по С++, в которой описаны все главные новшества С++11?
0
Mr.X
Эксперт С++
3178 / 1705 / 435
Регистрация: 03.05.2010
Сообщений: 3,867
05.01.2016, 11:55 #19
Цитата Сообщение от andreyananas Посмотреть сообщение
Существует книга по С++, в которой описаны все главные новшества С++11?
Ну, в одной книге они уже не умещаются. Вот здесь либо сами новшества, либо ссылки на другие источники.
1
0x10
2571 / 1751 / 288
Регистрация: 24.11.2012
Сообщений: 4,377
05.01.2016, 13:23 #20
Mr.X, все равно сложно.
1. Из-за неудобного способа хранения всех скобок (одна строка) наружу вылезла вся работа с индексами.
2. В основной функции для добавления правой скобки выполняется куча проверок:
— Это левая скобка?
— Это правая скобка?
— А стек пустой?
Все это сводится к одному общему случаю:
— Стек пуст? Добавляем скобку.
— Скобки на вершине стека и очередная на входе — парные? Если да, снимаем скобку со стека, если нет — помещаем текущую на стек.
3. О стиле: try_to_continue_brackets_sequence_on_both_sides — ну просто бесчеловечно длинное название для функции.
0
05.01.2016, 13:23
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
05.01.2016, 13:23

Ошибка: "Unhandled exception: Stack cookie instrumentation code detected a stack-based buffer overrun"
Не могу понять почему значение ChoiceOfPlayer меняется и почему NumberOfRow и...

Написать автомат парсер строки
Условия задачи написать автомат, которы принимает язык L={v | v содержащий...

Простой парсер - как перебрать варианты строки
Всем привет!Опыт программирования на си++ всего месяц-c# около 4 а делфи один...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
20
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru