Описание структуры

Стек - структура с двумя операциями: push(x) и pop().

Первая добавляет x в стек, а вторая — удаляет последний добавленный элемент, то есть стек работает по принципу FILO — “First In, Last Out”.

Реализации

Фактически обычные std::vector в C++, list в python и другие динамические массивы реализуют стек.

Для вектора в C++ необходимые операции — методы push_back() и pop_back(), для питона — append() и pop().

Все указанные операции работают за амортизированную $O(1)$.

Задачи на стек

Правильная скобочная последовательность

Правильная скобочная последовательность (далее ПСП) — это последовательность из скобок, определяющиеся следующим образом:

1. пустая строка — ПСП
2. пусть A - ПСП, то (A) — тоже ПСП
3. пусть A и B — ПСП, то AB — тоже ПСП

Примеры скобочных последовательностей:

• правильных - ((()()()())), ()(()())
• неправильных - )( и (())))(

Задача заключается в том, чтобы проверить, является ли данная последовательность из скобок правильной.

Cкобки одного типа

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

Решением в этом случае будет подсчёт баланса на префиксах строки, то есть количества открытых скобок минус количество закрытых.

Последовательность будет являться правильной, если на всех ее возможных префиксах баланс неотрицателен, а баланс всей строки равен нулю.

Чтобы это проверить, достаточно пройтись по массиву, поддерживая баланс:

• добавляя +1, если текущая скобка является открывающей
• и -1, если скобка закрывающая

Если на каком-то шаге, баланс оказался отрицательным, перед нами не ПСП.

Так же стоит проверить, что баланс всей строки равен 0. В противном случае не все скобки разбиваются на пары, и такая последовательность не будет являться правильной.

Скобки разных типов

Однако задача становится сложнее, если допустить различные виды скобок (например, (, {, [, <).

Заметим, что решение с балансом работает неправильно, ведь оно не учитывает, что скобки разных типов не могут образовывать пары.

Например, для последовательностей [)(], {}<) алгоритм выдаст положительный ответ, однако эти последовательности правильными не являются.

Воспользуемся стеком. Как и раньше будем поочереди обрабатывать скобки в последовательности, однако вместо поддержки баланса будем делать следующее:

• добавлять в стек скобку, если она является открывающей
• иначе будем сравнивать тип текущей скобки и последней открывающей скобки, которая лежит в вершине стека, и удалять ее, если она является парой к текущей

Если на каком-то шаге, стек пуст или пара не подошла, перед нами не ПСП.

Аналогично, нужно проверить, что в конце стек остался пустым.

---

Примечание. Для более компактного кода лучше использовать словарь для определения пары скобки.

pair = {')': '(', '}': '{', ']': '['}