Проверить, является ли последовательность скобок корректной

@IramKenZo · Регистрация: 02.11.2014

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

Здравствуйте, нашел на просторах интернета такую задачу. Нам даны строки, содержащие скобки 4 видов - круглые (), квадратные [], фигурные {} и угловые <>. Задача в том, чтобы проверить является ли последовательность скобок корректной. Т.е. любая открывающая скобка должна иметь закрывающую того же типа где-то дальше по строке - и кроме того пары скобок не должны пересекаться, хотя они могут быть вложенными:

(a+[b*c] - {d/3}) - здесь квадратные и фигурные скобки вложены в круглые

(a+[b*c) - 17] - а здесь "область действия" круглых и квадратных пересекается, что некорректно

Входные данные указывают количество тестов в первой строке.
Далее идет указанное количество строк, содержащих по одной символьной последовательности.
Ответ должен содержать для каждого теста 1 если скобки расставлены верно или 0 если нет.

Вот моё решение:

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
#include <iostream>
#include <string>
#include <vector>
 
using namespace std;
 
int main(){
    int NumberTestCases; 
    string str1;
    vector<char> str2;
    int length;
    int point;
 
    cin >> NumberTestCases; 
 
    for(int i=0; i<NumberTestCases; i++){
    getline(cin, str1);
    length = str1.length();
    str2.clear();
    for(int i=0; i<length; i++){
        if(str1[i] == '(' || str1[i] == '{' || str1[i] == '[' || str1[i] == '<') str2.push_back(str1[i]);
        else if(str1[i] == ')' || str1[i] == '}' || str1[i] == ']' || str1[i] == '>'){
        point = str2.size();
        if (!point) {cout << '0' << ' '; break;}
        if(str1[i] == ')' && str2[point-1] == '(') str2.pop_back();
        else if(str1[i] == '}' && str2[point-1] == '{') str2.pop_back();
        else if(str1[i] == ']' && str2[point-1] == '[') str2.pop_back();
        else if(str1[i] == '>' && str2[point-1] == '<') str2.pop_back();
        else {cout << '0' << ' '; break;}
        }
    }
    if(str2.empty()) cout << '1' << ' ';
    
    }
    return 0;
}

вот входные данные:
18
<x>{<[^]v>{< >*[d(f)[d](x[a])]}{u}[/]<x([ ]z<(f)z{v}>)>}[z]<+>< >
[g][<<>%(b)]{[ ][(<{y}y>g)<< >/>y]{d}}{+(fa>u)}
(f)[][(-){w((+)c)}d]( )(c) v}<(*)e>< ><(+)*>
[<]<h>(*)[[(z)x]{a}<[c]</>v> u><(+(h)){*}g>]<{ (b)(t)}e>
{}[[e](v{g})(d(%(+))(c)(w))e(z)[(b)h]]{</>x[d]}(<z>b[(/)a])(c)[ ]
< ><>[[c[{/}[g](/) ]<<c>b<t>>][ [u]]{z(*)}e{e}]{-}< >
<>[g]{-}[{/}c](c){f{*}[v{w}]}{^{t[(h)^]}}{f}{x}
[[%] [<[t]w{ }{ }>u]{h}{^(b)([^] )<z>}(a)]<^>[(/)((+)-)]<[(-)c]t>
(a<{(%)d}b>)(<c>x)[(<->({d[c]}/)(a)[a]( )v)<c>](+)
()<</>t><[{v){+[a[+][+]]}[ ( }(/<e{t<h>}>)[-]][z]-](a)[ ]*>{-}
<{%}(x)<<(h{w} c[*<b><y>])(d))u<a</>>{b}>+>< < [d{^}][*]>>>
<{/}f>({b}b{e(d)}{%})(f)(<d((c){y{b}}-)<*>>)(d)
<y>[(c<(z)z(w{/}[ ](^))<w>(t)[<c>{d} ]>)<d>{^}{ }%{f}<g>]()
[(<t>{-} <g>)]{z}<[e]t{x}(b){-}{x}>{[v][a]z}[x[-]{<*>[c]c{b}}]
[/[t]]<t><g><b><>(w[(d){^}y(%)[t]]<{{b}t}[-]{a<v>}t<g>>{+}){u}
<(<<f(y)> <v>(b)>[z(*)]f)[*](b){(v)(a)[{a}a](+)b(u)}><v>
((e){a[/]{w}}(x v)(x)[<c>y](g[{ }[-]c[v]]))(f(^)))<b>
{ <b><y><y>([[g]+]f{c}){<%>{[v]u}h}}()[(<[d]({*}{d}-) >%)a]{[g]e}

Мой ответ:
1 1 0 0 1 0 1 1 1 1 1 0 0 1 1 1 1 1 0 1
Правильный ответ:
1 0 0 0 1 1 1 1 1 0 0 1 1 1 1 1 0 1

Где ошибка? И почему сin >> NumberTestCases; и getline(cin, str1); при первой итерации работают не так как я хочу XD Ну то есть getline "хватает число в начале входных данных"
И почему у меня первое число всегда 1 в ответе? Почему первый проход происходит с пустой строкой? из-за этого у меня числе в ответе больше

@S_Perekrestova · 20.06.2017, 13:53

IramKenZo, у тебя получилось найти решение? Я тоже неделю не могу решить аналогичную задачу.

oldnewyear · 20.06.2017, 15:16

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
#include <stack>
#include <iostream>
#include <algorithm>
 
using namespace std;
 
const string strings[] = {
    "<x>{<[^]v>{< >*[d(f)[d](x[a])]}{u}[/]<x([ ]z<(f)z{v}>)>}[z]<+>< >",
    "[g][<<>%(b)]{[ ][(<{y}y>g)<< >/>y]{d}}{+(fa>u)}",
    "(f)[][(-){w((+)c)}d]( )(c) v}<(*)e>< ><(+)*>",
    "[<]<h>(*)[[(z)x]{a}<[c]</>v> u><(+(h)){*}g>]<{ (b)(t)}e>",
    "{}[[e](v{g})(d(%(+))(c)(w))e(z)[(b)h]]{</>x[d]}(<z>b[(/)a])(c)[ ]",
    "< ><>[[c[{/}[g](/) ]<<c>b<t>>][ [u]]{z(*)}e{e}]{-}< >",
    "<>[g]{-}[{/}c](c){f{*}[v{w}]}{^{t[(h)^]}}{f}{x}",
    "[[%] [<[t]w{ }{ }>u]{h}{^(b)([^] )<z>}(a)]<^>[(/)((+)-)]<[(-)c]t>",
    "(a<{(%)d}b>)(<c>x)[(<->({d[c]}/)(a)[a]( )v)<c>](+)",
    "()<</>t><[{v){+[a[+][+]]}[ ( }(/<e{t<h>}>)[-]][z]-](a)[ ]*>{-}",
    "<{%}(x)<<(h{w} c[*<b><y>])(d))u<a</>>{b}>+>< < [d{^}][*]>>>",
    "<{/}f>({b}b{e(d)}{%})(f)(<d((c){y{b}}-)<*>>)(d)",
    "<y>[(c<(z)z(w{/}[ ](^))<w>(t)[<c>{d} ]>)<d>{^}{ }%{f}<g>]()",
    "[(<t>{-} <g>)]{z}<[e]t{x}(b){-}{x}>{[v][a]z}[x[-]{<*>[c]c{b}}]",
    "[/[t]]<t><g><b><>(w[(d){^}y(%)[t]]<{{b}t}[-]{a<v>}t<g>>{+}){u}",
    "<(<<f(y)> <v>(b)>[z(*)]f)[*](b){(v)(a)[{a}a](+)b(u)}><v>",
    "((e){a[/]{w}}(x v)(x)[<c>y](g[{ }[-]c[v]]))(f(^)))<b>",
    "{ <b><y><y>([[g]+]f{c}){<%>{[v]u}h}}()[(<[d]({*}{d}-) >%)a]{[g]e}"
};
 
 
bool valid (string s) {
    stack <char> stck;
    char br[8] = {'(', '[', '{', '<', ')', ']', '}', '>'};
 
    for(char& c : s) {  // for each character in a string
        char *f = find(begin(br), end(br), c);
        if (f == end(br)) continue;
        if (stck.empty()) {
            if (distance(br, f) > 3) return false;
            else stck.push(c);
        }
        else if (distance(br, f) < 4) stck.push(c);
        else {
            if (stck.top() != br[distance(br, f) - 4]) return false;
            stck.pop();
        }
    }
    return (stck.empty() ? true : false);
}
 
int main() {
    for (int i=0; i<sizeof(strings)/sizeof(strings[0]); i++) {
        cout << valid(strings[i]) << " ";
    }
    cout << endl;
    return 0;
}

@Catstail · 20.06.2017, 15:49

Эту задачу нужно решать так: завести стек для хранения char-ов. Затем читаем строку символ за символом. Встретив "([{<", заносим символ в стек. Встретив ")]}>" выталкиваем символ из стека. Если перед выталкиванием стек пуст - скобки не на балансе. Если открывающая скобка не соотв. закрывающей - то нарушение области действия. Если после просмотра всех символов в стеке что-то осталось, то скобки не на балансе. Остальные символы входной строки (кроме скобок) пропускаем.

@IramKenZo · 20.06.2017, 20:49 **[ТС]**

S_Perekrestova, да, все дело в том, что в потоке остается символ новой строки. Его нужно проигнорировать. Решается так cin >> NumberTestCases; => (cin >> NumberTestCases).get();

@S_Perekrestova · 20.06.2017, 21:35

IramKenZo, А-н, нет, всё равно промахивается местами.

@Fixer_84 · 21.06.2017, 14:24

IramKenZo, написал для вас программу. Надеюсь, подходит:

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
#include <iostream>
#include <string>
 
using namespace std;
 
int Braces(string s, char a, char b)
{
    int k, L;
    L = s.size();
    k = 0;
    for (int i = 0; i < L; i++)
    {
        for (int j = i + 1; j < L; j++)
        {
            if (((s[i] == a) && (s[j] == b) && (i % 2 == 0) && (j % 2 != 0))
                || ((s[i] == a) && (s[j] == b) && (i % 2 != 0) && (j % 2 == 0)))
 
            {
                k++;
                break;
            }
        }
    }
    return k;
}
 
int main()
{
    int N, L;
    string s, str;
    cout << "Введите строку [ENG]:" << endl;
    getline(cin, s);
    for (int i = 0; s[i]; i++)
    {
    if ((s[i] == '(') || 
        (s[i] == ')') ||
        (s[i] == '[') || 
        (s[i] == ']') ||
        (s[i] == '{') || 
        (s[i] == '}') ||
        (s[i] == '<') ||
        (s[i] == '>')) str += s[i]; 
    }
    L = str.size();
    if (!(L % 2))
    {
        N = Braces(str, '(', ')') + 
            Braces(str, '[', ']') + 
            Braces(str, '{', '}') +
            Braces(str, '<', '>');
        if (N == L / 2)
            cout << "Да!" << endl;
        else
            cout << "Нет!" << endl;
    }
    else if (L % 2)
        cout << "Нет!" << endl;
    else if (str == "")
        cout << "Да!" << endl;
    cin.get();
    return 0;
}

@Геомеханик · 21.06.2017, 17:47

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
#include <iostream>
#include <stack>
#include <string>
bool is_beg_end(int a, int b);
bool is_valid(const std::string& s);
 
int main(){
    std::string s = "<x>{<[^]v>{< >*[d(f)[d](x[a])]}{u}[/]<x([ ]z<(f)z{v}>)>}[z]<+>< >";
    if(is_valid(s))
        std::cout << "Yes.";
    else
        std::cout << "Not!";
    std::cin.get();
    return 0;
}
 
bool is_valid(const std::string& s){
    std::stack<char> st;
    for(std::string::const_iterator i = s.begin(); i != s.end(); ++i){
        switch(*i){
        case '(':
        case '{':
        case '[':
        case '<':
            st.push(*i);
            break;
        case ')':
        case '}':
        case ']':
        case '>':
            if(st.empty() || !is_beg_end(st.top(), *i))
                return false;
            st.pop();
            break;
        }
    }
    return st.empty();
}
 
bool is_beg_end(int a, int b){
    return (a == '(' && b == ')') ||
           (a == '{' && b == '}') ||
           (a == '[' && b == ']') ||
           (a == '<' && b == '>');
}

@повар1 · 21.06.2017, 21:26

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
#include<iostream.h>
#include<string>
 
int main()
{
 
  char s[]="<x>{<[^]v>{< >*[d(f)[d](x[a])]}{u}[/]<x([ ]z<(f)z{v}>)>}[z]<+>< >";
  string st="";
  int i=0;
 
  while(s[i]!='\0')
  {
  if(s[i]=='<' || s[i]=='>' ||
     s[i]=='{' || s[i]=='}' ||
     s[i]=='[' || s[i]==']' ||
     s[i]=='(' || s[i]==')')
 
  st +=s[i];
   i++;
   }
   cout<<st<<"\n";
 
     for(;;)
     {
     i=0;
     while(st[i]!='\0')
     {
 
      if(st[i]=='<' && st[i+1]=='>'||
         st[i]=='[' && st[i+1]==']' ||
         st[i]=='(' && st[i+1]==')' ||
         st[i]=='{' && st[i+1]=='}' )
      {
      st.erase(i,2);
      break;
      }
      i++;
      }
     if(st[i]=='\0')
     {
     if(st.size()==0)
       cout<<1;
     else
     cout<<0;
 
     break;
     }
      }
 
    system("pause>NULL");
    return 0;
}

Новые блоги и статьи Все статьи Все блоги /
Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост. Programma_Boinc 28.12.2025 Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост. Налог на собак: https:/ / ********/ gallery/ V06K53e Финансовый отчет в Excel: https:/ / ********/ gallery/ bKBkQFf Пост отсюда. . .	Кто-нибудь знает, где можно бесплатно получить настольный компьютер или ноутбук? США. Programma_Boinc 26.12.2025 Нашел на реддите интересную статью под названием Anyone know where to get a free Desktop or Laptop? Ниже её машинный перевод. После долгих разбирательств я наконец-то вернула себе. . .	Thinkpad X220 Tablet — это лучший бюджетный ноутбук для учёбы, точка. Programma_Boinc 23.12.2025 Рецензия / Мнение/ Перевод Нашел на реддите интересную статью под названием The Thinkpad X220 Tablet is the best budget school laptop period . Ниже её машинный перевод. Thinkpad X220 Tablet —. . .	PhpStorm 2025.3: WSL Terminal всегда стартует в ~ and_y87 14.12.2025 PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .	Как объединить две одинаковые БД Access с разными данными VikBal 11.12.2025 Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.
Новый ноутбук volvo 07.12.2025 Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro	Музыка, написанная Искусственным Интеллектом volvo 04.12.2025 Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .	От async/await к виртуальным потокам в Python IndentationError 23.11.2025 Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .	Поиск "дружественных имён" СОМ портов Argus19 22.11.2025 Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .	Сколько Государство потратило денег на меня, обеспечивая инсулином. Programma_Boinc 20.11.2025 Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .

@S_Perekrestova 0 / 0 / 0 Регистрация: 20.06.2017 Сообщений: 2
	20.06.2017, 13:53
	IramKenZo, у тебя получилось найти решение? Я тоже неделю не могу решить аналогичную задачу. 0

@Catstail Супер-модератор 38161 / 21096 / 4306 Регистрация: 12.02.2012 Сообщений: 34,683 Записей в блоге: 14
	20.06.2017, 15:49
	Эту задачу нужно решать так: завести стек для хранения char-ов. Затем читаем строку символ за символом. Встретив "([{<", заносим символ в стек. Встретив ")]}>" выталкиваем символ из стека. Если перед выталкиванием стек пуст - скобки не на балансе. Если открывающая скобка не соотв. закрывающей - то нарушение области действия. Если после просмотра всех символов в стеке что-то осталось, то скобки не на балансе. Остальные символы входной строки (кроме скобок) пропускаем. 1

@IramKenZo 1 / 1 / 0 Регистрация: 02.11.2014 Сообщений: 57
	20.06.2017, 20:49 [ТС]
	S_Perekrestova, да, все дело в том, что в потоке остается символ новой строки. Его нужно проигнорировать. Решается так cin >> NumberTestCases; => (cin >> NumberTestCases).get(); 1

@S_Perekrestova 0 / 0 / 0 Регистрация: 20.06.2017 Сообщений: 2
	20.06.2017, 21:35
	IramKenZo, А-н, нет, всё равно промахивается местами. 0