LeetCode 772 - Basic Calculator III
This problem asks us to evaluate a mathematical expression represented as a string. The expression may contain: - Non-negative integers - Addition (+) - Subtraction (-) - Multiplication () - Division (/) - Parentheses (( and )) The goal is to compute the final integer result…
Difficulty: 🔴 Hard
Topics: Math, String, Stack, Recursion
Solution
LeetCode 772 - Basic Calculator III
Problem Understanding
This problem asks us to evaluate a mathematical expression represented as a string. The expression may contain:
- Non-negative integers
- Addition (
+) - Subtraction (
-) - Multiplication (
*) - Division (
/) - Parentheses (
(and))
The goal is to compute the final integer result while respecting normal arithmetic precedence rules.
The important detail is that multiplication and division have higher precedence than addition and subtraction. Parentheses override precedence and force expressions inside them to be evaluated first. Division must truncate toward zero, which matches the behavior expected by the problem.
The input is a single string s, representing a valid mathematical expression. The output is a single integer, the evaluated result of that expression.
The constraints tell us several important things:
-
The string length can be as large as
10^4, so the solution must be efficient. -
The expression is guaranteed to be valid, which means:
-
Parentheses are balanced
-
Operators appear in valid positions
-
No malformed expressions exist
-
Intermediate results fit within 32-bit signed integer range.
Several edge cases can cause problems in naive implementations:
- Nested parentheses such as
"2*(3+(4*5))" - Multi-digit numbers such as
"123+456" - Division with negative values, where truncation toward zero matters
- Expressions ending with a number
- Consecutive operations where precedence matters, such as
"2+3*4"
A correct implementation must parse the string carefully while preserving operator precedence and properly evaluating nested expressions.
Approaches
Brute Force Approach
A brute force style approach would repeatedly scan the string and evaluate operations according to precedence rules.
One possible implementation is:
- Resolve the innermost parentheses first.
- Replace each parenthesized expression with its computed value.
- Repeatedly scan for multiplication and division.
- Then scan for addition and subtraction.
This eventually produces the correct answer because arithmetic precedence rules are explicitly enforced in stages.
However, this approach is inefficient because every reduction may require rebuilding or rescanning large portions of the string. With deeply nested expressions or long inputs, repeated scans become expensive.
The implementation is also complicated because string mutation and token management become difficult to maintain correctly.
Optimal Approach
The optimal solution uses recursion together with a stack.
The key observation is that parentheses naturally form recursive subproblems. Whenever we encounter '(', we can recursively evaluate the subexpression inside it until reaching the matching ')'.
At each recursion level:
- We maintain the current number being built.
- We track the previous operator.
- We use a stack to handle precedence.
The stack works because:
- Addition pushes a positive number.
- Subtraction pushes a negative number.
- Multiplication immediately combines with the previous stack value.
- Division immediately combines with the previous stack value.
This preserves operator precedence naturally without needing multiple passes.
At the end of the expression or when reaching ')', the stack contains values that should simply be summed together.
| Approach | Time Complexity | Space Complexity | Notes |
|---|---|---|---|
| Brute Force | O(n²) | O(n) | Repeated rescanning and rebuilding of expressions |
| Optimal | O(n) | O(n) | Single pass parsing with recursion and stack |
Algorithm Walkthrough
- Initialize an index pointer that tracks our current position in the string.
- Create a recursive helper function that evaluates an expression starting from the current index.
- Inside the helper function, maintain:
- A stack for processed values
- A current number being built from digits
- The previous operator, initially
'+'
- Iterate through the string character by character.
- If the current character is a digit, update the current number:
num = num * 10 + digit
This correctly handles multi-digit numbers.
6. If the current character is '(', recursively evaluate the subexpression inside the parentheses. The recursive call returns the computed value, which becomes the current number.
7. When we encounter an operator, a closing parenthesis, or the end of the string, process the previous operator:
'+'pushesnum'-'pushes-num'*'pops the last value, multiplies it bynum, then pushes the result'/'pops the last value, divides bynumwith truncation toward zero, then pushes the result
- Reset
numto0and update the previous operator. - If the current character is
')', stop the current recursive call and return the sum of the stack. - After finishing the loop, return the sum of the stack as the final value for this expression level.
Why it works
The algorithm maintains an important invariant:
- The stack always contains correctly processed values for the current expression level.
- Addition and subtraction defer evaluation by storing signed values.
- Multiplication and division are evaluated immediately, ensuring proper precedence.
Recursion correctly isolates parenthesized subexpressions, allowing nested expressions to be evaluated independently before being integrated into the outer expression.
Because every character is processed exactly once, the algorithm efficiently computes the correct result.
Python Solution
class Solution:
def calculate(self, s: str) -> int:
index = 0
def evaluate() -> int:
nonlocal index
stack = []
num = 0
operator = '+'
while index < len(s):
char = s[index]
if char.isdigit():
num = num * 10 + int(char)
elif char == '(':
index += 1
num = evaluate()
if (
char in '+-*/)'
or index == len(s) - 1
):
if operator == '+':
stack.append(num)
elif operator == '-':
stack.append(-num)
elif operator == '*':
stack.append(stack.pop() * num)
elif operator == '/':
prev = stack.pop()
stack.append(int(prev / num))
operator = char
num = 0
if char == ')':
break
index += 1
return sum(stack)
return evaluate()
The implementation uses a recursive helper function named evaluate. This function processes one expression scope at a time.
The index variable is shared across recursive calls using nonlocal. This allows nested expressions to continue parsing from the correct position after returning.
The stack stores partially evaluated values. Addition and subtraction push signed numbers directly, while multiplication and division immediately modify the most recent value. This guarantees correct precedence handling.
When encountering '(', the function recursively evaluates the nested subexpression. The returned value becomes the current number in the outer expression.
The division step uses:
int(prev / num)
This is important because Python floor division (//) behaves differently for negative numbers. Using int(prev / num) ensures truncation toward zero, which matches the problem specification.
Finally, the function returns sum(stack), which combines all deferred addition and subtraction operations.
Go Solution
func calculate(s string) int {
index := 0
var evaluate func() int
evaluate = func() int {
stack := []int{}
num := 0
operator := byte('+')
for index < len(s) {
char := s[index]
if char >= '0' && char <= '9' {
num = num*10 + int(char-'0')
} else if char == '(' {
index++
num = evaluate()
}
if char == '+' ||
char == '-' ||
char == '*' ||
char == '/' ||
char == ')' ||
index == len(s)-1 {
switch operator {
case '+':
stack = append(stack, num)
case '-':
stack = append(stack, -num)
case '*':
last := stack[len(stack)-1]
stack = stack[:len(stack)-1]
stack = append(stack, last*num)
case '/':
last := stack[len(stack)-1]
stack = stack[:len(stack)-1]
stack = append(stack, last/num)
}
operator = char
num = 0
}
if char == ')' {
break
}
index++
}
total := 0
for _, value := range stack {
total += value
}
return total
}
return evaluate()
}
The Go implementation closely mirrors the Python solution, but there are several language-specific details worth noting.
Go slices are used as stacks. Removing the top element requires slicing:
stack = stack[:len(stack)-1]
Integer division in Go already truncates toward zero, so standard integer division is sufficient.
Go does not support nested functions with nonlocal variables like Python, but closures still allow access to the shared index variable.
Worked Examples
Example 1
Input:
"1+1"
Trace
| Step | Character | Current Number | Operator | Stack |
|---|---|---|---|---|
| 1 | 1 |
1 | + |
[] |
| 2 | + |
1 | + |
[1] |
| 3 | 1 |
1 | + |
[1] |
| 4 | end | 1 | + |
[1, 1] |
Final result:
1 + 1 = 2
Example 2
Input:
"6-4/2"
Trace
| Step | Character | Current Number | Operator | Stack |
|---|---|---|---|---|
| 1 | 6 |
6 | + |
[] |
| 2 | - |
6 | + |
[6] |
| 3 | 4 |
4 | - |
[6] |
| 4 | / |
4 | - |
[6, -4] |
| 5 | 2 |
2 | / |
[6, -4] |
| 6 | end | 2 | / |
[6, -2] |
Final result:
6 + (-2) = 4
Example 3
Input:
"2*(5+5*2)/3+(6/2+8)"
Parenthesized evaluation
First subexpression:
(5+5*2)
Processing:
| Step | Character | Stack |
|---|---|---|
5 |
push 5 | [5] |
+ |
operator update | [5] |
5 |
push 5 later | [5] |
* |
multiplication pending | [5, 5] |
2 |
compute 5*2 | [5, 10] |
Result:
15
Expression becomes:
2*15/3+(6/2+8)
Second subexpression:
(6/2+8)
Processing:
| Step | Character | Stack |
|---|---|---|
6 |
push 6 | [6] |
/ |
division pending | [6] |
2 |
compute 6/2 | [3] |
+ |
operator update | [3] |
8 |
push 8 | [3, 8] |
Result:
11
Expression becomes:
2*15/3+11
Final evaluation:
30/3 + 11
10 + 11
21
Complexity Analysis
| Measure | Complexity | Explanation |
|---|---|---|
| Time | O(n) | Every character is processed once |
| Space | O(n) | Stack and recursion depth can grow linearly |
The algorithm performs a single pass over the input string. Each character is visited once, and every stack operation is constant time.
The worst case space complexity occurs when the expression contains many nested parentheses or many deferred addition/subtraction values.
Test Cases
solution = Solution()
assert solution.calculate("1+1") == 2 # simple addition
assert solution.calculate("6-4/2") == 4 # division precedence
assert solution.calculate("2*(5+5*2)/3+(6/2+8)") == 21 # nested parentheses
assert solution.calculate("10") == 10 # single number
assert solution.calculate("2+3*4") == 14 # multiplication before addition
assert solution.calculate("(2+3)*4") == 20 # parentheses override precedence
assert solution.calculate("14-3/2") == 13 # truncation toward zero
assert solution.calculate("100/10/2") == 5 # left-to-right division
assert solution.calculate("1+(2+(3+(4+5)))") == 15 # deeply nested parentheses
assert solution.calculate("0") == 0 # smallest valid input
assert solution.calculate("123+456*2") == 1035 # multi-digit numbers
assert solution.calculate("7+(6*5^2+3)") != 0 # sanity check for unsupported operators not included in constraints
assert solution.calculate("42/(2*3)") == 7 # division with parentheses
assert solution.calculate("8/3") == 2 # truncation behavior
assert solution.calculate("18/(2+1)") == 6 # nested arithmetic
assert solution.calculate("50-25*2+10") == 10 # mixed operations
| Test | Why |
|---|---|
"1+1" |
Validates basic addition |
"6-4/2" |
Validates operator precedence |
"2*(5+5*2)/3+(6/2+8)" |
Validates nested parentheses |
"10" |
Validates single-number expressions |
"2+3*4" |
Ensures multiplication occurs before addition |
"(2+3)*4" |
Ensures parentheses override precedence |
"14-3/2" |
Tests truncation toward zero |
"100/10/2" |
Tests chained division |
"1+(2+(3+(4+5)))" |
Tests deep recursion |
"0" |
Tests smallest numeric value |
"123+456*2" |
Tests multi-digit parsing |
"42/(2*3)" |
Tests nested multiplication inside division |
"8/3" |
Tests integer truncation |
"18/(2+1)" |
Tests recursive subexpression evaluation |
"50-25*2+10" |
Tests multiple mixed operators |
Edge Cases
One important edge case is multi-digit numbers. A naive implementation may process each digit independently, incorrectly interpreting "123" as separate values instead of a single number. This solution handles the issue by continuously building the current number using:
num = num * 10 + digit
Another critical edge case is nested parentheses. Expressions such as:
"1+(2*(3+(4*5)))"
require recursive evaluation at multiple levels. Without recursion or careful stack management, it is easy to lose track of which operations belong to which scope. The recursive helper function cleanly isolates each parenthesized subexpression.
Division involving negative numbers is also a common source of bugs. In Python, floor division behaves differently from truncation toward zero:
-3 // 2 == -2
However, the problem requires truncation toward zero, which should produce -1. Using:
int(a / b)
ensures the correct behavior.
A final edge case involves expressions ending with a number. Since there may be no trailing operator to trigger processing, some implementations forget to evaluate the last accumulated number. This solution explicitly checks:
index == len(s) - 1
to ensure the final value is processed correctly.