Evaluate Reverse Polish Notation

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

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

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 an integer or an operator.

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

• Invariant: the stack always contains the values of the sub-expressions evaluated so far.
• The stack always holds the correct values of processed subexpressions.
• Applying an operator to the top values yields the correct combined value.
• The final stack top equals the expression value.

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.

Complexity

• Time: O(n)
• Extra space: O(n)

Implementation notes (Go)

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