# NEETCODE - Stack: Evaluate Reverse Polish Notation ## 1. Problem Statement You are given an array of strings `tokens` that represents a valid arithmetic expression in **Reverse Polish Notation** (RPN). Return the integer that represents the evaluation of the expression. ### Rules - The operands may be integers or the results of other operations - The operators include `'+'`, `'-'`, `'*'`, and `'/'` - Assume that division between integers always **truncates toward zero** ### Example 1 **Input:** `tokens = ["1", "2", "+", "3", "*", "4", "-"]` **Output:** `5` **Explanation:** `((1 + 2) * 3) - 4 = 5` ### Example 2 **Input:** `tokens = ["10", "6", "9", "3", "/", "-11", "*", "/", "*", "17", "+", "5", "+"]` **Output:** `22` ### Constraints - `1 <= tokens.length <= 1000` - `tokens[i]` is `"+", "-", "*", or "/", or a string representing an integer in the range `[-100, 100]` --- ## 2. Your Solution Review & Feedback ### What You Implemented You wrote **two implementations** of this problem: **First attempt:** ```python class Solution: def __init__(self): self.stack = [] def push(self, value): self.stack.append(value) def pop(self): return self.stack.pop() def is_number(self, character: str) -> bool: try: int(character) return True except: return False def evalRPN(self, tokens: List[str]) -> int: for character in tokens: if self.is_number(character): character_int = int(character) self.push(character_int) else: second_addend = self.pop() first_addend = self.pop() if character == "+": self.push(first_addend + second_addend) elif character == "-": self.push(first_addend - second_addend) elif character == "*": self.push(first_addend * second_addend) elif character == "/": self.push(int(first_addend / second_addend)) return self.stack[0] ``` **Second attempt:** ```python class Solution: def evalRPN(self, tokens: List[str]) -> int: stack = [] for token in tokens: if token.strip("-").isdigit(): stack.append(int(token)) elif token == "+": a = stack.pop() b = stack.pop() stack.append(a + b) elif token == "-": a = stack.pop() b = stack.pop() stack.append(b - a) elif token == "*": a = stack.pop() b = stack.pop() stack.append(a * b) elif token == "/": a = stack.pop() b = stack.pop() stack.append(int(b / a)) return stack.pop() ``` ### What Worked Well ✅ **Core algorithm is perfect:** Both solutions correctly use a stack to evaluate RPN expressions. ✅ **Correct operand order in second solution:** In your second attempt, you correctly handle `b - a` and `b / a` (not `a - b` or `a / b`). This is crucial because subtraction and division are not commutative. ✅ **Good progression:** You showed improvement from first to second attempt, making the code cleaner. ✅ **Handles negative numbers:** Your second solution uses `strip("-").isdigit()` to handle negative numbers correctly. ### Issues Identified ❌ **Incorrect operand order in first solution:** When you pop from a stack, the order matters for non-commutative operations! **Overcomplicated number detection in first solution:** This works, but using bare `except` is bad practice. Should catch specific exception. **Your second solution uses a better approach:** `tokens[i].strip("-").isdigit()`. ### Learning Points 1. **Order matters for non-commutative operations:** When popping two values from a stack for subtraction or division, remember that the first popped value is the second operand in the original expression. 2. **Local variables > instance variables for stateless functions:** Your second solution is better because it doesn't maintain state between calls. 3. **Clear variable names matter:** `first_addend` is confusing when it's actually the value that was pushed second. Generic names like `a`/`b` or `right`/`left` are clearer. 4. **Python division quirks:** `int(a / b)` truncates toward zero (correct for this problem). ### Recommended Improvements 1. Iterate directly over tokens instead of using indices: ```python for token in tokens: if token.strip("-").isdigit(): ``` 2. Consider using a dictionary for operators to avoid the long `elif` chain: ```python ops = { "+": lambda a, b: b + a, "-": lambda a, b: b - a, "*": lambda a, b: b * a, "/": lambda a, b: int(b / a), } if token in ops: a = stack.pop() b = stack.pop() stack.append(ops[token](a, b)) ``` ### Approach 1: Recursion (Not Optimal) ```python class Solution: def evalRPN(self, tokens: List[str]) -> int: def evaluate(index): token = tokens[index] if token in "+-*/": right, right_index = evaluate(index - 1) left, left_index = evaluate(right_index - 1) if token == "+": result = left + right elif token == "-": result = left - right elif token == "*": result = left * right elif token == "/": result = int(left / right) return result, left_index else: return int(token), index - 1 result, _ = evaluate(len(tokens) - 1) return result ``` **Time Complexity:** O(n) - visit each token once **Space Complexity:** O(n) - recursion call stack depth **Why this doesn't work well:** - Overly complex for this problem - Hard to understand and debug ### Approach 2: Stack (Optimal) ```python class Solution: def evalRPN(self, tokens: List[str]) -> int: operand_stack = [] for current_token in tokens: if current_token in ["+", "-", "*", "/"]: right_operand = operand_stack.pop() left_operand = operand_stack.pop() if current_token == "+": result = left_operand + right_operand elif current_token == "-": result = left_operand - right_operand elif current_token == "*": result = left_operand * right_operand elif current_token == "/": result = int(left_operand / right_operand) operand_stack.append(result) else: operand_stack.append(int(current_token)) return operand_stack[0] ``` **Key insight:** RPN eliminates the need for parentheses by using postfix notation. The stack naturally handles operator precedence because operators are applied immediately to their operands. #### Common Mistakes 1. **Wrong operand order for non-commutative operations:** ```python result = left - right # First popped is right operand ``` 2. **Using floor division for truncation:** ```python result = int(left / right) # Truncates toward zero ``` 3. **Not handling negative numbers in input:** ```python if token not in operators: stack.append(int(token)) # int() handles negatives ``` 4. **Returning wrong result:** ```python return stack[0] # or stack.pop() ``` ### Interview Tips **Do's** - Clarify input format: "Are all tokens already split into a list?" - Explain RPN concept: "In RPN, operators come after operands, so 3 + 4 becomes 3 4 +" - Walk through an example: Draw the stack state after each token **Don'ts** - Don't confuse RPN with infix notation: - Don't use `//` for division: - Don't forget operand order: --- ## 12. Complexity Summary Table | Approach | Time | Space | When to Use | | --- | --- | --- | --- | | Stack (if/elif) | O(n) | O(n) | Always - simple and clear | | Stack (operator dict) | O(n) | O(n) | When you need extensibility | **Optimal Solution:** Stack with O(n) time and O(n) space.