Стек — естественный инструмент везде, где «последним положенный выходит первым». В этом уроке пять классических применений: скобки, RPN, undo/redo, DFS и монотонный стек. Сам стек реализован в прошлом уроке (реализация стека); здесь хватит обычного list.

Проверка скобок
Проверка скобок

Проверка скобок

Открывающую скобку кладём на стек. На закрывающей снимаем вершину и проверяем пару. Три вида ошибок: пара не совпала, закрывающая встретила пустой стек, в конце остались открывающие. Строка правильная, только если ничего из этого не случилось и стек пуст. Время O(n), память O(n).

python
PAIRS = {")": "(", "]": "[", "}": "{"}

def balanced(s):
    stack = []
    for ch in s:
        if ch in "([{":
            stack.append(ch)
        elif ch in PAIRS:
            if not stack or stack.pop() != PAIRS[ch]:
                return False
    return not stack

for s in ["{[()]}", "([)]", "((", ")("]:
    print(s, balanced(s))
text
{[()]} True
([)] False
(( False
)( False

Постфиксная запись (RPN)