Введение
Определение
Правильной скобочной последовательностью называется строка, состоящая только из скобок, в которой все скобки можно разбить на пары таким образом, что:
- в каждой паре есть левая и правая скобка, причем левая скобка расположена левее правой;
- для любых двух пар скобок либо одна из них полностью находится внутри другой пары, либо промежутки между скобками в парах не пересекаются;
- в паре с круглой скобкой может быть только круглая скобка, с квадратной — квадратная, с фигурной — фигурная.
Примеры
Если разрешены только круглые скобки:
- правильные последовательности:
(),(()),()(),()()(),(())(),((())); - неправильные последовательности:
)(,)),((,())()(,()),))((;
Если разрешены круглые и квадратные скобки:
- правильные последовательности:
[],(),[()],[[([])]()]; - неправильные последовательности:
[),([)],(())()[]][;
Если разрешены еще и фигурные скобки:
- правильные последовательности:
[{(())}({})],[]{}(),{},(),[]; - неправильные последовательности:
[{(})],[(]())]{}.
Задача
Во входном файле задана строка α, состоящая только из скобок (круглых, квадратных и фигурных). Требуется определить, является ли она правильной скобочной последовательностью. Если да, выведите в выходной файл слово CORRECT. Если нет, выведите длину максимального префикса (начального отрезка) α, который либо сам является правильной скобочной последовательностью, либо может быть продолжен до таковой.
Например, для строки (()))) ответом будет 4, так как строка (()) является правильной скобочной последовательностью, а строку (())) уже нельзя никаким образом продолжить вправо, чтобы получить правильную скобочную последовательность. Для строки ]())( ответ 0, поскольку строку ] нельзя продолжить вправо, чтобы получить правильную скобочную последовательность. Для строки [(()){()()[[]]}] ответ CORRECT.
Указание. Понадобится стек. У класса std::vector есть методы push_back и pop_back, с помощью которых его можно легко имитировать (последнее указание для языка C++).
Решение
Рассмотрим первую правую скобку, встречающуюся в строке. Если она находится на первой же позиции, то строка уже некорректна и нельзя ничего приписать справа, чтобы она стала корректной (не найдется пары к самой первой правой скобке).
Если же данная скобка встречается на позиции r > 0, то скобка на позиции r – 1 является левой, и она является парной к данной правой скобке.
Действительно, если бы какая-то левая скобка на позиции l < r – 1 была парой к правой скобке на позиции r, то пара к левой скобке на позиции r – 1 находилась бы правее r, и тогда эти две пары пересекались бы, что противоречит определению. С другой стороны, если самая первая правая скобка стоит на позиции r > 0, то строку еще можно продолжить так, чтобы она стала корректной: нужно дописать столько правых скобок, чтобы закрыть все левые скобки, и остановиться. Поэтому самая первая правая скобка и левая скобка сразу перед ней соответствуют друг другу.
Теперь если выкинуть эту пару скобок из строки, то корректность оставшейся строки определяется тем же самым способом, так как пара скобок, стоящая непосредственно рядом (без промежуточных скобок) не мешает выполнению ни одного из наложенных условий. Из этих соображений вытекает следующий алгоритм решения задачи.
Из определения корректной скобочной последовательности следует, что при чтении такой последовательности слева направо всегда есть набор открывающих скобок, ожидающих себе парных закрывающих скобок (по первому свойству). При этом если встречается очередная закрывающая скобка, то она должна быть парной именно к последней открывающей скобке, иначе нарушилось бы второе свойство. В тот момент, когда для последней открывающей скобки в наборе находится парная закрывающая, эта открывающая скобка из набора удаляется, ожидающих открывающих скобок становится на одну меньше, и последней становится та, что была предпоследней. В конце, когда мы прочитали все символы строки, стек должен оказаться пустым: к каждой открывающей скобке нашлась парная. Кроме того, в процессе обработки никогда не должно получиться, что мы читаем закрывающую скобку, а стек либо пуст, либо на его вершине находится неправильная открывающая скобка. В этом случае последовательность сразу же получается некорректной, и к ней уже справа ничего нельзя дописать, чтобы последовательность стала корректной.
Такое поведение ожидающих открывающих скобок позволяет хранить их в стеке, используя следующий алгоритм. Изначально стек пустой. Идем по строке слева направо, считывая по одному символу. В зависимости от очередного символа, выполняем действия.
- Если очередной символ — открывающая скобка, то кладем его на стеки, двигаемся дальше.
- Если очередной символ — закрывающая скобка, то посмотрим на состояние стека. Если на стеке нет ни одного элемента или открывающая скобка на вершине стека не соответствует текущей закрывающей скобке, то последовательность неправильная. При этом она могла быть дополнена до правильной последовательности до текущего момента (обоснуйте), а после того, как найдена неправильная закрывающая скобка, она уже не может быть дополнена до правильной. Соответственно, нужно вывести длину прочитанного префикса, не включая последнюю прочитанную скобку, и выйти из программы. Если стек не пуст и в вершине стека лежит соответствующая открывающая скобка, удаляем из стека эту скобку и двигаемся дальше.
В конце, если пройдена вся строка до конца, нужно еще не забыть определить, является ли прочитанная строка правильной скобочной последовательностью или же только началом правильной скобочной последовательности. Если стек в конце просмотра строки пуст, то прочитанная строка является правильной скобочной последовательностью и нужно выдать CORRECT. Если же стек не пуст, то строку можно дополнить до правильной скобочной последовательности, но она еще такой не является, поэтому нужно выдать длину всей строки.
Для анализа каждого очередного символа строки требуется константное время, поэтому общая сложность алгоритма составляет O(n). Памяти требуется O(n) на хранение самой строки и O(n) на стек.
Список литературы
- Бабенко М. А., Левин М. В. Введение в теорию алгоритмов и структур данных. Электронное издание М.: МЦНМО, 2016. с. 11–14. Книга доступна в нашей группе по ссылке.