Evaluate Reverse Polish Notation

Problem

Stack-based virtual machines - including the JVM and Python's bytecode interpreter - evaluate arithmetic by pushing operands and applying operators as they arrive. Given an array of tokens representing an arithmetic expression in Reverse Polish Notation, evaluate the expression and return the result. Operators are +, -, *, and /; division truncates toward zero.

Input:  ["2","1","+","3","*"]              → 9     ((2+1)*3)
Input:  ["4","13","5","/","+"]             → 6     (4+(13/5))
Input:  ["10","6","9","3","+","-11","*","/',*","17","+","5","+"]  → 22

Try it

Python

Loading editor…

Tests

assert eval_rpn(["2", "1", "+", "3", "*"]) == 9

assert eval_rpn(["4", "13", "5", "/", "+"]) == 6

assert eval_rpn(["3"]) == 3

assert eval_rpn(["7", "2", "-"]) == 5

assert eval_rpn(["6", "2", "/"]) == 3

Hints (3)

Solution

Approach: Operand stack for a postfix expression.

Scan tokens left to right with a stack of operands. If a token is one of + - * /, it operates on the two most recently produced values: pop right first (it is on top), then left, apply the operator, and push the result back so it can serve as an operand for later operators. Any other token is a number, so push int(token). Because the expression is valid postfix, when the scan ends the stack holds exactly one value, stack[0], the answer.

The insight is that postfix notation already encodes evaluation order, so no precedence rules or parentheses parsing are needed - the stack simply holds operands waiting for the next operator. Operand order matters for the non-commutative operators: since the stack is LIFO, the first pop is the right-hand operand and the second is the left, so ["7", "2", "-"] correctly computes 7 - 2 = 5, not 2 - 7. Trace ["2", "1", "+", "3", "*"]: push 2, push 1, + pops 1 and 2 and pushes 3, push 3, * pops 3 and 3 and pushes 9. Result: 9.

Edge cases: Division uses int(left / right) to truncate toward zero, unlike // which floors (for -7 / 2, this gives -3, not -4). Negative-number tokens like "-11" are matched against the operator set first, so they fall through to int(token) and are pushed as numbers. A lone number such as ["3"] is pushed and returned unchanged.

Complexity: O(n) time, O(n) space - each token is handled once with O(1) stack operations; the stack can hold up to n operands when numbers precede a trailing operator.