Наложение скобок [дубликат]

383

31 августа 2017, 18:12

На данный вопрос уже ответили:

Вернуть true если скобки совпадают 3 ответа
Проверить правильно ли вложены скобки 〈 ( { [ ] } ) 〉в тексте 2 ответа

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

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

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

Нету вообще никаких идей по поводу того, как можно проверить "наложение" скобок. Как это сделать?

Answer 1

Какие тут могут быть идеи кроме как "в лоб" - хранить в стеке открывающие скобки, а на каждую закрывающую доставать последний элемент из стека и проверять на соответствие типу скобки.

Answer 2

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

Изначально стек пуст, в нем будут хранится открывающиеся скобки. Мы итерируемся по строке символов, если текущий символ - открывающаяся скобка, кидаем его в стек, если это закрывающаяся скобка, то смотрим на состояние стека. Если он пуст - последовательность некорректна (на вход дана последовательность вида '())'). Иначе достаем верхушку из стека и сравниваем на соответсвие (т.е. если сверху '(', то сейчас должна быть ')' и т.д.), если не соответствует - последовательность некорректна (последовательность вида '{]').

После проверки всех символов строки смотрим на состояние стека. Если он не пуст - последовательность некорректна (к примеру, '((()').

Если до сих пор не определено, что последовательно некорректна, то мы можем утверждать, что она корректна.

Answer 3

В комментариях меня поправили, так что: ПРИМЕР НЕВЕРНОГО АЛГОРИТМА))

Можно хранить только кол-во скобок и код последней открытой. Например, пусть A [1] - кол-во квадратных открытых - кол-во квадратных закрытых (по умолчанию = 0) A [2] - то же самое для круглых A [3] - для фигурных. И пусть B = 0 - код последней открытой скобки (напр. для круглой B = 2)

Читаем посимвольно текст

Если мы встречаем открытую скобку, то A[i]++,

закрытую - 1) A[i]-- и 2) если A[i] меньше нуля, то сразу неверно расставлены 3) если закрытая скобка не соответствует B и B!=0, то неверно

В итоге, если все A[i]==0, то верно.

Алгоритм придуман только что, поэтому не тестился.