Форум программистов, компьютерный форум CyberForum.ru

Проверка на расстановку скобок - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 23, средняя оценка - 4.96
saserlend
10 / 10 / 1
Регистрация: 25.11.2011
Сообщений: 139
09.09.2013, 15:06     Проверка на расстановку скобок #1
В общем задание такое.
Программа (консольная) проверяет каждую строку файла для проверки на расстановку скобок 4 типов ("(" и ")", "[" и "]", "{" и "}", "<" и ">"), проверка должна учесть парность и вложенность расстановки скобок (как в математических выражениях), другие символы - пропускать без обработки.
По результатам проверки формируется файл результатов, каждая строка которого соответствует строке файла для проверки, результат в строке может быть описан как - "нет ошибок", "ошибка в символе N" (N - порядковый номер символа в строке).

Подскажите как лучше это организовать.
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
eXtream
24 / 24 / 0
Регистрация: 10.03.2010
Сообщений: 161
09.09.2013, 15:13     Проверка на расстановку скобок #2
в цикле ищем скобку begin если находим то с следующей позиции ищем скобку end, если нет скобки end то error
saserlend
10 / 10 / 1
Регистрация: 25.11.2011
Сообщений: 139
09.09.2013, 15:27  [ТС]     Проверка на расстановку скобок #3
Цитата Сообщение от eXtream Посмотреть сообщение
в цикле ищем скобку begin если находим то с следующей позиции ищем скобку end, если нет скобки end то error
Все сложней.
Пример: ( [ { < > } ] ) результат - true
а ( [ < { ] > } ) результат - false.
Пример: ((( )( ))( )), результат – true;
)(((())), результат – false.
Пример: {}[]()(()[]) результат – true;
Пример: (}{), результат – false.
Croessmah
Модератор
Эксперт С++
 Аватар для Croessmah
11849 / 6828 / 773
Регистрация: 27.09.2012
Сообщений: 16,930
Записей в блоге: 2
Завершенные тесты: 1
09.09.2013, 15:31     Проверка на расстановку скобок #4
Работа со стеком (Необходимо проверить,правильно ли расставлены скобки)
SatanaXIII
Супер-модератор
Эксперт С++
 Аватар для SatanaXIII
5549 / 2563 / 233
Регистрация: 01.11.2011
Сообщений: 6,337
Завершенные тесты: 1
09.09.2013, 15:34     Проверка на расстановку скобок #5
Цитата Сообщение от saserlend Посмотреть сообщение
Все сложней
Берется четыре стека - каждый на свой вид скобочек. Парсер разбирает строку следующим образом:
- встретилась открывающая скобочка - записать ее в соответствующий стек.
- встретилась закрывающая скобочка - проверить есть ли в соответствующем стеке предыдущая открывающая скобочка. Если есть, то вычесть одну. Если нет, то ошибка разбора.
CheshireCat
Эксперт С++
2907 / 1235 / 78
Регистрация: 27.05.2008
Сообщений: 3,309
09.09.2013, 15:58     Проверка на расстановку скобок #6
Хм, пожалуй, нет. Стек должен быть один. Иначе с четырьмя стеками возможна ситуация:
([)] - считается, что расстановка скобок правильная, а это не так.
Raali
572 / 276 / 12
Регистрация: 06.07.2013
Сообщений: 917
Завершенные тесты: 1
09.09.2013, 16:01     Проверка на расстановку скобок #7
Цитата Сообщение от CheshireCat Посмотреть сообщение
([)] - считается, что расстановка скобок правильная, а это не так.
каким образом, если все 2 стека окажутся незакрытыми, и еще 2 с ошибкой закрытия
CheshireCat
Эксперт С++
2907 / 1235 / 78
Регистрация: 27.05.2008
Сообщений: 3,309
09.09.2013, 16:10     Проверка на расстановку скобок #8
Нет. Вот смотри, если руководствоваться изложенными правилами:
Парсер разбирает строку следующим образом:
1) - встретилась открывающая скобочка - записать ее в соответствующий стек.
2) - встретилась закрывающая скобочка - проверить есть ли в соответствующем стеке предыдущая открывающая скобочка. Если есть, то вычесть одну. Если нет, то ошибка разбора.
У нас есть стеки s1, s2, s3, s4. Анализируем строку: ([)]
Берем первую скобку: ( - она открывающая. По п.1 помещаем ее в стек - например, s1.
Берем вторую скобку: [ - она тоже открывающая, помещаем ее в стек s2.
Итого: s1 содержит (, s2 содержит [, стеки s3 и s4 пока пусты.
Разбираем строку дальше: третья скобка ) - закрывающая. По правилу п.2 выбираем открывающую скобку из стека s1 - открывающая скобочка там как раз есть.
Разбираем следующую скобку: ] - закрывающая, поэтому выбираем открывающую скобочку из стека s2 - она там как раз есть.
Строка закончена.
Все стеки у нас пусты. Вывод: скобки расставлены правильно.

А на самом деле это не так!
Raali
572 / 276 / 12
Регистрация: 06.07.2013
Сообщений: 917
Завершенные тесты: 1
09.09.2013, 16:15     Проверка на расстановку скобок #9
значит используем 1 стек, и заносим тип скобки
Archi0
28 / 14 / 4
Регистрация: 18.07.2013
Сообщений: 164
04.09.2014, 12:25     Проверка на расстановку скобок #10
А если усложнить задачу наличием разделителя ','. Между двумя ',' скобки должны быть растравлены правильно, а также количество открывающих и закрывающих равны. ',' нельзя поставить вне блока скобок. между открывающей или закрывающей блок скобки и ',' действует тоже правило на скобки, что на случай между двумя ','
Boleon
Guardian of Asgaard
372 / 315 / 106
Регистрация: 11.11.2013
Сообщений: 1,045
04.09.2014, 12:34     Проверка на расстановку скобок #11
Archi0,
А если усложнить задачу наличием разделителя ','
Зачем?
Archi0
28 / 14 / 4
Регистрация: 18.07.2013
Сообщений: 164
04.09.2014, 13:17     Проверка на расстановку скобок #12
ну типа функции в строке. Неверно описал задачу, так как между двумя ',' может быть другая функция.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
04.09.2014, 14:20     Проверка на расстановку скобок
Еще ссылки по теме:

Проверка числа открывающихся и закрывающихся скобок C++
Проверка правильности расстановки скобок в строке (рекурсия) C++
C++ Проверка баланса скобок арифметического выражения, введенного с клавиатуры

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

Или воспользуйтесь поиском по форуму:
gru74ik
Модератор
 Аватар для gru74ik
3131 / 1357 / 168
Регистрация: 20.02.2013
Сообщений: 3,877
Записей в блоге: 18
04.09.2014, 14:20     Проверка на расстановку скобок #13
Было же:
Формула, по которой можно вычислить время наступления Рагнарека
Yandex
Объявления
04.09.2014, 14:20     Проверка на расстановку скобок
Ответ Создать тему
Опции темы

Текущее время: 17:35. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru