pattern heroPT–23LeetCode Extension

Stack

Put items on a pile and always take the top one, the last one put there. That is how nested things like brackets are handled: the match for a closing bracket is never searched for, it is always on top.

Variant
P07 StackBrackets · 1×

Example problem: check whether every bracket in "([]{})" and in "[{(})]" is closed by its own kind, in the right order.

call 1([]{})call 2[{(})]stack—
not read yetch, read nowopen, on the stacktop, popped to compareclosed in a pair

First call, s = "([]{})": start with an empty stack

s = "([]{})"stack = []ch = –top = –
01/38
restart · back · play · step
Speed
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

← → step · space play/pause

How to recognise

nested pairs (brackets, tags), undo or "go back one step" (a path with ".."), evaluating an expression, or a stack that must also answer "what is the minimum?" at once, by keeping extra info such as the running minimum next to each entry.

How to solve problems like this

  1. Ask whether the latest unfinished thing must be finished first: an open bracket, a folder you went into, a number waiting for its operator.
  2. Push what is still open. When something closes it, pop the top and check or combine.
  3. Handle the edges: popping an empty stack, and items still on the stack at the end.
  4. If you also need the minimum (or maximum) at any moment, push it with each entry: the pair (value, minimum so far). Then the top always knows the answer in O(1).

Variant: Evaluate

The same, but the pile holds numbers: an operation takes the top two, works out the result and puts it back. That evaluates an expression with no brackets or precedence rules.

  1. Push every number as soon as you read it.
  2. On an operator, pop b first and a second: the top is the right operand, which matters for − and ÷.
  3. Push a op b back; at the end the stack holds exactly one number, the answer.
  4. For an ordinary expression with brackets, keep the result and sign so far; at "(" push them and start fresh, at ")" pop them and combine.

Where it's used

  • Function calls. When a function calls another, the program pushes where to come back to. The latest call has to return first, so this is a stack, and a "stack overflow" error is that stack running out of room.
  • Reading HTML. While reading a page, the browser keeps a stack of open tags. A closing tag closes the one on top of the stack; that is how the HTML standard describes the parser.
  • Undo. Ctrl+Z in an editor undoes the last action first, then the one before it: the actions lie on a stack.