Generated by Codex with GPT-5

Quick facts

Problem gist

Reverse Polish Notation writes an arithmetic expression so that every operator comes after the two values it uses. Instead of writing 2 + 3, it writes 2 3 +. This removes parentheses because the order is encoded directly in the token stream.

The task is to read a list of tokens and compute the final integer result. A token is either an integer or one of +, -, *, and /. Division must truncate toward zero, so -7 / 3 becomes -2, not -3.

Core idea

A stack matches the grammar of Reverse Polish Notation exactly. Numbers wait on the stack until an operator appears. When an operator arrives, the two most recent values are the complete operands for that operator.

For each token:

  1. If it is a number, push it onto the stack.
  2. If it is an operator, pop the right operand first, then the left operand.
  3. Apply the operator and push the result back.

At the end, the only remaining stack value is the expression result. The important detail is operand order: for subtraction and division, left op right is not the same as right op left.

Why this is optimal

Every token must be inspected at least once, so no algorithm can do better than linear time. The stack solution does exactly one pass and constant work per token. It also stores only values whose operators have not appeared yet, which is the minimum useful state for a streaming evaluation.

Python solution

from typing import Callable, Iterable, List


class ReversePolishEvaluator:
    def __init__(self) -> None:
        self._operations: dict[str, Callable[[int, int], int]] = {
            "+": lambda left, right: left + right,
            "-": lambda left, right: left - right,
            "*": lambda left, right: left * right,
            "/": self._divide_toward_zero,
        }

    def evaluate(self, tokens: Iterable[str]) -> int:
        values: list[int] = []

        for token in tokens:
            if token not in self._operations:
                values.append(int(token))
                continue

            if len(values) < 2:
                raise ValueError(f"operator {token!r} is missing operands")

            # The right operand is closer to the operator, so it is on top.
            right_operand = values.pop()
            left_operand = values.pop()
            values.append(self._operations[token](left_operand, right_operand))

        if len(values) != 1:
            raise ValueError("expression did not reduce to one result")

        return values[0]

    @staticmethod
    def _divide_toward_zero(left: int, right: int) -> int:
        if right == 0:
            raise ZeroDivisionError("division by zero")

        quotient = abs(left) // abs(right)
        return quotient if (left >= 0) == (right >= 0) else -quotient


class Solution:
    def evalRPN(self, tokens: List[str]) -> int:
        return ReversePolishEvaluator().evaluate(tokens)

Correctness sketch

After processing any prefix of the token list, the stack contains exactly the values of the complete subexpressions that have been seen but not yet consumed by a later operator. This is true initially because the stack is empty. Reading a number creates a new complete subexpression, so pushing it preserves the invariant. Reading an operator consumes the two most recent complete subexpressions, combines them into one complete subexpression, and pushes that result, so the invariant still holds.

When all tokens have been processed, a valid Reverse Polish expression has reduced every subexpression into one final value. By the invariant, that single value is the value of the whole expression.

Complexity

The algorithm runs in O(n) time for n tokens because each token is processed once and each stack operation is constant time. The stack uses O(n) space in the worst case, such as when many numbers appear before any operators.

Interview follow-ups

What if division must use floor division instead of truncation toward zero?

The stack logic stays the same, but the division helper changes. Python’s // already floors toward negative infinity, so the helper could return left // right directly. The tradeoff is semantic: floor division gives different answers for mixed-sign operands, such as -7 // 3 == -3, while the original problem requires -2.

How would this handle unary operators like negation?

The evaluator should store each operator’s arity along with its function. Binary operators would pop two operands, while unary operators would pop one. The same stack invariant still works because an operator consumes the complete subexpressions immediately before it and pushes one new result. Time stays O(n), and space stays bounded by the maximum stack depth.

How would you report malformed expressions cleanly?

Production code should validate three cases: an operator appears before enough operands exist, a token cannot be parsed as either a number or a known operator, and the final stack has anything other than one value. The implementation above raises explicit exceptions for missing operands and leftover values; a full parser could add a custom exception type that includes the token index for easier debugging.

Can the expression be evaluated from a stream?

Yes. Reverse Polish Notation is naturally streamable because the evaluator only needs the stack of unresolved values. It can process tokens one at a time without knowing future tokens. The caller only needs some end-of-stream signal so the evaluator can check that exactly one final value remains.

How would you extend this to variables or custom functions?

Numbers and operators can be replaced with a small registry. Numeric tokens still push values, variable tokens look up their current value in an environment map, and function tokens pop the number of arguments declared by the registry. This keeps the evaluator generic, but it shifts more responsibility into validation: unknown names, wrong arity, and domain errors must be reported clearly.