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

1. Remove all spaces from the string and initialize an empty stack.
2. Track the current num and the previous op (start with +).
3. 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 num and update the previous op.
4. 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: $O(n)$
• Space complexity: $O(n)$

---

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

1. Initialize total, prev, and num to 0, and set the initial operator to +.
2. Iterate through the string (plus one extra iteration to process the last number).
3. Skip spaces. Build up multi-digit numbers.
4. When we hit an operator or the end:
   • For +: add prev to total, set prev to num.
   • For -: add prev to total, set prev to -num.
   • For *: multiply prev by num.
   • For /: divide prev by num (truncate toward zero).
   • Update the operator and reset num.
5. Add the final prev to total and 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 total

Time & Space Complexity

• Time complexity: $O(n)$
• Space complexity: $O(1)$

---

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.