1Understand
The idea
A stack remembers what is still open. Push when something opens (a bracket, an operand, a directory) and pop when it closes; the top is always the most recent unfinished item. At the end, an empty stack means everything matched.
Intuition
A stack remembers what is still open. Push when something opens (a bracket, an operand, a directory segment) and pop when it closes; the top is always the most recent unfinished item.
At the end, an empty stack means everything matched. A close with an empty stack, or a final leftover open, means failure. The same discipline evaluates RPN, simplifies paths, and decodes nested strings.
Anything "most recently unmatched" is a stack cue.
What you will be able to do
- Push/pop on the right events
- Check the stack is empty at the end
When to use it
- Balanced brackets
- Evaluate an expression
- Most recent unmatched item
2See it
Walkthrough
Valid parentheses
s = "([])", push openers, pop on closers; the top must match.
1 / 4
See "(". Push it. Stack = ["("].
Live template
Line 1 active
Complexity: time O(n), space O(n)
Time O(n), space O(n) for the stack in the nested worst case. Regex or counting alone cannot handle multiple bracket types with proper nesting. For path simplify / calculators, the same O(n) bound holds; the stored items change, not the pattern.
Read the walkthrough as text
Valid parentheses. s = "([]){}".
- Push
'(', then'['. - See
']': top'['matches, pop. - See
')': top'('matches, pop. - Push
'{', see'}', pop. Stack empty → valid.
In code:
pairs = {')':'(', ']':'[', '}':'{'}stack = []for ch in s:if ch in '([{':stack.append(ch)elif not stack or stack.pop() != pairs[ch]:return Falsereturn not stack
3Recognise it
Kinds of problems (8)
Same pattern, different surfaces. Each row is a problem shape you should recognise, not only the first walkthrough example.
Balanced brackets
Example. Is the bracket string valid?
How. Push opens; on close, pop must match; stack empty at end.
Reverse Polish notation
Example. Evaluate an RPN expression.
How. Push numbers; on operator, pop right then left (order matters), push result.
Simplify a path or undo operations
Example. Canonical Unix path or matching undo/redo.
How. Stack of segments: push names, pop on "..", skip duplicates like ".".
Decode nested strings
Example. 3[a2[c]] → accaccacc.
How. Stack of (count, prefix) or (count, string); expand when you see ].
Basic calculator
Example. Evaluate +, -, parentheses.
How. Stack current number and last sign; on ")", push outer context and evaluate inner.
Collision or fleet simulation with a stack
Example. Cars stack when slower ahead; process from right.
How. Monotonic stack of indices by position/speed; pop when current catches up.
Stack of (value, count) pairs
Example. Remove adjacent duplicates k times.
How. Push (val, count); merge with top when val matches and count+k threshold met.
Simulate push and pop sequences
Example. Can target stack order be built from 1..n pushes?
How. Simulate: push next number until top equals next needed pop, then pop.
Common mistakes
Failure modes the tutor watches for. Open the Common mistake tab in the walkthrough to watch one fail live.
Pop from empty stack
Why it happens. You expect a close bracket to always have a partner.
How it fails. s = ")": stack.pop() on empty raises IndexError instead of returning false for invalid.
Fix. Check stack before pop; on close, empty or mismatch → invalid.
Leftover items ignored
Why it happens. The last closers balanced, so the string feels done.
How it fails. "(()", stack still has "(" at the end; returning True without checking not stack.
Fix. Valid only if every open was closed: return not stack after the scan.
Operand order
Why it happens. Addition commutes, so operand order seems irrelevant.
How it fails. RPN "3 4 -": pop a=3, b=4, push a-b = -1 but correct is b-a = 1.
Fix. On binary op: second = pop(), first = pop(), push first op second (not the reverse).
4Check yourself
Concept check
A short quiz on this lesson before you practise. Optional, and it does not gate coding.
Ready to practise?
Mastery comes from solving. The lesson is optional context.