Сбалансированные скобки на Python: как работает стек

Скобки сбалансированы, когда каждая закрывающая скобка завершает последнюю ещё не закрытую пару своего типа. Одного равенства количества открывающих и закрывающих мало: в строке ([)] числа совпадают, но порядок вложенности нарушен. Проверить порядок помогает стек. Примеры ниже выполнены на CPython 3.14.5.

Баланс означает порядок, а не только количество

Для одного вида скобок счётчик кажется достаточным: ( увеличивает число, ) уменьшает. Но даже здесь есть два разных сбоя. Счётчик не должен становиться отрицательным по ходу строки, а в конце обязан вернуться к нулю.

С несколькими видами скобок количества уже не хранят главную информацию: какая открывающая скобка была последней. Это видно на коротком примере:

source = "([)]"
round_counts_match = source.count("(") == source.count(")")
square_counts_match = source.count("[") == source.count("]")

print(round_counts_match, square_counts_match)

True True

Обе проверки проходят, хотя ) пытается закрыть ( через незавершённую [. Значит, алгоритму нужна история открывающих скобок с сохранением их порядка.

Стек хранит последнюю незавершённую пару на вершине

Стек работает по правилу LIFO: последний добавленный элемент извлекается первым. В Python отдельный тип для простого стека не нужен. Обычный список добавляет элемент на вершину через append() и снимает вершину через pop() без индекса.

stack = []
stack.append("config")
stack.append("section")
stack.append("field")

print(stack.pop())
print(stack.pop())
print(stack)

field
section
['config']

Первым вышел field, хотя его добавили последним. Для вложенных скобок это ровно нужное поведение: внутренняя пара должна закрыться раньше внешней.

Список изменяется на месте, поэтому append() и pop() работают с одним объектом. Подробнее это поведение разобрано в материале про изменяемые и неизменяемые типы Python.

Для каждой закрывающей нужна ожидаемая открывающая

Связь между шестью символами удобно представить как таблицу:

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

Таблица соответствий лучше трёх разрозненных веток. В ней видно само отношение «закрывающая → открывающая», а добавление нового вида пары не требует переписывать логику обхода. Но полная реализация остаётся практической задачей: здесь нет готовой функции проверки.

У проверки есть три точки отказа

Несбалансированность обнаруживается в одном из трёх мест.

Закрывающая пришла при пустом стеке. У неё нет открывающей пары. Вызов pop() на пустом списке завершится IndexError, поэтому сначала проверяют состояние стека.

stack = []

if stack:
    print(stack.pop())
else:
    print("стек пуст")

стек пуст

Вершина другого типа. Для ([)] перед символом ) на вершине лежит [. Количество пар не поможет: ошибка именно в порядке.

После обхода что-то осталось. Строка (() ни разу не пытается снять неверную вершину, но последняя ( остаётся без пары. Поэтому успешный обход ещё не означает успешный результат; в конце стек должен быть пуст.

Пустая строка и текст без скобок корректны

Если учитываются только символы ()[]{}, пустая строка не содержит незакрытых пар и считается сбалансированной. По той же причине строка host = localhost корректна: обычные буквы, пробелы и знак равенства не попадают в стек.

Полезный набор граничных случаев:

Тесты () и (( проверяют разные ветви. Первый подтверждает обычное закрытие, второй ловит забытый финальный контроль пустоты. Пара ([)] отдельно защищает от неправильного решения на счётчиках.

Один проход даёт линейную сложность

Каждый символ читается один раз. Операции append() и pop() на конце списка подходят для стека, поэтому время проверки растёт линейно с длиной строки: O(n).

Память зависит от глубины вложенности. В худшем случае строка состоит только из открывающих скобок, и все они остаются в стеке. Тогда потребуется O(n) дополнительной памяти. Для строки без скобок стек остаётся пустым.

Рекурсия здесь не нужна. Она усложнит обработку обычной строки и упрётся в ограничение глубины вызовов на длинном вводе. Один список и один проход выражают условие задачи напрямую.

Практика

В задаче «Сбалансированные скобки на Python» нужно применить стек к трём видам пар и проигнорировать остальные символы. Задача входит в путь «Python: структуры данных», где стек используется рядом с другими базовыми структурами.