pattern heroPT–23LeetCode Extension

Стек

Кладём элементы в стопку и всегда берём верхний, то есть последний положенный. Так обрабатывают вложенное, например скобки: пару для закрывающей скобки не ищут по всей строке, она всегда наверху.

Вариант
P07 СтекСкобки · 1×

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

вызов 1([]{})вызов 2[{(})]стек—
ещё не прочитанаch, читаем сейчасоткрыта, в стекеtop, сняли для сравнениязакрыта в паре

Первый вызов, s = "([]{})": начинаем с пустого стека

s = "([]{})"stack = []ch = –top = –
01/38
сначала · назад · пуск · шаг
Скорость
1function isValid(s):
2 stack = empty stack
3 for each ch in s:
4 if ch is an opener:
5 push ch onto stack
6 else:
7 top = pop from stack or none
8 if top is not pair[ch]:
9 return false
10 return stack is empty

← → шаг · пробел — пауза

Как узнать

вложенные пары (скобки, теги), отмена или «шаг назад» (путь с ".."), вычисление выражения или стек, который должен сразу отвечать «какой минимум?», если хранить рядом с каждым элементом что-то ещё, например текущий минимум.

Как решать такие задачи

  1. Спроси себя, нужно ли закончить сначала то, что начато последним: открытую скобку, папку, в которую зашли, число, которое ждёт операцию.
  2. Клади в стек то, что ещё открыто. Когда что-то это закрывает, сними верх и проверь или объедини.
  3. Не забудь крайние случаи: снятие из пустого стека и то, что осталось в стеке в конце.
  4. Если в любой момент нужен ещё и минимум (или максимум), клади его вместе с каждым элементом: пару (значение, минимум до сих пор). Тогда верх всегда знает ответ за O(1).

Вариант: Вычисление

То же, но в стопке лежат числа: операция снимает два верхних, считает и кладёт результат обратно. Так вычисляют выражение без скобок и приоритетов.

  1. Каждое число сразу клади в стек.
  2. На операции сначала сними b, потом a: верх — правый операнд, это важно для − и ÷.
  3. Положи a op b обратно; в конце в стеке ровно одно число — ответ.
  4. Для обычного выражения со скобками держи текущий результат и знак; на «(» положи их в стек и начни заново, на «)» сними и объедини.

Где встречается

  • Вызовы функций. Когда функция вызывает другую, программа кладёт в стек, куда вернуться. Вернуться нужно сначала из последнего вызова, поэтому это стек, а ошибка «stack overflow» — его переполнение.
  • Разбор HTML. Читая страницу, браузер держит стек открытых тегов. Закрывающий тег закрывает тот, что на верху стека; так парсер описан в стандарте HTML.
  • Отмена действий. Ctrl+Z в редакторе отменяет сначала последнее действие, потом предыдущее: действия лежат в стеке.