Prerequisites
Before attempting this problem, you should be comfortable with:
- Stack Data Structure - Used to defer lower-precedence operations while computing higher-precedence ones
- String Parsing - Building multi-digit numbers from character sequences and handling whitespace
- Operator Precedence - Understanding that multiplication/division must be evaluated before addition/subtraction
1. Stack
Intuition
The challenge with evaluating expressions is handling operator precedence. Multiplication and division must be done before addition and subtraction. We can use a stack to defer the addition and subtraction while immediately computing multiplication and division. For + and -, we push numbers onto the stack (negative for subtraction). For * and /, we pop the previous number, compute the result, and push it back. At the end, summing the stack gives us the answer.
Algorithm
- Remove all spaces from the string and initialize an empty
stack. - Track the current
numand the previousop(start with+). - For each character:
- If it's a digit, build up the current
num. - If it's an operator or the last character:
- Apply the previous
op: push for+, push negative for-, multiply top for*, divide top for/. - Reset the current
numand update the previousop.
- Apply the previous
- If it's a digit, build up the current
- Return the sum of all elements in the
stack.
class Solution:
def calculate(self, s: str) -> int:
stack = []
num = 0
op = '+'
s = s.replace(' ', '')
for i, ch in enumerate(s):
if ch.isdigit():
num = num * 10 + int(ch)
if (not ch.isdigit()) or i == len(s) - 1:
if op == '+':
stack.append(num)
elif op == '-':
stack.append(-num)
elif op == '*':
stack.append(stack.pop() * num)
else:
prev = stack.pop()
stack.append(int(prev / num))
op = ch
num = 0
return sum(stack)Time & Space Complexity
- Time complexity:
- Space complexity:
2. Without Stack
Intuition
We can avoid using a stack by realizing that we only need to track two values: the running total of all fully computed terms, and the prev term that might still be involved in a multiplication or division. When we see + or -, we can add the prev term to our total and start a new term. When we see * or /, we update the prev term directly. This reduces space complexity to O(1).
Algorithm
- Initialize
total,prev, andnumto0, and set the initial operator to+. - Iterate through the string (plus one extra iteration to process the last number).
- Skip spaces. Build up multi-digit numbers.
- When we hit an operator or the end:
- For
+: addprevtototal, setprevtonum. - For
-: addprevtototal, setprevto-num. - For
*: multiplyprevbynum. - For
/: divideprevbynum(truncate toward zero). - Update the operator and reset
num.
- For
- Add the final
prevtototaland return it.
class Solution:
def calculate(self, s: str) -> int:
total = prev = num = 0
op = '+'
n = len(s)
i = 0
while i <= n:
ch = s[i] if i < n else '+'
if ch == ' ':
i += 1
continue
if '0' <= ch <= '9':
num = num * 10 + (ord(ch) - ord('0'))
else:
if op == '+':
total += prev
prev = num
elif op == '-':
total += prev
prev = -num
elif op == '*':
prev = prev * num
else:
if prev < 0:
prev = -(-prev // num)
else:
prev = prev // num
op = ch
num = 0
i += 1
total += prev
return totalTime & Space Complexity
- Time complexity:
- Space complexity:
Common Pitfalls
Incorrect Integer Division with Negative Numbers
Division in this problem truncates toward zero, but some languages (like Python) use floor division by default, which truncates toward negative infinity. This gives wrong results for negative numbers.
# Wrong: -3 // 2 = -2 in Python (floor division)
# Correct: int(-3 / 2) = -1 (truncation toward zero)Forgetting to Process the Last Number
The algorithm typically processes a number when it encounters an operator. However, the last number in the expression has no operator after it, so it might never get processed unless you handle this edge case explicitly.
Not Handling Spaces Correctly
The expression can contain spaces between numbers and operators. Failing to skip or remove spaces causes parsing errors or treats spaces as invalid characters.