Expression Parsing · bigonotes

Calculators, nested strings and file paths all share one problem: you read them left to right, but you can't finish an operation until you've read what comes after it. The half-finished work has to wait somewhere, and a stack is the natural place. This note covers Reverse Polish Notation, calculators with precedence, nested repeats like 3[a2[c]], and Unix paths.

The idea#

The stack holds work that is waiting for more input. Each token either adds pending work or completes the newest pending work.

Input shape	What waits on the stack	When it resolves
Postfix tokens	operands	an operator pops two and pushes the result
Infix with precedence	signed terms	high-precedence operators combine with the top at once; low ones wait for a final sum
Nested brackets	the outer state for each open bracket	the closing bracket pops it and merges the inner result
Paths and commands	names	a canceling token pops one

Why a stack? The newest pending item is always the first one that can complete. That is last in, first out, which is exactly what a stack gives you.

You can also solve these with recursion. It's the same idea with the call stack doing the pushing: each opening bracket makes a recursive call, and each closing bracket returns its result to the caller.

How to spot it#

The input is text you evaluate token by token. Look for these signals.

"Evaluate the expression", "implement a basic calculator".
Tokens in postfix order (operands before their operator).
Nested brackets that change how the inside is interpreted (k[...], parentheses with a sign).
A path or command list where some tokens cancel earlier ones (.., "undo").

Template#

Read one token at a time. Decide whether it adds pending work or completes it.

stack = empty
current = empty                      # number or string being built
for each token in input:
    if token continues current:      # e.g. another digit
        extend current
    elif token opens new work:       # operand, "[", directory name
        push current or token
        reset current
    elif token completes work:       # operator, "]", ".."
        pop what it needs
        combine and push or keep the result
finish any pending work
return the result from the stack

Each token is pushed and popped at most once, so the scan is $O(n)$ .

Precedence without parentheses#

The template's "completes work" step is trickiest when operators have different precedence. For + - * / without parentheses, read a number, then apply the operator that came before it. Start as if the string began with +. The table traces 3+2*2.

Token read	Operator applied	Stack after
`3` then `+`	`+`	`[3]`
`2` then `*`	`+`	`[3, 2]`
`2` (end)	`*`	`[3, 4]`
	sum	7

Pitfalls#

These bugs give wrong values on edge inputs.

Operand order. With two pops, the first pop is the right operand. Order matters for - and /.
Floor vs truncation. Python's // floors toward negative infinity, so -7 // 2 is -4. Most of these problems want truncation toward zero, int(b / a), which gives -3.
Multi-digit numbers. Accumulate num = num * 10 + digit; never treat each digit as its own token.
The last token. Apply any pending work at the last character, even if it's a space, or the final number is lost.
Popping an empty stack. A canceling token at the start (like .. at the root) must be a no-op.

Worth exploring: once precedence makes sense, try Basic Calculator (LC 224), with +, - and parentheses. The usual approach keeps a stack of the sign in front of each open parenthesis.

Problems in this pattern#

These problems use this pattern. Solve them before you open the hints below.

Hints#

Open a hint only after you have tried the problem for a while.

Hint: Evaluate Reverse Polish Notation

Push numbers. On an operator, pop a first, then b, and push b op a: in ["4", "2", "-"] the answer is 4 - 2. For division, int(b / a) truncates toward zero, which is what the problem wants. Don't use //.

Hint: Basic Calculator II

Keep num and the previous operator op, starting with op = "+". When a number is complete (at an operator or the last character), + pushes num, - pushes -num, and * or / pop the top and push the combined value. The answer is the sum of the stack.

Hint: Decode String

On [, push (current_string, count) and start a fresh string. On ], pop (prev, k) and set current = prev + current * k. Counts can have several digits, so build them as count * 10 + digit.

Hint: Decode String: recursive version

A helper reads characters until it sees ]. On [ it calls itself for the inner part and multiplies the result. The call stack remembers the outer string while the inner one is built.

Hint: Simplify Path

Split on /. Skip empty parts and .. On .., pop if the stack is non-empty; otherwise push the name. Join the stack with / and put one / in front.

Hint: Crawler Log Folder

Treat the logs like a path: ../ pops a level (never below the root), ./ does nothing, anything else pushes. The answer is the final depth, so a counter can stand in for the stack.

Key takeaways#

The stack holds work that can't finish until more input arrives.
Apply each operator when the number after it is complete.
Higher-precedence operators combine with the top immediately; lower ones wait.
Truncate toward zero with int(b / a), not //.
Recursion is a stack too; pick whichever reads more clearly.

Core idea#

You cannot finish an operation until you read what comes after it. Put the half-finished work on a stack, and resolve it when the missing input arrives.

Key points#

The stack holds work that waits for more input.
Apply each operator when the number after it is complete.
Higher-precedence operators (*, /) combine with the top at once. + and - push a signed term and wait for the final sum.
Recursion is the same idea. The call stack does the pushing: [ makes a call, ] returns.
Spot it: "evaluate the expression", postfix tokens, nested brackets like k[...], paths with ...

What waits on the stack#

Problem	Stack holds	Resolves when
Reverse Polish Notation	operands	an operator pops two, pushes `b op a`
Basic Calculator II	signed terms	`*` and `/` combine with the top; sum at the end
Decode String	`(string so far, count)` per `[`	`]` pops: `prev + current * k`
Simplify Path	directory names	`..` pops one; skip empty parts and `.`

Template#

stack = empty
num = 0, op = "+"                # as if the input began with "+"
for each character ch:
    if ch is a digit: num = num * 10 + digit
    if ch is an operator or the last character:
        if op is "+": push num
        if op is "-": push -num
        if op is "*" or "/": pop top, push top op num
                                 # "/" truncates toward 0
        num = 0, op = ch
return sum of stack

Pitfalls#

Operand order in RPN. The first pop is the right operand a; push b op a.
Floor vs truncation. // floors, so -7 // 2 is -4. Use int(b / a).
Multi-digit numbers. Accumulate num = num * 10 + digit.
The last number. Apply the pending operator at the last character, even a space.
.. at the root. Popping an empty stack must be a no-op.

Say it in an interview#

"The stack holds work that cannot finish until more input arrives."
"Multiply and divide combine with the top at once. Plus and minus wait for the final sum."