Evaluate Reverse Polish Notation

Use a stack to evaluate arithmetic expressions in postfix notation.

stacks arithmetic parsing

Implement a function `eval_rpn(tokens)` that evaluates an arithmetic expression in Reverse Polish Notation (postfix). The expression is given as a list of strings, where each string is either an integer (e.g., `"4"`, `"-3"`) or one of the binary operators `"+"`, `"-"`, `"*"`, `"/"`.

Division between two integers should truncate toward zero (e.g., `8 / -3 = -2`). The expression is guaranteed to be valid and the final result is a 32-bit integer. Use a stack to keep track of operands.

Return the integer result.

Constraints

- 1 <= len(tokens) <= 10^4
- tokens[i] is either an integer string (with an optional leading `-`) or one of `+`, `-`, `*`, `/`.
- The input is always a valid postfix expression.
- Intermediate results fit within a 32-bit signed integer.

Example

>>> eval_rpn(["2", "1", "+", "3", "*"])
9
>>> eval_rpn(["4", "13", "5", "/", "+"])
6
>>> eval_rpn(["10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"])
22

25 points ~25 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Push every operand onto the stack. When an operator is encountered, pop two operands and compute the result.

For subtraction and division, the order matters: the second popped value is the left operand.

For division, use `int(a / b)` to truncate toward zero, not `a // b` which floors.

The final stack should contain exactly one value—the result.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.