# LeetCode 227: Basic Calculator II ## Problem Restatement We are given a string `s` representing a mathematical expression. The expression contains: - Non-negative integers - Operators: `+`, `-`, `*`, `/` - Spaces We must evaluate the expression and return the integer result. Division truncates toward zero. LeetCode examples: ```text Input: "3+2*2" Output: 7 ``` ```text Input: " 3/2 " Output: 1 ``` ```text Input: " 3+5 / 2 " Output: 5 ``` The expression is always valid. ## Input and Output | Item | Meaning | |---|---| | Input | String `s` containing numbers and operators | | Output | Integer result | | Operators | `+`, `-`, `*`, `/` | | Division | Truncate toward zero | | Spaces | May appear anywhere | Function shape: ```python class Solution: def calculate(self, s: str) -> int: ... ``` ## Examples Example 1: ```text s = "3+2*2" ``` Multiplication has higher priority: ```text 2 * 2 = 4 3 + 4 = 7 ``` Result: ```text 7 ``` Example 2: ```text s = "14-3/2" ``` Division first: ```text 3 / 2 = 1 ``` Integer division truncates toward zero. Then: ```text 14 - 1 = 13 ``` Result: ```text 13 ``` Example 3: ```text s = "18+4*5-6/2" ``` Compute multiplication and division first: ```text 4 * 5 = 20 6 / 2 = 3 ``` Then: ```text 18 + 20 - 3 = 35 ``` Result: ```text 35 ``` ## First Thought: Build the Full Expression One possible idea is: 1. Parse all numbers and operators. 2. Build an expression tree. 3. Evaluate the tree. This works, but the problem is simpler than a full calculator parser. We only have four operators and no parentheses. That means we only need to handle operator precedence. ## Key Insight Addition and subtraction are low-priority operators. Multiplication and division are high-priority operators. We can process the expression from left to right while maintaining a stack. The stack represents values that will eventually be added together. Rules: - `+x` → push `x` - `-x` → push `-x` - `*x` → pop top value, multiply, push result - `/x` → pop top value, divide, push result At the end: ```python answer = sum(stack) ``` This works because multiplication and division are resolved immediately before later addition. ## Algorithm We scan the string character by character. Maintain: - `num`: current number being built - `op`: previous operator - `stack`: intermediate values Initially: ```python op = "+" ``` This means the first number behaves like a positive number. For every character: ### If the character is a digit Extend the current number: ```python num = num * 10 + int(ch) ``` This handles multi-digit numbers. For example: ```text "123" ``` becomes: ```text 1 12 123 ``` ### If the character is an operator or we reached the end We process the previous operator stored in `op`. If: ```python op == "+" ``` push: ```python num ``` If: ```python op == "-" ``` push: ```python -num ``` If: ```python op == "*" ``` compute immediately: ```python stack.pop() * num ``` If: ```python op == "/" ``` compute immediately: ```python int(stack.pop() / num) ``` Then: 1. Update `op` 2. Reset `num = 0` At the end, sum the stack. ## Correctness We process the expression from left to right. The stack always stores values that should eventually be added together. For addition: ```text a + b ``` we simply push `a`, then push `b`. For subtraction: ```text a - b ``` we push `a`, then push `-b`. So subtraction becomes addition of a negative number. Multiplication and division must happen before later additions. When we encounter `*` or `/`, the left operand is already at the top of the stack. So we immediately compute: ```text top * num ``` or: ```text top / num ``` and replace the old value. This guarantees multiplication and division are resolved before the final sum. Therefore, the final stack sum equals the correctly evaluated expression. ## Complexity | Metric | Value | Why | |---|---|---| | Time | `O(n)` | We scan the string once | | Space | `O(n)` | Stack may store many numbers | Here, `n` is the length of the string. ## Implementation ```python class Solution: def calculate(self, s: str) -> int: stack = [] num = 0 op = "+" for i, ch in enumerate(s): if ch.isdigit(): num = num * 10 + int(ch) if ch in "+-*/" or i == len(s) - 1: if op == "+": stack.append(num) elif op == "-": stack.append(-num) elif op == "*": stack.append(stack.pop() * num) elif op == "/": stack.append(int(stack.pop() / num)) op = ch num = 0 return sum(stack) ``` ## Code Explanation We keep building the current number: ```python num = num * 10 + int(ch) ``` This supports numbers larger than one digit. The variable `op` stores the operator that should be applied to `num`. Initially: ```python op = "+" ``` so the first number gets pushed normally. When we hit an operator, we process the previous operation. For example: ```python elif op == "*": stack.append(stack.pop() * num) ``` Suppose the stack top is `3` and `num = 4`. Then: ```text 3 * 4 = 12 ``` and `12` replaces the old stack value. Division uses: ```python int(stack.pop() / num) ``` because LeetCode requires truncation toward zero. At the end: ```python return sum(stack) ``` All multiplication and division are already resolved, so simple addition gives the final answer. ## Testing ```python def run_tests(): s = Solution() assert s.calculate("3+2*2") == 7 assert s.calculate(" 3/2 ") == 1 assert s.calculate(" 3+5 / 2 ") == 5 assert s.calculate("14-3/2") == 13 assert s.calculate("18+4*5-6/2") == 35 assert s.calculate("42") == 42 assert s.calculate("100/10*5") == 50 assert s.calculate("1-1+1") == 1 print("all tests passed") run_tests() ``` | Test | Why | |---|---| | `"3+2*2"` | Basic precedence | | `"3/2"` | Integer division | | `"3+5/2"` | Mixed operators | | `"14-3/2"` | Subtraction with division | | `"18+4*5-6/2"` | Multiple precedence changes | | `"42"` | Single number | | `"100/10*5"` | Sequential high-priority operators | | `"1-1+1"` | Mixed positive and negative accumulation |