ПСП
Есть несколько определений Правильной скобочной последовательности(ПСП).
1) Неформальное определение
ПСП - это строка из открывающих и закрывающих скобок, который получается из арифметических выражений удалением всего, кроме скобок.
Например: из выражения $(1 + 2) * (3 + 100 * (3 / 2))$ получается ПСП $()(())$. А вот $)(())$ не получится из никакого выражения.
2) Явное определение
ПСП - это строка из открывающих и закрывающих скобок, в которой все скобки можно разделить на пары, где первая скобка - открывающая, а вторая - закрывающая, открывающая идет раньше закрывающей, и никакие две пары не пересекаются.
Например: $((())())$ - ПСП, так как разбивает на вот такие непересекающиеся пары: $\textbf{(}\underline{(}\overline{(}\overline{)}\underline{)}\textit{()}\textbf{)}$. А вот строку $(()$ нельзя разбить на пары - там нечетное число скобок.
3) Рекурсивное определение
- пустая строка - это ПСП
- если $A$ - это ПСП, то $(A)$ - это тоже ПСП
- если $A$ и $B$ - это ПСП, то $AB$ - это тоже ПСП
Например: пустая строка - ПСП, значит $()$ - ПСП, значит $(())$ - ПСП, значит $(())()$ - ПСП, значит $((())())$ - ПСП. А вот $())(()$ не получится по этим правилам никак.
4) Определение через баланс ПСП - это строка из открывающих и закрывающих скобок. Давайте определим **баланс** на префиксе длины $n$ как разница числа открывающих и закрывающих скобок на этом префиксе. Тогда в ПСП должны выполняться два свойства:
- любой баланс больше или равен 0
- баланс всей строки равен 0
То есть на любом префиксе открывающих скобок не меньше, чем закрывающих, а во всей строке их равное число.
Оказывается, именно последним определением удобно пользоваться, чтобы определить, является ли строка ПСП. А именно, давайте пройдемся слева направо и будем прибавлять $+1$, если встретим открывающую скобку, и $-1$, если встретим закрывающую скобку. И достаточно проверить, что баланс всегда неотрицателен, и равен нулю в конце.
Еще можно определить ПСП с разными видами скобок. Например, $([](\{\}))$ - это ПСП, а $[(])$ - нет. В явное определение надо просто добавить, что скобки в одной паре должны быть одного вида. В рекурсивное определение нужно добавить правила вида "если $A$ - это ПСП, то $[A]$ - это тоже ПСП" для всех видов скобок.
А вот определение через баланс так легко не обобщается, а ведь мы именно его хотим использовать для алгоритма проверки на ПСП. Для расширения придется использовать стек:
ПСП - это такая строка из открывающих и закрывающих скобок разного типа, если построении стека открытых скобок при прохождении по строке не возникает ошибки, а в конце стек пустой. А именно, давайте заведем пустой стек, пройдемся слева направо и будем класть в конец стека открывающую скобку, если мы ее встретили, и вынимать её, если встретили закрывающую - при этом надо проверить, что вынимаемся открытая скобка того же типа, что и встреченная закрывающая.
Например: строка $\{[([])()]{}\}$. В ходе алгоритм стек будет меняться так:
- пустой
- $\{$
- $\{[$
- $\{[($
- $\{[([$
- $\{[($ - убранная $[$ подходит $]$
- $\{[$ - убранная $($ подходит $)$
- $\{[($
- $\{[$ - убранная $($ подходит $)$
- $\{$ - убранная $[$ подходит $]$
- $\{\{$
- $\{$ - убранная $\{$ подходит $\}$
- пустой - убранная $\{$ подходит $\}$
Все убранные скобки подошли встреченным закрытым, а в конце стек пустой - а значит это ПСП.
А вот строка $[ \{ ]}$ - это не ПСП:
- пустой
- $[$
- $[ \{$
- ошибка, так как $\{$ в конце стека не подходит $]$
Такой алгоритм работает за $O(N)$ - так как мы проходимся по массиву и каждый раз делаем одну из операций со стеком - либо push, либо pop.