Evaluate Reverse Polish Notation
Module 8 · Stacks
Problem
Evaluate an arithmetic expression in Reverse Polish Notation (RPN,
postfix): operators come after their operands. Tokens are integers or
+ - * /; division truncates toward zero. The input is always a
valid expression.
Examples
Example 1
Input
["2","1","+","3","*"]Output9 ((2 + 1) * 3)Example 2
Input
["4","13","5","/","+"]Output6 (4 + (13 / 5))Example 3
Input
["10","6","9","3","+","-11","*","/","*","17","+","5","+"]Output22Constraints
1 ≤ tokens ≤ 10⁴ · intermediate values fit in 32 bits.
Attempt it first
RPN looks alien until you see what it removes: parentheses. The order
of operations is encoded in the token order itself — which is exactly
why compilers convert your infix code to this form. The evaluation rule
is one sentence; find it by evaluating 2 1 + 3 * by hand.