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]

10^4 tokens sinks the rescan-and-splice simulation (O(n^2)); 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.

class Solution:
    def evalRPN(self, 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: RPN is designed for a stack — an operator always consumes the two most recent unconsumed values, which is exactly the top two of a stack of results-so-far. So numbers get pushed; each operator pops its right operand, then its left, and pushes the folded result. No rescanning, no splicing.

class Solution:
    def evalRPN(self, 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.

class Solution:
    def evalRPN(self, 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 the purest form of the stack pattern: values wait on the stack until an operator retires the top two into one. The same push-values / fold-on-operator loop underlies calculator problems, expression-tree building, and compilers’ actual bytecode evaluation — and the recursive variant is a reminder that any explicit stack can trade places with the call stack.