Expression Evaluation: RPN, Calculators and Parsing

"Evaluate this expression string" is a family of interview favorites: reverse Polish notation, the basic calculator with + - * /, the version with parentheses and unary minus, and full expression parsing. All of them are solved with stacks or with a small recursive parser that encodes operator precedence. The key ideas are short; the difficulty is in the details (operand order, unary minus, associativity, integer division), so a clean template pays off.

Intuition

• Expression trees. Every expression is a tree: operators are internal nodes, numbers are leaves. A post-order traversal gives reverse Polish notation (RPN), for example 3 4 + 2 * for (3 + 4) * 2. RPN needs no parentheses and no precedence rules, and a single stack evaluates it: push numbers; on an operator pop the right operand, then the left one, and push the result.
• Infix with precedence: two stacks. The shunting-yard method scans left to right with a stack of numbers and a stack of pending operators. Before pushing an operator, apply every pending operator that must happen first: those with higher precedence, and those with equal precedence if the new operator is left-associative (a - b - c means (a - b) - c). A right-associative operator such as power (2 ^ 3 ^ 2 = 2 ^ 9) waits instead. ( is pushed as a barrier and ) applies operators back to it.
• Unary minus is detected by position: a - is unary at the start, after (, or after another operator. Treat it as its own operator with higher precedence than * and /.
• Recursive descent. Write one function per precedence level: an expression is a sum of terms, a term is a product of factors, and a factor is a number, a parenthesized expression, or a signed factor. Each function consumes tokens and returns a value. This mirrors the grammar directly and is often the least error-prone option in an interview.
• Only + - * /, no parentheses: one stack suffices. Push +num or -num for additive terms and immediately combine * and / with the top of the stack; the answer is the sum of the stack.

When to use it in interviews / OAs

• "Evaluate reverse Polish notation": one stack.
• "Basic calculator" with + - * / and spaces: the one-stack method.
• "Basic calculator" with parentheses and unary minus, possibly all four operators: two stacks or recursive descent.
• Parsing other small grammars with nesting: boolean expressions, nested lists, chemical formulas (count atoms), decoding strings like 3[a2[c]], Lisp-like expressions. The same "stack per nesting level" or "recursive function per rule" structure applies.
• Building an expression tree from a string, or converting infix to postfix.

Template

Most of these problems want integer division that truncates toward zero (as in C and Java), while Python's // rounds down:

import operator


def div_trunc(a: int, b: int) -> int:
    """Integer division rounding toward zero: -7 / 2 == -3."""
    q = abs(a) // abs(b)
    return q if (a >= 0) == (b >= 0) else -q


OPS = {"+": operator.add, "-": operator.sub, "*": operator.mul, "/": div_trunc}

Reverse Polish notation

def eval_rpn(tokens: list[str]) -> int:
    stack: list[int] = []
    for tok in tokens:
        if tok in OPS:
            b = stack.pop()  # the right operand is on top
            a = stack.pop()
            stack.append(OPS[tok](a, b))
        else:
            stack.append(int(tok))  # handles negative literals such as "-11"
    return stack[-1]

One stack for + - * / without parentheses

def calculate_no_parens(s: str) -> int:
    stack: list[int] = []
    num, op = 0, "+"  # op is the operator in front of num
    for i, ch in enumerate(s):
        if ch.isdigit():
            num = num * 10 + int(ch)
        if (not ch.isdigit() and ch != " ") or i == len(s) - 1:
            if op == "+":
                stack.append(num)
            elif op == "-":
                stack.append(-num)
            elif op == "*":
                stack.append(stack.pop() * num)
            else:
                stack.append(div_trunc(stack.pop(), num))
            op, num = ch, 0
    return sum(stack)

Two stacks: parentheses, unary minus, right associativity

PREC = {"+": 1, "-": 1, "*": 2, "/": 2, "neg": 3, "^": 4}
RIGHT_ASSOC = {"neg", "^"}


def evaluate(s: str) -> int:
    nums: list[int] = []
    ops: list[str] = []

    def apply(op: str) -> None:
        if op == "neg":
            nums.append(-nums.pop())
            return
        b, a = nums.pop(), nums.pop()
        nums.append(a ** b if op == "^" else OPS[op](a, b))

    i, expect_operand = 0, True  # True at the start, after "(" and after an operator
    while i < len(s):
        ch = s[i]
        if ch == " ":
            i += 1
        elif ch.isdigit():
            j = i
            while j < len(s) and s[j].isdigit():
                j += 1
            nums.append(int(s[i:j]))
            i, expect_operand = j, False
        elif ch == "(":
            ops.append(ch)
            i, expect_operand = i + 1, True
        elif ch == ")":
            while ops[-1] != "(":
                apply(ops.pop())
            ops.pop()  # discard "("
            i, expect_operand = i + 1, False
        else:
            if expect_operand and ch in "+-":
                if ch == "-":
                    ops.append("neg")  # unary minus; unary plus is simply ignored
                i += 1
                continue
            while ops and ops[-1] != "(" and (
                PREC[ops[-1]] > PREC[ch] or (PREC[ops[-1]] == PREC[ch] and ch not in RIGHT_ASSOC)
            ):
                apply(ops.pop())  # pending operators that bind at least as tightly go first
            ops.append(ch)
            i, expect_operand = i + 1, True
    while ops:
        apply(ops.pop())
    return nums[-1]

With "neg" ranked below ^, -2^2 is -(2^2) = -4, the usual mathematical convention.

Recursive descent

One function per precedence level; pos points at the next token:

import re


def evaluate_rd(s: str) -> int:
    """expr := term (("+" | "-") term)*
    term := factor (("*" | "/") factor)*
    factor := ("+" | "-") factor | number | "(" expr ")" """
    tokens = re.findall(r"\d+|[-+*/()]", s)
    pos = 0

    def peek() -> str | None:
        return tokens[pos] if pos < len(tokens) else None

    def take() -> str:
        nonlocal pos
        pos += 1
        return tokens[pos - 1]

    def expr() -> int:
        value = term()
        while peek() in ("+", "-"):
            op = take()
            value = OPS[op](value, term())
        return value

    def term() -> int:
        value = factor()
        while peek() in ("*", "/"):
            op = take()
            value = OPS[op](value, factor())
        return value

    def factor() -> int:
        tok = take()
        if tok == "-":
            return -factor()
        if tok == "+":
            return factor()
        if tok == "(":
            value = expr()
            take()  # the matching ")"
            return value
        return int(tok)

    return expr()

The loops in expr and term make + - * / left-associative; a right-associative operator would recurse instead of looping.

Complexity

All of the methods above run in O(n) time for an expression of length n: every token is pushed and popped at most once, or consumed once by the parser. Space is O(n) for the stacks or the recursion depth, which grows with the nesting depth of parentheses.

Common pitfalls

• Operand order. For -, / and ^, the first value popped is the right operand.
• Python's // floors. -7 // 2 == -4; most calculator problems expect -3. Avoid int(a / b) for large integers because it goes through floating point.
• Unary minus. Decide by context (start, after (, after an operator); a leading - or -(...) breaks naive code that always pops two operands.
• Multi-digit numbers. Accumulate digits until a non-digit, and flush the last number at the end of the string.
• Equal precedence. Pop on >= for left-associative operators; for right-associative ones pop only on >.
• Spaces everywhere, including between a unary minus and its operand.
• Deep nesting in Python. Recursive descent recurses once per nesting level; inputs with thousands of nested parentheses need the stack version.

Interview variations

• Evaluate reverse Polish notation: the one-stack evaluator.
• Basic calculator I (+, -, parentheses, unary minus): a simpler stack trick also works, pushing the running result and the sign when entering (.
• Basic calculator II (+ - * /, no parentheses): the one-stack method.
• Basic calculator III (everything): two stacks or recursive descent.
• Build a binary expression tree from infix: run the two-stack method but push tree nodes instead of numbers.
• Parse a boolean expression, decode string, number of atoms, mini parser for nested lists: stack per nesting level or a recursive function per grammar rule.
• Different ways to add parentheses: not parsing but divide and conquer over operator positions.