Stack Parsing and Expression Evaluation

Whenever the most recently opened thing must be closed first, you are looking at a stack. Brackets, nested arithmetic, [3[a2[c]]]-style encodings, directory paths, undo history — all the same shape, because all of them are last-in, first-out by definition.

This is a different use of a stack from Monotonic Stack. There, the stack holds a sorted set of candidates to answer next-greater-element questions. Here, the stack holds suspended context: work you must come back to once the current nested piece finishes.

What you’ll learn

• Bracket matching, and the two failure modes people forget.
• Why postfix (RPN) needs no precedence rules at all.
• The save-and-restore template for nested encodings — push the outer context, start a fresh inner one, merge on close.
• How to accumulate multi-digit numbers while scanning character by character.
• Three real LeetCode problems solved in the browser: 20, 150, 394.

The cue

You are looking at stack parsing when…

• The input has matched pairs: brackets, tags, quotes — 20, 921, 32.
• The structure is nested and can nest arbitrarily deep — 394, 224, 726.
• You are evaluating an expression with precedence or parentheses — 150, 227, 224.
• Something cancels its neighbour on contact — 1047, 2696.
• You are resolving a path with . and .. segments — 71.
• The recursive solution is obvious, and the interviewer says “now do it iteratively”. A stack is how you convert recursion to iteration.

Nesting depth is the tell

A single counter is enough for one kind of bracket — LC 20 with only () can be solved by incrementing and decrementing an integer.

The moment there are multiple bracket types, or you need to know what was opened rather than just how many, a counter is insufficient and you need the stack. If an interviewer starts with () only and then adds [] and {}, that is the pivot they are testing for.

Template 1 — matched pairs

valid_parentheses.py

def is_valid(s):
    pairs = {")": "(", "]": "[", "}": "{"}      # closer -> its opener
    stack = []
 
    for ch in s:
        if ch in pairs:                        # a closer
            if not stack or stack.pop() != pairs[ch]:
                return False                   # nothing open, or wrong type
        else:                                  # an opener
            stack.append(ch)
 
    return not stack                           # nothing may be left open
 
 
print(is_valid("([])"))    # True
print(is_valid("([)]"))    # False -- correctly nested matters, not just counts

Two failure modes, not one

Both of these must be handled or you will pass the samples and fail the suite:

1. A closer with nothing open — "]". Checking stack.pop() without first checking if not stack raises IndexError.
2. Leftovers at the end — "(". The loop completes without complaint, so the final return not stack is what catches it.

And the reason a counter fails: "([)]" has balanced counts of every bracket type but is not correctly nested. Only a stack sees that.

Template 2 — postfix evaluation, no precedence needed

Reverse Polish Notation puts operators after their operands, which removes precedence and parentheses from the problem entirely. Push operands; on an operator, pop two, combine, push the result.

eval_rpn.py

def eval_rpn(tokens):
    stack = []
    for t in tokens:
        if t in {"+", "-", "*", "/"}:
            b = stack.pop()            # SECOND operand pops FIRST
            a = stack.pop()
            if t == "+":   stack.append(a + b)
            elif t == "-": stack.append(a - b)
            elif t == "*": stack.append(a * b)
            else:          stack.append(int(a / b))   # truncate toward zero
        else:
            stack.append(int(t))
    return stack[0]
 
 
print(eval_rpn(["4", "13", "5", "/", "+"]))   # 6   -> 4 + (13 // 5)

Order of pops, and Python’s floor division

Pop order. The second operand is on top, so b = pop() then a = pop(). Getting this backwards is invisible for + and * and wrong for - and /.

Truncation. LeetCode 150 requires truncation toward zero, but Python’s // floors toward negative infinity: -7 // 3 == -3 where the required answer is -2. Use int(a / b), or abs(a) // abs(b) with the sign reapplied. This single line is the most common wrong submission on the problem, and ["7","-3","/"] is the test that exposes it.

Template 3 — save and restore for nested encodings

This is the pattern worth internalising, because it generalises to every “decode the nested thing” problem. Keep the current context in plain variables. On an opener, push the current context and reset. On a closer, pop and merge.

decode_string.py

def decode_string(s):
    stack = []            # suspended (text_before, repeat_count) pairs
    current = ""          # text being built at this nesting level
    count = 0             # digits seen just before the next '['
 
    for ch in s:
        if ch.isdigit():
            count = count * 10 + int(ch)     # build multi-digit numbers
        elif ch == "[":
            stack.append((current, count))   # suspend the outer level
            current, count = "", 0           # start a fresh inner level
        elif ch == "]":
            prev, k = stack.pop()            # resume the outer level
            current = prev + current * k     # merge the finished inner one
        else:
            current += ch
 
    return current
 
 
print(decode_string("3[a2[c]]"))   # accaccacc

The count = count * 10 + int(ch) line matters: "10[a]" must repeat ten times, not once then zero times. Treating each digit character as a complete number is a real and common bug.

	Time	Space
Bracket matching	$O(n)$	$O(n)$ worst case (all openers)
RPN evaluation	$O(n)$	$O(n)$
Nested decoding	$O(\text{output length})$	$O(\text{output length})$

Visual intuition

Stack depth is nesting depth — that equivalence is the whole of bracket matching:

stackStack depth IS nesting depthLC 20

(0[1]2{3}4)5

stack (top)

empty

bottom

open0

1def is_valid(s):2    pairs = {')': '(', ']': '[', '}': '{'}3    stack = []4    for ch in s:5        if ch not in pairs:6            stack.append(ch)          # an opener7        elif not stack or stack.pop() != pairs[ch]:8            return False              # mismatch, or nothing to close9    return not stack                  # leftovers mean unclosed

setupThe stack holds openers that have not been closed yet. Its depth is the current nesting level, and the top is always the one that must close next — which is exactly what "properly nested" means.

Play‹›1/8⟲

Note the two failure modes the stack catches that a counter cannot: a closer arriving when nothing is open, and crossed nesting like ([)] where the counts balance but the order does not.

stackPostfix needs no precedence rules at allLC 150

2011+233*4

stack (top)

empty

bottom

depth0

1def eval_rpn(tokens):2    stack = []3    for tok in tokens:4        if tok in '+-*/':5            b = stack.pop()          # SECOND operand pops first6            a = stack.pop()7            stack.append(apply(a, tok, b))8        else:9            stack.append(int(tok))10    return stack[0]

setupPostfix notation needs no parentheses and no precedence rules, because the order is already unambiguous. A single stack evaluates it in one pass — which is why compilers convert infix to postfix before evaluating.

Play‹›1/7⟲

Watch the operand order on each operator: the SECOND operand pops first. Getting that backwards is invisible for + and *, and silently wrong for − and /.

The variant map

Variant	What the stack holds	Canonical problem
Matched pairs	The unclosed openers	20 Valid Parentheses
Count repairs needed	Just a counter plus one for unmatched closers	921 Minimum Add to Make Parentheses Valid
Postfix evaluation	Operands awaiting an operator	150 Evaluate RPN
Infix with precedence	Running value + the last operator, or two stacks	227 · 224
Nested decoding	Suspended (context, multiplier)	394 Decode String
Adjacent cancellation	Characters, popping on a match	1047 Remove All Adjacent Duplicates
Path resolution	Resolved directory names; .. pops	71 Simplify Path

Infix arithmetic without a precedence table

For LC 227 (+ - * /, no parentheses) you do not need a precedence table. Scan left to right keeping a stack of terms: on + push the number, on - push its negative, and on * or / pop the top and push the combined result immediately. Higher-precedence operators are applied eagerly, lower-precedence ones are deferred to a final sum(stack). For LC 224 (parentheses, + -), push the running total and sign on ( and restore on ) — the same save-and-restore idea as LC 394.

Practice — real LeetCode problems

LC 20 — Valid Parentheses · Easy

Problem. Given a string containing only (, ), {, }, [, ], determine whether the brackets are correctly closed, in the correct order, and each closer matches its opener type.

Constraints. 1 <= len(s) <= 10^4.

Examples. "()" gives True · "()[]{}" gives True · "(]" gives False · "([)]" gives False · "([])" gives True

pch.exerciseTag pch.exerciseTitle

Editorial — approach, complexity, follow-ups

Push openers; on a closer, the top of the stack must be its matching opener. Popping consumes the match. An empty stack at the end means every opener was closed.

Time $O(n)$. Space $O(n)$ — worst case "(((((".

"([)]" is why this is a stack problem rather than a counting problem: the counts of (, ), [, ] are all balanced, yet the nesting is wrong. "]" tests the empty-stack guard, and "" should be True (vacuously balanced) — though note LeetCode’s own constraints say len(s) >= 1, so the empty string is included here to test your guard rather than because the judge will send it.

Follow-ups you should expect: “Only one bracket type?” — an integer counter suffices; it must never go negative and must end at zero. “Return the index of the first invalid character?” — return i at the point of failure. “Minimum insertions to make it valid (921)?” — count unmatched closers as you scan plus whatever openers remain. “Longest valid substring (32)?” — a genuinely harder problem: push indices and measure gaps, or use DP.

LC 150 — Evaluate Reverse Polish Notation · Medium

Problem. Evaluate an arithmetic expression in Reverse Polish Notation. Valid operators are +, -, *, /. Division between two integers truncates toward zero.

Constraints. 1 <= len(tokens) <= 10^4. The expression is always valid, and division by zero never occurs.

Examples. ["2","1","+","3","*"] gives 9 · ["4","13","5","/","+"] gives 6 · ["10","6","9","3","+","-11","*","/","*","17","+","5","+"] gives 22

pch.exerciseTag pch.exerciseTitle

Editorial — approach, complexity, follow-ups

Postfix notation encodes precedence in the token order, so evaluation is a single pass with no lookahead: operands accumulate on the stack, and each operator consumes exactly the top two. Because the input is guaranteed valid, the stack holds exactly one value at the end.

Time $O(n)$. Space $O(n)$.

int(a / b) versus a // b

["7","-3","/"] must give -2. Python’s // floors: 7 // -3 == -3. int(7 / -3) truncates toward zero and gives -2, which is what the problem specifies.

For very large operands, a / b goes through a float and could in principle lose precision — the safer integer-only form is abs(a) // abs(b) with the sign of a * b reapplied. At this problem’s constraints int(a / b) is fine, but knowing why it could bite is the better answer.

Also note that a token like "-11" is a negative operand, not a minus operator — checking membership in the operator set (rather than t.isdigit(), which is False for "-11") handles it correctly. Using isdigit() here is a classic bug.

Follow-ups you should expect: “Evaluate infix instead?” — LC 227/224, or convert infix to postfix with the shunting-yard algorithm and reuse this code. “Prefix (Polish) notation?” — scan right to left with the pop order swapped. “Add ^ or unary minus?” — extend the operator set; unary operators pop only one value.

LC 394 — Decode String · Medium

Problem. Given an encoded string where k[encoded] means the bracketed substring repeats exactly k times, return the decoded string. k is guaranteed to be a positive integer, and the input is always valid.

Constraints. 1 <= len(s) <= 30, 1 <= k <= 300. Brackets may nest.

Examples. "3[a]2[bc]" gives "aaabcbc" · "3[a2[c]]" gives "accaccacc" · "2[abc]3[cd]ef" gives "abcabccdcdcdef"

pch.exerciseTag pch.exerciseTitle

Editorial — approach, complexity, follow-ups

The insight is to keep the current nesting level in ordinary variables and push only the suspended outer levels. On [ you are descending, so save what you had and start clean. On ] the inner level is complete, so pop the parent and splice the repeated result into it.

Time $O(\text{length of the output})$ — you cannot beat that, since you must produce every character. Space $O(\text{output})$.

Two details that break naive attempts:

• Multi-digit counts. "10[a]" must give ten as. count = count * 10 + int(ch) accumulates digits; treating each digit as its own number gives "a" repeated once then zero times.
• Text before a bracket. "abc3[cd]xyz" shows that current may already hold characters when [ arrives, which is exactly why the pushed tuple stores current alongside the count, and why the merge is prev + current * k rather than just current * k.

The recursive solution is equally valid and arguably more readable: parse a number, recurse on the bracketed segment, repeat and continue. The stack version is the iterative form of that same recursion, which is why “now do it without recursion” is such a common follow-up.

Follow-ups you should expect: “Do it recursively” (or iteratively, if you started recursive) — be ready to convert either way. “What if k could be zero?” — the merge still works and drops the segment. “Encode rather than decode?” — a different, harder problem (run-length compression with nesting). “What if the input might be malformed?” — add the LC 20 guards: check the stack is non-empty before popping and empty at the end.

LeetCode problem set

Generated from the problem database, so each entry carries its sheet membership and reported companies. Tick them off as you go — progress is saved in this browser, and the Export button writes it to a file you can keep.

LC 32 is not really a bracket-matching problem

Longest Valid Parentheses looks like LC 20 but resists the same approach: you need the length of the longest valid run, not a yes/no answer. The trick is to push indices and seed the stack with -1 as a sentinel “last unmatched position”. When you pop on a ), the current valid length is i - stack[-1]. Alternatively there is a neat $O(1)$-space two-pass scan (left to right, then right to left, counting). Worth studying separately — it is a favourite for senior loops.

10 problems

2 easy6 medium2 hard

Work down the ladder. Tick each problem off as you go — progress is saved in this browser, and the Export button in the filter bar writes it to a file you can keep.

AllEasyMediumHard

Unsolved onlyExportImportReset

• ○20Valid ParentheseseasyThe base template; guard the empty stack and the leftoversNeetCode 150Blind 75LeetCode Top Interview 150amazongooglemetamicrosoftbloomberg
• ○1047Remove All Adjacent Duplicates In StringeasyPush, and pop instead when the incoming char equals the top
• ○71Simplify PathmediumSplit on `/`; `..` pops, `.` and empty segments are skippedLeetCode Top Interview 150
• ○150Evaluate Reverse Polish NotationmediumPop order, and truncation toward zeroNeetCode 150LeetCode Top Interview 150
• ○227Basic Calculator IImediumApply `*` and `/` eagerly, defer `+` and `-` to a final sum
• ○394Decode StringmediumSave-and-restore; multi-digit counts
• ○678Valid Parenthesis StringmediumNeetCode 150
• ○921Minimum Add to Make Parentheses ValidmediumA counter is enough -- count unmatched closers plus leftover openers
• ○32Longest Valid ParentheseshardPush **indices**, not characters, and measure the gap to the last unmatched one
• ○224Basic CalculatorhardParentheses: push the running total **and** the sign, restore on `)`LeetCode Top Interview 150

Dry run

LC 394 Decode String on "3[a2[c]]" — the nested case that separates a working solution from one that only handles a single level.

ch	action	num	cur	stack (bottom → top)
3	accumulate digit	3	""	—
[	push (cur, num), reset both	0	""	[("", 3)]
a	append to cur	0	"a"	[("", 3)]
2	accumulate digit	2	"a"	[("", 3)]
[	push (cur, num), reset both	0	""	[("", 3), ("a", 2)]
c	append to cur	0	"c"	[("", 3), ("a", 2)]
]	pop ("a", 2); cur = "a" + "c"*2	0	"acc"	[("", 3)]
]	pop ("", 3); cur = "" + "acc"*3	0	"accaccacc"	[]

Answer "accaccacc".

Three details that are the whole problem:

• The stack stores a pair. Pushing only the multiplier loses the text built before the bracket, and "a2[c]" comes back as "cc" instead of "acc".
• Digits must accumulate across characters. num = num * 10 + int(ch), not num = int(ch) — otherwise "12[a]" repeats twice, not twelve times.
• Both num and cur reset on [. They belong to the level being entered, and forgetting to reset leaks state downward into the nested level.

Compare with LC 224 Basic Calculator on "1+(2-(3+4))", where the stack holds a running result and a sign instead of a string and a count. Same shape, different payload — that shape is the pattern.

Complexity

Problem shape	Time	Space
Bracket matching (LC 20)	$O(n)$	$O(n)$ — the stack, at worst all openers
Expression evaluation (LC 150, 224, 227)	$O(n)$	$O(n)$
Decode String (LC 394)	$O(\text{output length})$	$O(\text{output length})$

Two things worth saying out loud:

• Space is genuinely $O(n)$, not $O(1)$. A fully nested input like "((((((..." puts every character on the stack. If asked to reduce it: for balance checking only a counter suffices, but a counter cannot detect crossed nesting like "([)]", so it answers a weaker question.
• Decode String is measured against its output, not its input. "10[10[a]]" is nine characters and expands to a hundred, so quoting $O(n)$ in the input length is wrong — and being precise about which $n$ you mean is exactly the kind of care these rounds are looking for.

Interview follow-ups

They ask	What they’re checking	The answer
“Could you use a counter instead of a stack?”	Whether you know the boundary	Only with a single bracket type; multiple types need to know what was opened, which "([)]" demonstrates
“Why int(a / b) and not a // b?”	Reading the spec	The problem truncates toward zero; Python’s // floors toward negative infinity, so they differ on negative results
“Now do it iteratively / recursively”	Flexibility	A stack is the explicit form of the call stack — the save-and-restore template is the mechanical conversion
“What’s the space complexity?”	Precision	$O(n)$ worst case for matching (all openers); $O(\text{output})$ for decoding, which can exceed the input
“Handle malformed input”	Defensiveness	Guard every pop() with a non-empty check, and verify the stack is empty at the end
“Add precedence / parentheses to the calculator”	Depth	Apply higher-precedence ops eagerly on a stack of terms; for parentheses, push and restore the running total and sign

Edge-case checklist

• Closer with an empty stack — "]" must return False, not raise IndexError.
• Unclosed opener at the end — "("; the final emptiness check is the only thing that catches it.
• Correct counts, wrong nesting — "([)]"; the reason a counter is insufficient.
• Empty input — decide what it means and be consistent.
• Negative operands in RPN — "-11" is a number; isdigit() returns False for it, so test membership in the operator set instead.
• Negative division in RPN — ["7","-3","/"] gives -2, not -3.
• Multi-digit repeat counts — "10[a]" gives ten characters.
• Text before and after a bracket group — "abc3[cd]xyz"; the merge must preserve prev.
• Deep nesting — a recursive solution can hit Python’s recursion limit; the iterative stack version cannot.

Self-check

pch.quizTag Stack parsing — self-check

1. A counter of open brackets is simpler than a stack. Why is it not sufficient for LC 20?

   A It is sufficient — the stack is an over-engineering B A counter cannot detect crossed nesting like ([)], where the counts balance but the order is invalid C Counters cannot go negative D It would be O(n²)
   pch.quizShowAnswer

   B — A counter cannot detect crossed nesting like ([)], where the counts balance but the order is invalid — A counter answers the weaker question 'do the counts balance'. The stack answers 'is the nesting well-formed', because its top is always the bracket that must close next. With one bracket type a counter genuinely is enough — worth saying if asked.

2. In Decode String, what must be pushed onto the stack at each `[`?

   A Just the repeat count B Both the string built so far and the repeat count, as a pair C Just the string built so far D The index of the bracket
   pch.quizShowAnswer

   B — Both the string built so far and the repeat count, as a pair — Pushing only the count loses the prefix: 'a2[c]' returns 'cc' rather than 'acc'. Pushing only the string loses the multiplier. The pair is what lets the pop reconstruct prefix + repeated middle.

3. Why is `num = num * 10 + int(ch)` rather than `num = int(ch)`?

   A For speed B Because multi-digit counts arrive one character at a time, so '12[a]' must repeat twelve times, not two C To handle negative numbers D They are equivalent
   pch.quizShowAnswer

   B — Because multi-digit counts arrive one character at a time, so '12[a]' must repeat twelve times, not two — A single-digit test suite hides this completely. It is the most common reason a Decode String solution passes the samples and fails the hidden tests.

4. In Evaluate Reverse Polish Notation, which operand pops first?

   A The first operand, a B The second operand, b — so the expression is a op b, not b op a C Either, since the operators are commutative D It depends on the operator
   pch.quizShowAnswer

   B — The second operand, b — so the expression is a op b, not b op a — Stacks are LIFO, so the operand pushed last comes off first, and that is the right-hand operand. The mistake is invisible for + and *, and silently wrong for − and /.

5. What is the space complexity of Decode String, and in terms of what?

   A O(1) B O(n) in the input length C O(output length) — '10[10[a]]' is nine characters and expands to a hundred D O(log n)
   pch.quizShowAnswer

   C — O(output length) — '10[10[a]]' is nine characters and expands to a hundred — Quoting O(n) without saying which n is wrong here. Being explicit that the bound is in the output length, and giving the expanding example, is the kind of precision these rounds score.

Recall card

• Cue — nested structure in a string: brackets, parentheses, an expression, a path to simplify, a string to decode.
• Invariant — the stack holds the enclosing context, one entry per level currently open. Its depth is the nesting depth.
• Template — scan left to right; on an opener push the current context and reset it; on a closer pop and combine the popped context with what was built inside.
• What to push — a pair, almost always: (text so far, repeat count) for Decode String; (running result, sign) for Basic Calculator. Pushing one half is the standard bug.
• Complexity — $O(n)$ time, $O(n)$ space. For Decode String, $O(\text{output})$ — say which $n$ you mean.
• Remember — accumulate multi-digit numbers with num*10 + d; reset the level’s state on the opener; in RPN the second operand pops first.

Recap

• A stack is the right tool whenever the most recent open thing must be resolved first — brackets, nesting, suspended context.
• Matched pairs: push openers, match on closers, and check both failure modes (empty stack mid-scan, leftovers at the end).
• Postfix needs no precedence handling; just watch the pop order and truncate division toward zero.
• Nested decoding uses save-and-restore: push (context, multiplier) on the way in, pop and merge on the way out. Accumulate multi-digit numbers with count * 10 + digit.
• This is stack-as-suspended-context; stack-as-sorted-candidates is Monotonic Stack.
• Any recursive descent over nested input can be rewritten with this template — which is exactly what “now do it iteratively” is asking for.

Next: Frequency and Anagram Counting — the Counter-based patterns behind anagram grouping and character-multiset comparison.