Evaluate Reverse Polish Notation

Evaluate the value of an arithmetic expression in Reverse Polish Notation (RPN).

Valid operators are +, -, *, and /. Division truncates toward zero.

Why this is worth learning

The stack contains completed subexpression values whose parent operators have not yet arrived. Operand order is carried by position, not by operator commutativity.

Before coding: one-minute experiment

What does ["7","-3","/"] evaluate to, and why is the result not -3?

Function signature

func EvalRPN(tokens []string) int

Inputs / outputs

• tokens: list of tokens in RPN.
• Return: the evaluated integer result.

Example

tokens = ["2","1","+","3","*"]
Output: 9

((2 + 1) * 3) = 9

Constraints

• 1 <= len(tokens) <= 100_000
• Each token is a signed decimal integer or one of +, -, *, /.
• Tokens form a valid complete postfix expression: each operator has two operands and exactly one value remains.
• Every divisor is nonzero. Every literal and mathematical intermediate result fits the course's signed 64-bit int; this includes the result of division.

Core idea (near-solution)

Use a stack of integers. When you see a number, push it. When you see an operator, pop two numbers, apply, and push the result.

Invariant: the stack always contains the values of the sub-expressions evaluated so far.

Algorithm (step-by-step)

1. Initialize empty stack.
2. For each token:
   • If it's a number, push it.
   • Else pop b, then a, compute a op b, and push the result.
3. Return the final stack value.

Correctness sketch

For every processed token prefix, the stack lists the values of completed expression fragments in their original left-to-right order. An integer token contributes one new fragment. A binary operator combines the last two fragments: the last popped value is the right operand b and the next is the left operand a, so replace them with a op b. This is exactly the postfix grammar rule, preserving the fragment-value invariant. For a valid complete expression, all fragments eventually combine into one value, which is the answer. Go integer division supplies the specified truncation toward zero when the divisor is nonzero.

Trace (hand walkthrough)

Example input:
tokens = ["2","1","+","3","*"]
Output: 9

((2 + 1) * 3) = 9

Walk:
- push 2, push 1
- "+": pop 1,2 -> push 3
- push 3; "*": pop 3,3 -> push 9

Pitfalls to avoid

• Reversing operand order for subtraction/division.
• Using floor division instead of truncation toward zero.

Debugging lens

Use subtraction and negative division to expose operand reversal. Inputs must form a valid expression, have nonzero divisors, and keep parsed/intermediate values within the intended int range; this function is not an error-reporting parser.

Complexity

Time: O(T+B), where T is the token count and B the total bytes parsed from integer tokens; O(T) under bounded-width integers. Auxiliary stack space: O(T).

Implementation notes (Go)

• Use a stack of ints; parse numbers with strconv.Atoi.
• For operators, pop b then a and apply a op b.

Reconstruction checkpoint

What does ["7","-3","/"] evaluate to, and why is the result not -3?

Return to Stack + Monotonic · Module quiz