# LeetCode 150: Evaluate Reverse Polish Notation ## Problem Restatement We are given an array of strings representing an arithmetic expression in Reverse Polish Notation (RPN). Evaluate the expression and return the integer result. Valid operators are: | Operator | Meaning | |---|---| | `+` | Addition | | `-` | Subtraction | | `*` | Multiplication | | `/` | Division | Each operand may be an integer or another expression. Division truncates toward zero. LeetCode guarantees that: - the input is always valid - there is no division by zero - the final answer fits in a 32-bit signed integer ([leetcode.com](https://leetcode.com/problems/evaluate-reverse-polish-notation/?utm_source=chatgpt.com)) ## What Is Reverse Polish Notation? Normal arithmetic writes operators between operands: ```text 2 + 3 ``` Reverse Polish Notation writes the operator after the operands: ```text 2 3 + ``` More examples: | Infix | RPN | |---|---| | `(2 + 3) * 4` | `2 3 + 4 *` | | `5 - (1 + 2)` | `5 1 2 + -` | RPN removes the need for parentheses because the order of evaluation is encoded directly in the token order. ## Examples Example 1: ```python tokens = ["2", "1", "+", "3", "*"] ``` Evaluation: ```text 2 + 1 = 3 3 * 3 = 9 ``` Output: ```python 9 ``` Example 2: ```python tokens = ["4", "13", "5", "/", "+"] ``` Evaluation: ```text 13 / 5 = 2 4 + 2 = 6 ``` Output: ```python 6 ``` Example 3: ```python tokens = [ "10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+" ] ``` Output: ```python 22 ``` ## Input and Output | Item | Meaning | |---|---| | Input | `tokens: list[str]` | | Output | Integer result | | Expression type | Reverse Polish Notation | | Division rule | Truncate toward zero | Function shape: ```python class Solution: def evalRPN(self, tokens: list[str]) -> int: ... ``` ## Key Insight RPN evaluation naturally fits a stack. Why? When we see a number: ```text store it for later ``` When we see an operator: ```text combine the most recent operands ``` The "most recent unresolved values" behavior is exactly what a stack provides. ## Stack Process For each token: | Token type | Action | |---|---| | Number | Push onto stack | | Operator | Pop two operands, apply operator, push result | At the end, the stack contains one value: ```text the final answer ``` ## Important Operand Order Suppose the stack contains: ```text [5, 2] ``` and the operator is: ```text - ``` We pop: ```python right = 2 left = 5 ``` Then compute: ```python 5 - 2 ``` not: ```python 2 - 5 ``` So the order matters. The second popped value is the left operand. ## Example Walkthrough Consider: ```python tokens = ["2", "1", "+", "3", "*"] ``` Start: ```text stack = [] ``` Read `"2"`: ```text stack = [2] ``` Read `"1"`: ```text stack = [2, 1] ``` Read `"+"`: ```text pop 1 pop 2 compute 2 + 1 = 3 push 3 ``` Now: ```text stack = [3] ``` Read `"3"`: ```text stack = [3, 3] ``` Read `"*"`: ```text pop 3 pop 3 compute 3 * 3 = 9 push 9 ``` Final stack: ```text [9] ``` Answer: ```python 9 ``` ## Division Behavior LeetCode requires: ```text truncate toward zero ``` This matters for negative division. Example: ```python -7 / 2 ``` Mathematical result: ```python -3.5 ``` Truncate toward zero: ```python -3 ``` In Python: ```python -7 // 2 ``` gives: ```python -4 ``` because floor division rounds downward. So we must use: ```python int(a / b) ``` instead. ## Algorithm Create an empty stack. For each token: 1. If it is a number: - push it onto the stack 2. Otherwise: - pop right operand - pop left operand - apply operator - push result At the end: ```python stack[0] ``` is the answer. ## Correctness The stack always contains the values of fully evaluated subexpressions whose operators have not yet been applied to later expressions. When a number token appears, pushing it onto the stack correctly stores it as a new operand. When an operator appears, Reverse Polish Notation guarantees that the two most recent unresolved values are exactly the operands for that operator. The algorithm pops those two operands in the correct order, evaluates the operation, and pushes the resulting subexpression value back onto the stack. Thus, after processing each token, the stack correctly represents all partially evaluated expressions up to that point. Since the expression is valid, processing all tokens leaves exactly one value on the stack, which is the value of the entire expression. Therefore, the algorithm correctly evaluates the Reverse Polish Notation expression. ## Complexity Let: | Symbol | Meaning | |---|---| | `n` | Number of tokens | | Metric | Value | Why | |---|---:|---| | Time | `O(n)` | Each token processed once | | Space | `O(n)` | Stack may store many operands | ## Implementation ```python class Solution: def evalRPN(self, tokens: list[str]) -> int: stack = [] for token in tokens: if token not in {"+", "-", "*", "/"}: stack.append(int(token)) continue right = stack.pop() left = stack.pop() if token == "+": stack.append(left + right) elif token == "-": stack.append(left - right) elif token == "*": stack.append(left * right) else: stack.append(int(left / right)) return stack[0] ``` ## Code Explanation The stack stores intermediate values: ```python stack = [] ``` If the token is a number: ```python stack.append(int(token)) ``` push it onto the stack. Otherwise, it is an operator. Pop operands: ```python right = stack.pop() left = stack.pop() ``` Order matters. Apply the operator: ```python left op right ``` For division: ```python int(left / right) ``` ensures truncation toward zero. Finally: ```python return stack[0] ``` returns the evaluated expression. ## Alternative Operator Table We can avoid long `if` chains by using a dictionary of functions. ```python class Solution: def evalRPN(self, tokens: list[str]) -> int: stack = [] operators = { "+": lambda a, b: a + b, "-": lambda a, b: a - b, "*": lambda a, b: a * b, "/": lambda a, b: int(a / b), } for token in tokens: if token not in operators: stack.append(int(token)) continue right = stack.pop() left = stack.pop() stack.append( operators[token](left, right) ) return stack[0] ``` This version is shorter and easier to extend. ## Testing ```python def run_tests(): s = Solution() assert s.evalRPN([ "2", "1", "+", "3", "*" ]) == 9 assert s.evalRPN([ "4", "13", "5", "/", "+" ]) == 6 assert s.evalRPN([ "10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+" ]) == 22 assert s.evalRPN([ "3", "-4", "+" ]) == -1 assert s.evalRPN([ "-7", "2", "/" ]) == -3 assert s.evalRPN([ "5" ]) == 5 print("all tests passed") run_tests() ``` Test meaning: | Test | Why | |---|---| | `["2","1","+","3","*"]` | Standard nested expression | | Division example | Confirms operator ordering | | Large example | Complex nested evaluation | | Negative addition | Handles negative numbers | | Negative division | Confirms truncation toward zero | | Single number | Smallest valid expression |