Evaluate Reverse Polish Notation

Problem

You get an arithmetic expression as a list of tokens in Reverse Polish Notation (postfix): each token is either an integer (possibly negative) or one of the operators +, -, *, /. In RPN an operator comes after its two operands and applies to the two most recent unconsumed values — so there are no parentheses and no precedence rules.

Evaluate the expression and return the result as an integer. Division between integers truncates toward zero (so 6 / -132 is 0, and -7 / 2 is -3, not -4). The input is always a valid expression, and no division by zero occurs; every intermediate value fits in a 32-bit integer.

Examples

• ["2", "1", "+", "3", "*"] → 9 — means (2 + 1) * 3.
• ["4", "13", "5", "/", "+"] → 6 — means 4 + (13 / 5) and 13 / 5 truncates to 2.
• ["10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"] → 22 — ((10 * (6 / ((9 + 3) * -11))) + 17) + 5; note 6 / -132 truncates toward zero to 0.

Constraints

• 1 <= tokens.length <= 10^4
• Each token is an operator or an integer in [-200, 200]

With 10^4 tokens, a rescan-and-splice simulation is O(n^2) and too slow. The expected solution is a single O(n) pass.

Think about it first

TL;DR

Single pass with an operand stack: push numbers, pop-apply-push on operators — O(n) time, O(n) space.

Approach 1 — Brute force (rescan and splice)

Simulate the definition directly: find the leftmost operator, apply it to the two numbers just before it, splice the three tokens into one result token, and rescan from the start. Repeat until one token remains.

def evalRPN(tokens: list[str]) -> int:
    ops = {"+", "-", "*", "/"}
    toks = list(tokens)
    while len(toks) > 1:
        for i, t in enumerate(toks):
            if t in ops:
                a = int(toks[i - 2])
                b = int(toks[i - 1])
                if t == "+":
                    val = a + b
                elif t == "-":
                    val = a - b
                elif t == "*":
                    val = a * b
                else:
                    val = int(a / b)        # truncates toward zero
                toks[i - 2 : i + 1] = [str(val)]
                break
    return int(toks[0])

Complexity: O(n^2) time — up to n/2 operators, each found by an O(n) rescan followed by an O(n) list splice; O(n) space.

Why the constraints kill it: with n = 10^4, an expression whose operators sit near the end forces ~10^8 token touches — versus one linear pass.

Approach 2 — Operand stack

The insight: an operator always consumes the two most recent unconsumed values, which are exactly the top two of a stack of results so far. Push numbers; on each operator, pop the right operand, then the left, apply, and push the result. No rescanning, no splicing.

def evalRPN(tokens: list[str]) -> int:
    stack: list[int] = []
    for t in tokens:
        if t not in {"+", "-", "*", "/"}:
            stack.append(int(t))
            continue
        b = stack.pop()          # right operand (pushed last)
        a = stack.pop()          # left operand
        if t == "+":
            stack.append(a + b)
        elif t == "-":
            stack.append(a - b)
        elif t == "*":
            stack.append(a * b)
        else:
            stack.append(int(a / b))   # int() truncates toward zero
    return stack[0]

Walkthrough on ["4", "13", "5", "/", "+"]:

Answer: 6.

Complexity: O(n) time — each token is processed once, and each number is pushed and popped at most once. O(n) space for the stack (worst case: all numbers first).

Approach 3 — Recursion from the right

The insight: read the token list backwards and it becomes prefix-like. The last token is the root of the expression tree, and its two subtrees sit before it, right subtree first. A recursive evaluator that pops from the end reconstructs the tree top-down, using the call stack instead of an explicit one.

For ["2", "1", "+", "3", "*"], the expression tree is (2 + 1) * 3:

graph TD
    M["*"] --> P["+"]
    M --> T3["3"]
    P --> T2["2"]
    P --> T1["1"]

Popping from the end visits * (root), then its right child 3, then its left subtree rooted at +.

def evalRPN(tokens: list[str]) -> int:
    def evaluate() -> int:
        t = tokens.pop()
        if t not in {"+", "-", "*", "/"}:
            return int(t)
        right = evaluate()       # right operand is nearer the end
        left = evaluate()
        if t == "+":
            return left + right
        if t == "-":
            return left - right
        if t == "*":
            return left * right
        return int(left / right)

    return evaluate()

Walkthrough on ["2", "1", "+", "3", "*"]: evaluate pops * (root), recurses for the right operand and pops 3, then recurses for the left and pops +, which in turn resolves its right (1) and left (2) to give 3; finally 3 * 3 = 9.

Complexity: O(n) time, O(n) space for recursion depth (worst case a left-deep expression). Same asymptotics as the stack — it is the same stack, implicit.

Common pitfalls

• Operand order: the first pop is the right operand. ["3", "4", "-"] is 3 - 4 = -1; swapping gives 1. Subtraction and division are the tests that catch this.
• Python division: 13 // -5 is -3 (floor) but the problem wants -2 (truncation). Use int(a / b) — safe here since values fit comfortably in a float — or math.trunc, never bare //.
• Detecting numbers with str.isdigit(): it returns False for "-11"; test membership in the operator set (or use lstrip("-").isdigit()).
• Returning stack.pop() inside the loop: the answer is the lone survivor after all tokens are consumed.

Pattern takeaway

Postfix evaluation is a clean example of the stack pattern: values wait on the stack until an operator combines the top two into one. The same push-values, fold-on-operator loop underlies calculator problems, expression-tree building, and bytecode evaluation. The recursive variant shows that any explicit stack can be replaced by the call stack.