Evaluate Reverse Polish Notation

In normal notation, (3 + 4) × 2 - 7 needs parentheses and precedence rules to say what happens first. Reverse Polish notation, or postfix, writes each operator after its two operands: 3 4 + 2 × 7 -. It needs no parentheses and no precedence, and it evaluates left to right with one stack. Old calculators used it, and the Java virtual machine and Python's own bytecode work the same way.

The interview problem is short. It checks two small things that many candidates get wrong: the order in which operands come off the stack, and how Python divides negative numbers.

The problem

You are given a list of string tokens that form a valid postfix expression. Each token is an integer (possibly negative) or one of +, -, *, /. Division between two integers truncates toward zero. Return the value of the expression.

• ["3", "4", "+", "2", "*", "7", "-"] → 7. That is ((3 + 4) × 2) - 7 = 14 - 7.
• ["-7", "2", "/"] → -3. The exact value -3.5 truncated toward zero is -3.

Constraints: 1 ≤ len(tokens) ≤ 10⁴; the expression is always valid; there is no division by zero; every intermediate value fits in 32 bits.

Clarifying questions

• Is the input always valid? Yes. (In real code, an operator with fewer than two numbers on the stack would be an error.)
• Can numbers be negative? Yes, like "-7". So a token that starts with - is not always an operator.
• Which way does division round? Toward zero, as in C and Java. Python's // rounds toward minus infinity, which differs for negative results.
• Can a single number be the whole expression? Yes: ["42"] → 42.

Approach 1: the simple way

Find the first operator. The two tokens right before it are its operands. Replace those three tokens with the result, and repeat until one token is left.

1OPERATORS = {"+", "-", "*", "/"}234def apply(op: str, left: int, right: int) -> int:5    """Apply one operator; division truncates toward zero."""6    if op == "+":7        return left + right8    if op == "-":9        return left - right10    if op == "*":11        return left * right12    return int(left / right)                     # not //, which rounds toward minus infinity131415def eval_rpn_by_rewriting(tokens: list[str]) -> int:16    """Fold the first operator with the two numbers before it, repeat: O(n^2)."""17    tokens = list(tokens)18    while len(tokens) > 1:19        i = next(k for k, token in enumerate(tokens) if token in OPERATORS)20        value = apply(tokens[i], int(tokens[i - 2]), int(tokens[i - 1]))21        tokens[i - 2:i + 1] = [str(value)]       # three tokens become one22    return int(tokens[0])

Time: O(n²). Space: O(n).

It is correct: the first operator in a postfix list always has two plain numbers right before it. But every fold rescans the list from the start and shifts the rest of the list left. With 10⁴ tokens there are about 5,000 folds, each costing up to 10⁴ steps. The rescanning is pure waste: the numbers the next operator needs are the ones you just produced.

The key insight

In postfix, an operator always applies to the two most recent values that have not been used yet. Read 3 4 +: the + takes 3 and 4. Read on, 2 *: the * takes the 7 just produced and the 2. "The most recent unused values" is exactly the top of a stack.

So: push each number. When an operator arrives, pop two values, apply the operator, and push the result, which is now the most recent unused value. When the tokens run out, the one value left is the answer.

This is also why postfix needs no parentheses and no precedence rules. The position of each operator already says which values it takes:

In the second line, * comes straight after 4 2, so it takes them and leaves 8; then + takes 3 and 8. The order of the operators in the list is the order of evaluation. Nothing is left to decide, so a machine can evaluate it without a parser.

Order matters for - and /. The value on top was pushed last, so it is the right operand. Pop into a variable called right first, then left, and write left - right. Naming them this way makes the order visible in the code instead of hidden in it.

Approach 2: one pass with a stack

1def eval_rpn(tokens: list[str]) -> int:2    """Evaluate a postfix expression with one pass and a stack of numbers."""3    stack: list[int] = []4    for token in tokens:5        if token in OPERATORS:6            right = stack.pop()                  # pushed last, so it comes off first7            left = stack.pop()8            stack.append(apply(token, left, right))9        else:10            stack.append(int(token))11    return stack[0]

token in OPERATORS tests the whole token, so "-7" is correctly read as a number: it is not equal to "-".

Dry run on ["3", "4", "+", "2", "*", "7", "-"]:

The answer is 7. The stack never held more than two numbers here; in general its size is the number of values waiting for an operator.

Time: O(n) — one push per number and two pops per operator. Space: O(n) — for example, 1 2 3 4 + + + pushes four numbers before the first operator.

On division: int(left / right) computes the exact quotient as a float and drops the fraction, which truncates toward zero: int(-7 / 2) is int(-3.5), which is -3. Python's -7 // 2 is -4. The float is exact enough for 32-bit values; for huge integers, divide the absolute values with // and fix the sign.

Edge cases

• A single number: it is pushed and returned.
• Negative number tokens: handled by comparing whole tokens with the operator set.
• Negative division: ["-7", "2", "/"] and ["7", "-2", "/"] both give -3.
• Subtraction order: ["5", "3", "-"] gives 2. Swapping the pops gives -2, and + and * would hide the bug because they do not care about order.

Follow-ups

• "Evaluate normal infix, like 3 + 4 * 2." Convert to postfix with the shunting-yard algorithm (a stack of operators ordered by precedence), or evaluate directly with a stack of signed terms, as in the Basic Calculator lesson.
• "Build the expression tree." Same loop, but push tree nodes: an operator pops two nodes and pushes a new node with them as children.
• "Report invalid input." Check that the stack has two values before each operator and exactly one at the end.