Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.89/64: Рейтинг темы: голосов - 64, средняя оценка - 4.89
4 / 4 / 3
Регистрация: 27.11.2016
Сообщений: 59

Стековая реализация проверки правильности скобочной последовательности

20.07.2017, 19:56. Показов 13008. Ответов 14
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
Надо проверить, верна ли скобочная последовательность. Решение с помощью стека. Программа ломается на самом простом тесте(лол) : (). Но я не понимаю, почему так происходит, и как это поправить.
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
#include <iostream>
#include <stack>
#include <stdio.h>
 
 
using namespace std;
int main()
{
    stack<char> br;
    char buf;
    char var;
    buf = getchar();
    while(buf != EOF)
    {
        if(buf == '(' || buf == '[' || buf == '{')
        {
            br.push(buf);
        }
        else
        {
            if(br.empty())
            {
                cout << "no";
                return 0;
            }
            var = br.top();
            if((buf == ')' && var == '(') || (buf == ']' && var == '[') || (buf == '}' && buf == '{')){}
            else
            {
                cout << "no";
                return 0;
            }
            br.pop();
        }
        buf = getchar();
    }
    if(!(br.empty()))
    {
        cout << "no";
        return 0;
    }
    cout << "yes";
    return 0;
}
0
cpp_developer
Эксперт
20123 / 5690 / 1417
Регистрация: 09.04.2010
Сообщений: 22,546
Блог
20.07.2017, 19:56
Ответы с готовыми решениями:

Реализация скобочной записи дерева
#include &lt;iostream&gt; using namespace std; struct node { int info; node *left, *right; }; node *vvod(void); void...

Программа проверки правильности скобок
Написать программу которая определит правильно ли расставлены скобки (,) в выражении . Например (222-(2*Х+5))-3*у). Никак не могу понять((

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

14
 Аватар для anapshy
531 / 272 / 220
Регистрация: 14.11.2016
Сообщений: 1,052
20.07.2017, 20:51
TheJazzMandono, закидываем скобки в стек, а потом берем и сравниванием, совпало - удаляем и проверяем дальше пока один из стеков не пуст. Если скобки не совпали - скобки расставлены не верно. Если один из стеков пуст, а другой полон - скобки не совпали. Если оба стека пустые - скобки расставлены верно (либо отсутствуют)
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
#include <iostream>
#include <stack>
#include <cstdio>
#include <conio.h>
int main()
{
    std::stack<char> left_brakes,
        right_brakes;
    char buf('\0');
    // Пока не встретит символ новой строки (пока пользователь не нажмет ENTER)
    while ((buf = std::getchar()) != '\n')
    {   // Если это скобка, то вставляем в соответствующий стек
        if (buf == '(' || buf == '[' || buf == '{')
            left_brakes.push(buf);
        else if (buf == ')' || buf == ']' || buf == '}')
            right_brakes.push(buf);
    }
    // Пока стеки полные
    while (!left_brakes.empty() && !right_brakes.empty())
    {
        // Получаем скобки
        const char left(left_brakes.top());
        const char right(right_brakes.top());
        // Если левую закрывает права такого же типа...
        if (left == '(' && right == ')' || left == '{' && right == '}' || left == '[' && right == ']')
        { // Удаляем эти скобки и начинаем цикл по новой.
            left_brakes.pop();
            right_brakes.pop();
        }
        else // Если скобки не совпали, то значит уже стоят не верно
            break;  // Покидаем цикл и переходим к условиям ниже
    }
    // Если стек с левыми и правыми скобками пусто - всё верно
    if (left_brakes.empty() && right_brakes.empty())
        std::cout << "Yes" << std::endl;
    else // Если один из них полно - не верно расставлены
        std::cout << "No" << std::endl;
    
    _getch();
    return EXIT_SUCCESS;
}
0
Вездепух
Эксперт CЭксперт С++
 Аватар для TheCalligrapher
12937 / 6804 / 1821
Регистрация: 18.10.2014
Сообщений: 17,217
20.07.2017, 21:15
Цитата Сообщение от TheJazzMandono Посмотреть сообщение
Но я не понимаю, почему так происходит, и как это поправить.
Во-первых, ошибка/опечатка в последней части условия if

C++
1
if((buf == ')' && var == '(') || (buf == ']' && var == '[') || (buf == '}' && buf == '{')){}
смотрите внимательнее.

Во-вторых, результат getchar следует принимать в переменную типа int, а не char. Значение EOF может не помещаться в char.

Во-третьих, с кодом все более-менее нормально, а "не работает" он скорее всего потому, что в зубы ему попадает символ перевода строки '\n', которым вы завершаете ручной ввод. Код к этому не готов.

Либо делайте чтение до '\n' (а не до EOF), либо подготавливайте входные данные так, чтобы в них не было ничего лишнего.

Цитата Сообщение от anapshy Посмотреть сообщение
Если оба стека пустые - скобки расставлены верно (либо отсутствуют)
Какое отношение ваш код имеет к коду ТС? И два стека - неоправданно переусложненная реализация. Зачем?

Более того, ваш алгоритм совершенно не правилен. ([]) распознается как неправильный ввод.
1
4 / 4 / 3
Регистрация: 27.11.2016
Сообщений: 59
20.07.2017, 21:20  [ТС]
Там 60 тестов, проходят 39) А самый простой- нет. в чем ошибка в if?
0
Вездепух
Эксперт CЭксперт С++
 Аватар для TheCalligrapher
12937 / 6804 / 1821
Регистрация: 18.10.2014
Сообщений: 17,217
20.07.2017, 21:33
Цитата Сообщение от TheJazzMandono Посмотреть сообщение
Там 60 тестов, проходят 39
Я не знаю, чем заканчивается ввод в ваших тестах: EOF или '\n'. Отлавливайте оба - и все дела.

Цитата Сообщение от TheJazzMandono Посмотреть сообщение
в чем ошибка в if?
Ну, знаете ли... Опечатки уровня "детский сад" ищите сами. Я вам даже подсказал, в какую часть условия смотреть.

Это вообще ваш код?

Добавлено через 8 минут
Цитата Сообщение от anapshy Посмотреть сообщение
C++
1
2
3
4
5
6
7
while ((buf = std::getchar()) != '\n')
{ // Если это скобка, то вставляем в соответствующий стек
  if (buf == '(' || buf == '[' || buf == '{')
    left_brakes.push(buf);
  else if (buf == ')' || buf == ']' || buf == '}')
    right_brakes.push(buf);
}
Вот такое вот чтение входных данных в два стека - уже полная бессмыслица. После этого уже невозможно отличить правильную последовательность от неправильной. Например входы ([]) и ])([ породят одинаковое содержимое стеков.
0
 Аватар для zarko97
279 / 39 / 13
Регистрация: 11.10.2015
Сообщений: 405
20.07.2017, 21:53
самое адекватное решение
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
#include <iostream>
#include <string>
#include <map>
#include <stack>
 
std::map<char, char> OpenBracketPair = {
    {')', '('},
    {'}', '{'},
    {']', '['}
};
 
inline bool isOpenBracket(char ch) {
    return ch == '(' || ch == '{' || ch == '[';
}
 
inline bool isClosingBracket(char ch) {
    return ch == ')' || ch == '}' || ch == ']';
}
 
bool areParenthesesGood(std::string& str)
{
    std::stack<char> st;
    for (auto ch : str) {
        if (isOpenBracket(ch)) st.push(ch);
        else if (isClosingBracket(ch)) {
            if (!st.empty() && st.top() == OpenBracketPair[ch])
                st.pop();
            else 
                return false;
        }
    }
    return st.empty();
}
 
int main()
{
    std::string s = "{x+(g-[f+h]*c)-(q+w)})";
    (areParenthesesGood(s)) ? std::cout << "yes" : std::cout << "no";
    system("pause");
    return 0;
}
0
Вездепух
Эксперт CЭксперт С++
 Аватар для TheCalligrapher
12937 / 6804 / 1821
Регистрация: 18.10.2014
Сообщений: 17,217
20.07.2017, 22:20
Цитата Сообщение от zarko97 Посмотреть сообщение
самое адекватное решение
С довольно неряшливым отношением к константной корректности.

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

Нет, на "самое адекватное" не потянет.
0
4 / 4 / 3
Регистрация: 27.11.2016
Сообщений: 59
20.07.2017, 22:36  [ТС]
empty true возвращает, если стек не пуст, как я прочел. пробовал я ставить и убирать !)
Знаю, что непрофессионально это.
0
 Аватар для zarko97
279 / 39 / 13
Регистрация: 11.10.2015
Сообщений: 405
20.07.2017, 22:52
Цитата Сообщение от TheCalligrapher Посмотреть сообщение
Манерничанье с оператором ?:
а где вы его усмотрели в моём сорсе?
0
Вездепух
Эксперт CЭксперт С++
 Аватар для TheCalligrapher
12937 / 6804 / 1821
Регистрация: 18.10.2014
Сообщений: 17,217
20.07.2017, 23:22
Цитата Сообщение от zarko97 Посмотреть сообщение
а где вы его усмотрели в моём сорсе?
Вот это

C++
1
(areParenthesesGood(s)) ? std::cout << "yes" : std::cout << "no";
Либо

C++
1
2
3
4
if (areParenthesesGood(s))
  std::cout << "yes" << std::endl;
else
  std::cout << "no" << std::endl;
либо

C++
1
std::cout << (areParenthesesGood(s) ? "yes" : "no") << std::endl;
А вот оригинальный вариант - манерничанье.
1
 Аватар для zarko97
279 / 39 / 13
Регистрация: 11.10.2015
Сообщений: 405
20.07.2017, 23:26
Цитата Сообщение от TheCalligrapher Посмотреть сообщение
перемудреность решения
ну покажите тогда неперемудренное
0
4949 / 2289 / 287
Регистрация: 01.03.2013
Сообщений: 5,991
Записей в блоге: 32
21.07.2017, 03:49
Через стек, говорите? И не перемудренное? Держите
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <iostream>
using namespace std;
 
bool opn(char c) { return c=='(' || c=='[' || c=='{'; }
 
bool isp(char l, char r) {
    return l=='(' && r==')'
        || l=='[' && r==']'
        || l=='{' && r=='}';
}
 
bool f(int i, char a) {
    char b;
    return (!(cin>>b)) ? i==0
        : (opn(b)) ? f(i+1, b) && f(i, a) : isp(a, b);
}
 
int main() { cout << (f(0, ' ') ? "yes" : "no"); }
Code
1
2
3
4
5
6
7
8
ID          227-1521
Участник        Андрей Иванов
Задача            771. Правильная скобочная последовательность
Дата            2017-07-21 03:47:29
Язык            GNU C++ 5.3.1
Статус            OK
Пройдено тестов       15
Баллы          100
3
Вездепух
Эксперт CЭксперт С++
 Аватар для TheCalligrapher
12937 / 6804 / 1821
Регистрация: 18.10.2014
Сообщений: 17,217
21.07.2017, 04:43
Бесстековая (якобы) реализация от Коляна из третьего подъезда

C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <string.h>
#include <stdio.h>
 
int match(char str[])
{
  char *p;
  
  while ((p = strstr(str, "()")) || (p = strstr(str, "[]")) || (p = strstr(str, "{}")))
    memmove(p, p + 2, strlen(p + 2) + 1);
    
  return *str == '\0' || *str == '\n';  
}
 
int main()
{
  char buffer[1024];
  fgets(buffer, sizeof buffer, stdin);
  printf("%s\n", match(buffer) ? "yes" : "no");
}
1
4949 / 2289 / 287
Регистрация: 01.03.2013
Сообщений: 5,991
Записей в блоге: 32
21.07.2017, 05:57
Васян с соседнего дома не мог не ответить
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
using namespace std;
 
string s;
 
bool isp(char l, char r) {
    return l=='(' && r==')'
        || l=='[' && r==']'
        || l=='{' && r=='}';
}
int lv(char c) { return (c=='(' || c=='[' || c=='{') ? -1 : 1; }
 
int mp(char c, int i, int l) {
    return i<0 || l==0 && isp(s[i], c) ? i : mp(c, i-1, l+lv(s[i]));
}
bool f(int b, int e) {
    int c = mp(s[e], e, -1);
    return b>e || c>=b && f(b, c-1) && f(c+1, e-1);
}
 
int main() { cin >> s; cout << (f(0, s.length()-1) ? "yes" : "no"); }
Добавлено через 30 минут

Не по теме:

Эх, Васяну за его кота сказали спасибо, а мне за сиамского стекового и не перемудренного двумя постами выше - нет :)

4
4 / 4 / 3
Регистрация: 27.11.2016
Сообщений: 59
25.07.2017, 16:26  [ТС]
Cпасибо большое, заработало! Благодарю также за разъяснения с getchar()!
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
raxper
Эксперт
30234 / 6612 / 1498
Регистрация: 28.12.2010
Сообщений: 21,154
Блог
25.07.2017, 16:26
Помогаю со студенческими работами здесь

Функция для проверки правильности написания адреса почты
Написать функцию проверки правильности написания адреса почты. Функция возвращает указатель на переданную в неё строку с адресом почты,...

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

Функция проверки правильности написания адреса почты (DevC++)
Написать функцию проверки правильности написания адреса почты. Функция возвращает указатель на переданную в неё строку с адресом почты,...

Реализовать функцию проверки правильности html-тэгов в html-документе
нужно реализовать функцию на с++.Долго сидел,понять не могу.

Проверка правильности последовательности введённых символов
Допустим есть три символа (a, b, c). Я поочерёдно ввожу эти символы в аналогичном порядке(в консоли, через оператор cin например). Нужно...


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

Или воспользуйтесь поиском по форуму:
15
Ответ Создать тему
Новые блоги и статьи
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, то после закрытия окошка. . .
SDL3 для Web (WebAssembly): Работа со звуком через SDL3_mixer
8Observer8 08.02.2026
Содержание блога Пошагово создадим проект для загрузки звукового файла и воспроизведения звука с помощью библиотеки SDL3_mixer. Звук будет воспроизводиться по клику мышки по холсту на Desktop и по. . .
SDL3 для Web (WebAssembly): Основы отладки веб-приложений на SDL3 по USB и Wi-Fi, запущенных в браузере мобильных устройств
8Observer8 07.02.2026
Содержание блога Браузер Chrome имеет средства для отладки мобильных веб-приложений по USB. В этой пошаговой инструкции ограничимся работой с консолью. Вывод в консоль - это часть процесса. . .
SDL3 для Web (WebAssembly): Обработчик клика мыши в браузере ПК и касания экрана в браузере на мобильном устройстве
8Observer8 02.02.2026
Содержание блога Для начала пошагово создадим рабочий пример для подготовки к экспериментам в браузере ПК и в браузере мобильного устройства. Потом напишем обработчик клика мыши и обработчик. . .
Философия технологии
iceja 01.02.2026
На мой взгляд у человека в технических проектах остается роль генерального директора. Все остальное нейронки делают уже лучше человека. Они не могут нести предпринимательские риски, не могут. . .
SDL3 для Web (WebAssembly): Вывод текста со шрифтом TTF с помощью SDL3_ttf
8Observer8 01.02.2026
Содержание блога В этой пошаговой инструкции создадим с нуля веб-приложение, которое выводит текст в окне браузера. Запустим на Android на локальном сервере. Загрузим Release на бесплатный. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru