Whenever the most recently opened thing must be closed first, you are looking at a stack. Brackets, nested arithmetic, [3[a2[c]]][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

Template 1 — matched pairs

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

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

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.

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)

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)

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.

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

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)count = count * 10 + int(ch) line matters: "10[a]""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.

The variant map

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^41 <= len(s) <= 10^4.

Examples. "()""()" gives TrueTrue · "()[]{}""()[]{}" gives TrueTrue · "(]""(]" gives FalseFalse · "([)]""([)]" gives FalseFalse · "([])""([])" gives TrueTrue

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^41 <= len(tokens) <= 10^4. The expression is always valid, and division by zero never occurs.

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

LC 394 — Decode String · Medium

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

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

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

LeetCode problem set

Interview follow-ups

Edge-case checklist

• Closer with an empty stack — "]""]" must return FalseFalse, not raise IndexErrorIndexError.
• 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""-11" is a number; isdigit()isdigit() returns FalseFalse for it, so test membership in the operator set instead.
• Negative division in RPN — ["7","-3","/"]["7","-3","/"] gives -2-2, not -3-3.
• Multi-digit repeat counts — "10[a]""10[a]" gives ten characters.
• Text before and after a bracket group — "abc3[cd]xyz""abc3[cd]xyz"; the merge must preserve prevprev.
• Deep nesting — a recursive solution can hit Python’s recursion limit; the iterative stack version cannot.

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)(context, multiplier) on the way in, pop and merge on the way out. Accumulate multi-digit numbers with count * 10 + digitcount * 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 CounterCounter-based patterns behind anagram grouping and character-multiset comparison.