LeetCode 227 - Basic Calculator II
The problem gives us a string representing a mathematical expression containing non-negative integers, spaces, and the four operators +, -, , and /. Our task is to evaluate the expression and return the resulting integer value.
Difficulty: 🟡 Medium
Topics: Math, String, Stack
Solution
Problem Understanding
The problem gives us a string representing a mathematical expression containing non-negative integers, spaces, and the four operators +, -, *, and /. Our task is to evaluate the expression and return the resulting integer value.
The important detail is that multiplication and division must follow normal arithmetic precedence rules. This means * and / must be evaluated before + and -. Division truncates toward zero, which matches the behavior expected by the problem statement rather than floating point division.
For example, the expression "3+2*2" should evaluate to 7, not 10, because multiplication happens before addition. The multiplication 2*2 is evaluated first, producing 4, then 3+4 gives 7.
The input string may contain spaces anywhere between tokens. These spaces should simply be ignored during parsing. The expression is guaranteed to be valid, which simplifies the implementation because we do not need to handle malformed input cases such as consecutive operators or missing operands.
The constraints are important. The string length can be as large as 3 * 10^5, which means any inefficient parsing strategy could become too slow. We need an algorithm that processes the expression in a single pass or close to it. A quadratic solution would not scale to the maximum input size.
There are several edge cases that can easily introduce bugs:
- Expressions with spaces in arbitrary locations, such as
" 3+5 / 2 " - Multi-digit numbers like
"123+456" - Expressions ending with a number, where the final pending operation must still be processed
- Division involving negative intermediate results, where truncation toward zero matters
- Sequences of multiplication and division operators that must preserve precedence correctly
The problem guarantees that all intermediate results fit within a signed 32-bit integer, so overflow handling is not required.
Approaches
A brute-force approach would first tokenize the expression into numbers and operators, then repeatedly scan the expression to evaluate operators according to precedence rules. One pass could resolve all multiplications and divisions, followed by another pass for additions and subtractions.
This approach is correct because it explicitly simulates standard arithmetic evaluation order. However, if implemented naively using repeated list modifications or string rebuilding, it can become inefficient. Removing elements from arrays repeatedly can lead to quadratic behavior in the worst case.
The key insight for the optimal solution is that we do not actually need to build a full expression tree or repeatedly reprocess the input. Since multiplication and division have higher precedence than addition and subtraction, we can process the string from left to right while maintaining a stack of intermediate values.
Whenever we encounter:
+, we push the current number onto the stack-, we push the negative version of the current number*, we pop the previous number, multiply it with the current number, and push the result back/, we pop the previous number, divide it by the current number with truncation toward zero, and push the result back
At the end, summing the stack produces the correct answer because all multiplication and division operations have already been resolved immediately.
| Approach | Time Complexity | Space Complexity | Notes |
|---|---|---|---|
| Brute Force | O(n²) | O(n) | Repeatedly scans and modifies the expression |
| Optimal | O(n) | O(n) | Single pass using a stack to enforce precedence |
Algorithm Walkthrough
- Initialize an empty stack, a variable
current_numberset to0, and a variableprevious_operatorinitialized to'+'.
The stack will store numbers that are ready to be summed later. The previous_operator tells us how the current number should be processed once we encounter the next operator.
2. Iterate through the string character by character.
We scan the expression once from left to right. This ensures linear time complexity. 3. If the current character is a digit, build the full number.
Since numbers may contain multiple digits, we update:
current_number = current_number * 10 + digit
This allows us to correctly parse values like 123.
4. If the current character is an operator or we have reached the final character, process the previously accumulated number.
At this point, current_number represents the operand associated with previous_operator.
5. Apply the previous operator:
- If
previous_operatoris'+', pushcurrent_numberonto the stack - If
previous_operatoris'-', push-current_number - If
previous_operatoris'*', pop the top value, multiply it withcurrent_number, and push the result - If
previous_operatoris'/', pop the top value, divide it bycurrent_numberusing truncation toward zero, and push the result
This works because multiplication and division should happen immediately before lower-precedence operations are considered.
6. Update previous_operator to the current operator and reset current_number to 0.
This prepares us to parse the next number. 7. After processing the entire string, sum all values in the stack.
Addition and subtraction were deferred by storing signed values in the stack. Summing the stack therefore produces the final result.
Why it works
The core invariant is that the stack always contains values that are already fully resolved with respect to multiplication and division. Addition and subtraction are represented simply as signed numbers waiting to be summed later. Since multiplication and division are processed immediately when encountered, operator precedence is preserved correctly throughout the single left-to-right pass.
Python Solution
class Solution:
def calculate(self, s: str) -> int:
stack: list[int] = []
current_number = 0
previous_operator = "+"
for i, char in enumerate(s):
if char.isdigit():
current_number = current_number * 10 + int(char)
if char in "+-*/" or i == len(s) - 1:
if previous_operator == "+":
stack.append(current_number)
elif previous_operator == "-":
stack.append(-current_number)
elif previous_operator == "*":
stack.append(stack.pop() * current_number)
elif previous_operator == "/":
previous_value = stack.pop()
stack.append(int(previous_value / current_number))
previous_operator = char
current_number = 0
return sum(stack)
The implementation follows the exact algorithm described earlier.
The stack stores intermediate values that are ready for eventual summation. Addition and subtraction simply push positive or negative numbers. Multiplication and division immediately combine with the previous stack value, ensuring operator precedence is respected.
The variable current_number is used to construct multi-digit integers while scanning the string. Each digit updates the number incrementally.
The condition:
if char in "+-*/" or i == len(s) - 1:
ensures that processing occurs whenever we reach an operator or the end of the string. This final condition is important because expressions always end with a number rather than an operator.
For division, the expression:
int(previous_value / current_number)
correctly truncates toward zero, matching the problem requirements.
Finally, summing the stack produces the complete evaluated result.
Go Solution
func calculate(s string) int {
stack := []int{}
currentNumber := 0
previousOperator := '+'
for i := 0; i < len(s); i++ {
char := s[i]
if char >= '0' && char <= '9' {
currentNumber = currentNumber*10 + int(char-'0')
}
if (char < '0' || char > '9') && char != ' ' || i == len(s)-1 {
switch previousOperator {
case '+':
stack = append(stack, currentNumber)
case '-':
stack = append(stack, -currentNumber)
case '*':
lastValue := stack[len(stack)-1]
stack = stack[:len(stack)-1]
stack = append(stack, lastValue*currentNumber)
case '/':
lastValue := stack[len(stack)-1]
stack = stack[:len(stack)-1]
stack = append(stack, lastValue/currentNumber)
}
previousOperator = rune(char)
currentNumber = 0
}
}
result := 0
for _, value := range stack {
result += value
}
return result
}
The Go implementation mirrors the Python logic closely, but there are some language-specific differences.
Go uses slices instead of Python lists. Removing the top element from the stack requires slicing:
stack = stack[:len(stack)-1]
Go integer division already truncates toward zero, so no extra conversion is needed for division.
Characters are processed as bytes from the string, and digit parsing is done manually using ASCII arithmetic:
int(char - '0')
Unlike Python, Go does not provide built-in methods like isdigit(), so character comparisons are used instead.
Worked Examples
Example 1
Input:
"3+2*2"
| Step | Character | Current Number | Previous Operator | Stack |
|---|---|---|---|---|
| 1 | 3 |
3 | + |
[] |
| 2 | + |
3 | + |
[3] |
| 3 | 2 |
2 | + |
[3] |
| 4 | * |
2 | + |
[3, 2] |
| 5 | 2 |
2 | * |
[3, 2] |
| 6 | End | 2 | * |
[3, 4] |
Final result:
3 + 4 = 7
Example 2
Input:
" 3/2 "
| Step | Character | Current Number | Previous Operator | Stack |
|---|---|---|---|---|
| 1 | 3 |
3 | + |
[] |
| 2 | / |
3 | + |
[3] |
| 3 | 2 |
2 | / |
[3] |
| 4 | End | 2 | / |
[1] |
Final result:
1
The division truncates toward zero.
Example 3
Input:
" 3+5 / 2 "
| Step | Character | Current Number | Previous Operator | Stack |
|---|---|---|---|---|
| 1 | 3 |
3 | + |
[] |
| 2 | + |
3 | + |
[3] |
| 3 | 5 |
5 | + |
[3] |
| 4 | / |
5 | + |
[3, 5] |
| 5 | 2 |
2 | / |
[3, 5] |
| 6 | End | 2 | / |
[3, 2] |
Final result:
3 + 2 = 5
Complexity Analysis
| Measure | Complexity | Explanation |
|---|---|---|
| Time | O(n) | Each character is processed exactly once |
| Space | O(n) | The stack may store up to O(n) numbers |
The algorithm performs a single left-to-right scan of the string. Every character contributes to constant-time work, so the runtime is linear.
The stack can grow proportionally to the number of operators in the worst case, such as an expression containing only additions and subtractions. Therefore, the auxiliary space complexity is linear.
Test Cases
solution = Solution()
assert solution.calculate("3+2*2") == 7 # basic precedence
assert solution.calculate(" 3/2 ") == 1 # truncating division
assert solution.calculate(" 3+5 / 2 ") == 5 # spaces and precedence
assert solution.calculate("1+2+3") == 6 # only addition
assert solution.calculate("10-3-2") == 5 # chained subtraction
assert solution.calculate("2*3*4") == 24 # chained multiplication
assert solution.calculate("100/10/2") == 5 # chained division
assert solution.calculate("14-3/2") == 13 # truncation toward zero
assert solution.calculate("0") == 0 # single number
assert solution.calculate("42") == 42 # multi-digit single number
assert solution.calculate("1+2*5-3/2") == 10 # mixed operations
assert solution.calculate("12+34*2") == 80 # multi-digit parsing
assert solution.calculate(" 30 + 2 * 5 ") == 40 # irregular spaces
assert solution.calculate("1-1+1") == 1 # alternating operators
assert solution.calculate("2*3+4") == 10 # multiplication before addition
assert solution.calculate("2+3*4") == 14 # multiplication precedence
assert solution.calculate("100000") == 100000 # large single number
| Test | Why |
|---|---|
"3+2*2" |
Verifies operator precedence |
" 3/2 " |
Verifies truncating integer division |
" 3+5 / 2 " |
Verifies spaces are ignored |
"1+2+3" |
Tests repeated addition |
"10-3-2" |
Tests repeated subtraction |
"2*3*4" |
Tests repeated multiplication |
"100/10/2" |
Tests repeated division |
"14-3/2" |
Ensures truncation toward zero |
"0" |
Smallest valid numeric input |
"42" |
Single multi-digit number |
"1+2*5-3/2" |
Mixed operators and precedence |
"12+34*2" |
Multi-digit parsing correctness |
" 30 + 2 * 5 " |
Handles excessive spaces |
"1-1+1" |
Alternating addition and subtraction |
"2*3+4" |
Multiplication before addition |
"2+3*4" |
Multiplication after addition |
"100000" |
Larger numeric input |
Edge Cases
One important edge case is expressions containing many spaces in unpredictable locations. A naive parser might incorrectly interpret spaces as meaningful characters or fail to process the final number correctly. This implementation ignores spaces naturally because processing only occurs when encountering operators or digits.
Another important edge case is multi-digit numbers. If the algorithm treated every digit independently, an input like "123+45" would be interpreted incorrectly. The implementation avoids this by continuously building the current number using:
current_number = current_number * 10 + int(char)
This preserves the full numeric value regardless of digit length.
A third critical edge case involves division with negative intermediate results. Languages differ in how integer division behaves for negative numbers. The problem requires truncation toward zero, not floor division. In Python, using:
int(previous_value / current_number)
ensures the result truncates correctly toward zero.
Another subtle case occurs at the end of the string. Since expressions end with a number rather than an operator, the final number would never be processed if we only reacted to operators. The condition:
or i == len(s) - 1
ensures the last pending operation is always applied.