Стек: незавершённая работа и скобки

Трассировка ([]): после ( стек равен ['('], после [ — ['(', '[']; символы ] и ) снимают ожидаемые пары, поэтому к концу стек пуст.

Стек ограничивает доступ намеренно

Стек хранит последовательность, но разрешает работать только с её вершиной: push кладёт новый элемент, top/[-1] читает последний, pop удаляет его. Это порядок LIFO — last in, first out, «последним пришёл — первым вышел».

Обычно стек реализуют поверх динамического массива: вершина находится в конце, поэтому добавление и удаление не сдвигают остальные элементы. В C++ адаптер std::stack намеренно скрывает индексы и середину базового контейнера. В Python отдельного встроенного класса стека не требуется: list.append и list.pop() работают с правым концом. pop(0) — уже не стек и стоит O(n).

Стек вызовов и стек данных — одна идея, но разные объекты

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

Явный стек в контейнере полезен, когда мы хотим сами управлять обходом: итеративный DFS, разбор выражения, undo, вычисление постфиксной записи. Он не «ускоряет рекурсию» автоматически, но делает состояние и предел памяти видимыми.

Когда последовательность скобок корректна?

Проверить, является ли строка из ()[]{} правильной скобочной последовательностью.

Можно ли просто удалять готовые пары?

Пока строка меняется, удалять из неё пары (), [], {}. Если останется пустая строка, ответ положительный.

Почему повторные удаления дают квадратное время?

Каждое удаление сдвигает символы и вынуждает многократно пересматривать строку; в худшем случае получается O(n²).

Какая открывающая скобка обязана закрыться первой?

Закрывающая скобка может сопоставляться только с самой поздней ещё не закрытой открывающей скобкой.

Что хранит стек после каждого префикса?

Стек содержит открывающие скобки обработанного префикса, ещё не получившие пару, в порядке их появления.

Один проход по открывающим и закрывающим символам

Идти слева направо. Открывающую скобку положить в стек. Для закрывающей проверить непустой стек и совпадение типа с вершиной, затем снять вершину. После прохода стек должен быть пуст.

Проверка скобок на C++17 и Python 3

C++17

#include <cassert>
#include <stack>
#include <string>
using namespace std;

bool isValid(const string& text) {
    stack<char> opened;
    for (char token : text) {
        if (token == '(' || token == '[' || token == '{') {
            opened.push(token);
            continue;
        }
        if (token != ')' && token != ']' && token != '}') return false;
        if (opened.empty()) return false;
        char expected = token == ')' ? '(' : token == ']' ? '[' : '{';
        if (opened.top() != expected) return false;
        opened.pop();
    }
    return opened.empty();
}

int main() {
    assert(isValid(""));
    assert(isValid("([])"));
    assert(!isValid("([)]"));
    assert(!isValid("]"));
    assert(!isValid("a"));
}

Python 3

def is_valid(text: str) -> bool:
    opened: list[str] = []
    matching = {")": "(", "]": "[", "}": "{"}
    for token in text:
        if token in "([{":
            opened.append(token)
            continue
        if token not in matching:
            return False
        if not opened or opened[-1] != matching[token]:
            return False
        opened.pop()
    return not opened


assert is_valid("")
assert is_valid("([])")
assert not is_valid("([)]")
assert not is_valid("]")
assert not is_valid("a")

Каждый символ входит в стек не более одного раза

O(n) времени и O(n) памяти в случае строки из одних открывающих скобок. Чтение вершины и удаление с конца занимают O(1); добавление в стек поверх динамического массива — амортизированное O(1), но отдельное расширение буфера может стоить O(n).

Инвариант важнее выбранного контейнера

Стек можно физически хранить в vector, deque или связных узлах. Алгоритм становится стековым не из-за названия типа, а потому что разрешён только последний незавершённый элемент. Если код произвольно читает середину коллекции, стоит заново проверить, действительно ли модель LIFO выражает задачу.

Монотонный стек — производная идея: кроме LIFO он удаляет кандидатов, которые уже не могут стать ответом. Обычный стек хранит порядок незавершённой работы; монотонный — ещё и инвариант порядка значений.

Пустой стек, неверная пара и незакрытый остаток

Пустая строка корректна; первая скобка закрывающая; несовпадающие типы ([)]; лишняя открывающая в конце; символ вне алфавита ()[]{} отклоняется.

Строки, которые ловят ошибку сопоставления

"" -> true, "([])" -> true, "([)]" -> false, "]" -> false, "((" -> false, "a" -> false.

Где в условии скрыт порядок LIFO?

Есть вложенные конструкции, и текущий символ должен завершать последнюю незавершённую конструкцию.

Когда одного стека для синтаксиса недостаточно?

Стек не подходит, если закрытие может законно соответствовать не последнему открытому объекту. Для обработки в порядке поступления нужна очередь; для многократного извлечения лучшего по приоритету — куча. Если нужны произвольный индекс и сортировка всего набора, обычный массив предоставляет более прямой интерфейс.

Мини-проверка: почему ([)] отклоняется на символе )?

Вопрос: почему ([)] отклоняется на символе )? Ответ: вершина стека — [, а закрывается другой тип.

Мини-проверка: после прохода стек не пуст

Вопрос: достаточно ли не встретить ошибку во время прохода? Ответ: нет; после (( стек непуст, значит конструкции не закрыты.

Проследите стек для вложенной строки

Проследите стек для {[()]} после каждого символа, затем измените предпоследнюю скобку и укажите первый ошибочный шаг.

Проверьте скобки без готового алгоритма

Задача 1

Реализуйте проверку строки с ()[]{} и верните индекс первой ошибочной закрывающей скобки либо -1, если последовательность корректна.

Стек хранит только незавершённые пары

Стек нужен потому, что вложенность закрывается в обратном порядке: последняя открытая скобка должна закрыться первой.