ПСП

Есть несколько определений Правильной скобочной последовательности(ПСП).

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.