Problem Description

You are given a string s that represents a mathematical expression containing integers and the operators +, -, *, and /. Your task is to evaluate this expression and return its value.

The expression follows these rules:

• The string contains only non-negative integers and the four operators (+, -, *, /)
• Integer division should truncate toward zero (e.g., 7/2 = 3 and -7/2 = -3)
• The given expression is always valid
• All intermediate results will be within the range [-2^31, 2^31 - 1]
• You cannot use built-in functions like eval() that evaluate strings as mathematical expressions

The expression follows standard mathematical operator precedence where multiplication and division are performed before addition and subtraction. For example, "3+2*2" should return 7 (not 10), and "3/2" should return 1.

The string may contain spaces, which should be ignored during evaluation. Your solution needs to correctly handle the operator precedence and return the final calculated result.

Intuition

The key challenge is handling operator precedence - multiplication and division must be evaluated before addition and subtraction. If we try to evaluate the expression from left to right in a single pass, we'd get incorrect results for expressions like "3+2*2".

Think about how we'd manually evaluate "3+5*2-6/3":

1. First, we'd identify all the multiplication and division operations: 5*2=10 and 6/3=2
2. Then we'd be left with "3+10-2"
3. Finally, we'd evaluate from left to right: 3+10-2=11

This suggests we need a two-phase approach: handle * and / first, then handle + and -. But how can we do this in a single pass?

The insight is to use a stack to defer the final addition/subtraction until we've handled all multiplications and divisions. When we encounter:

• A + or -: We can safely push the number to the stack (with appropriate sign) because these operations have the lowest precedence
• A * or /: We must immediately compute it with the previous number (top of stack) since these have higher precedence

For example, with "3+5*2":

• See 3 with + sign → push 3 to stack: [3]
• See 5 with + sign → push 5 to stack: [3, 5]
• See 2 with * sign → pop 5, compute 5*2=10, push back: [3, 10]
• Sum the stack: 3+10=13

The clever part is tracking the operator that comes before each number. This tells us what to do with that number when we finish reading it. By processing multiplication/division immediately but deferring addition/subtraction to the stack, we naturally handle operator precedence in a single pass.

Solution Approach

We traverse the string s using a stack-based approach. The key variables are:

• stk: A stack to store numbers that will be summed at the end
• v: Current number being built from consecutive digits
• sign: The operator before the current number (initialized as +)

The algorithm works as follows:

1. Iterate through each character in the string:

   • If it's a digit, build the current number: v = v * 10 + int(c)
   • If it's an operator (+-*/) or we've reached the end of the string, process the completed number

2. Process the number based on the previous operator (sign):

   • +: Push the number directly to the stack: stk.append(v)
   • -: Push the negative of the number: stk.append(-v)
   • *: Pop the top element, multiply with current number, push result: stk.append(stk.pop() * v)
   • /: Pop the top element, divide by current number, push result: stk.append(int(stk.pop() / v))

3. Update for next iteration:

   • Set sign to the current operator for the next number
   • Reset v = 0 to start building the next number

4. Return the final result: Sum all elements in the stack

Example walkthrough for "3+5*2-6/3":

• Process 3 with sign +: stack = [3]
• Process 5 with sign +: stack = [3, 5]
• Process 2 with sign *: pop 5, compute 5*2=10, stack = [3, 10]
• Process 6 with sign -: stack = [3, 10, -6]
• Process 3 with sign /: pop -6, compute -6/3=-2, stack = [3, 10, -2]
• Return sum: 3 + 10 + (-2) = 11

The stack naturally handles operator precedence: multiplication and division are computed immediately (modifying the stack top), while addition and subtraction are deferred (just pushing to stack) until the final sum.

Example Walkthrough

Let's walk through the expression "2+3*4-8/2" step by step to see how our stack-based approach handles operator precedence correctly.

Initial Setup:

• stk = [] (empty stack)
• v = 0 (current number being built)
• sign = '+' (initialized as addition)

Step-by-step Process:

1. Character '2': It's a digit, so v = 0 * 10 + 2 = 2

2. Character '+': An operator! Process the number 2 with current sign = '+'

   • Since sign is '+', push 2 to stack → stk = [2]
   • Update sign = '+' for next number
   • Reset v = 0

3. Character '3': It's a digit, so v = 0 * 10 + 3 = 3

4. Character '*': An operator! Process the number 3 with current sign = '+'

   • Since sign is '+', push 3 to stack → stk = [2, 3]
   • Update sign = '*' for next number
   • Reset v = 0

5. Character '4': It's a digit, so v = 0 * 10 + 4 = 4

6. Character '-': An operator! Process the number 4 with current sign = '*'

   • Since sign is '*', pop top element 3, compute 3 * 4 = 12, push result
   • stk = [2, 12]
   • Update sign = '-' for next number
   • Reset v = 0

7. Character '8': It's a digit, so v = 0 * 10 + 8 = 8

8. Character '/': An operator! Process the number 8 with current sign = '-'

   • Since sign is '-', push -8 to stack → stk = [2, 12, -8]
   • Update sign = '/' for next number
   • Reset v = 0

9. Character '2': It's a digit, so v = 0 * 10 + 2 = 2

10. End of string: Process the final number 2 with current sign = '/'

    • Since sign is '/', pop top element -8, compute -8 / 2 = -4, push result
    • stk = [2, 12, -4]

Final Result: Sum all elements in stack: 2 + 12 + (-4) = 10

Notice how multiplication (3*4) and division (-8/2) were computed immediately when we encountered the next operator, while addition and subtraction operations were deferred to the stack. This ensures correct operator precedence without needing multiple passes through the string.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n)

The algorithm iterates through the string s exactly once using a single for loop. For each character, it performs constant time operations:

• Checking if a character is a digit: O(1)
• Updating the value v: O(1)
• Performing stack operations (append/pop): O(1)
• Arithmetic operations (+, -, *, /): O(1)

After the loop, the sum() function iterates through the stack once, which contains at most n elements, adding another O(n) operation. Therefore, the overall time complexity is O(n) + O(n) = O(n).

Space Complexity: O(n)

The main space consumption comes from the stack stk. In the worst case, when the expression contains only addition and subtraction operations (e.g., "1+2+3+4+5"), every number will be pushed onto the stack. Since there can be at most n/2 numbers in a string of length n (considering operators and digits), the stack can grow up to O(n) size. The other variables (v, n, sign, i, c) use constant space O(1). Therefore, the overall space complexity is O(n).

Common Pitfalls

1. Incorrect Handling of Division with Negative Numbers

The Pitfall: The most common mistake is using // (floor division) instead of int(a/b) for integer division. In Python, these behave differently for negative numbers:

• 7 // 2 = 3 and int(7/2) = 3 (same result)
• -7 // 2 = -4 but int(-7/2) = -3 (different results!)

The problem requires truncation toward zero, meaning -7/2 should give -3, not -4.

Incorrect Code:

elif previous_operator == '/':
    stack.append(stack.pop() // current_number)  # Wrong for negative numbers!

Correct Solution:

elif previous_operator == '/':
    stack.append(int(stack.pop() / current_number))  # Truncates toward zero

2. Not Processing the Last Number

The Pitfall: Forgetting to process the last number when the string ends with a digit. The operator processing logic only triggers when encountering an operator, so the final number might be ignored.

Incorrect Code:

for index, char in enumerate(s):
    if char.isdigit():
        current_number = current_number * 10 + int(char)
    if char in '+-*/':  # Missing end-of-string check!
        # Process number...

Correct Solution:

if index == string_length - 1 or char in '+-*/':
    # This ensures the last number is processed

3. Processing Spaces Incorrectly

The Pitfall: Treating spaces as triggers for number processing, which can cause premature evaluation or incorrect operator assignment.

Incorrect Code:

if not char.isdigit() or index == string_length - 1:
    # This would trigger on spaces, causing errors
    if previous_operator == '+':
        stack.append(current_number)
    previous_operator = char  # Space gets assigned as operator!

Correct Solution: Only process when hitting actual operators or end of string, and skip spaces entirely:

if index == string_length - 1 or char in '+-*/':
    # Process number
    # Only update operator if char is actually an operator
    if char in '+-*/':
        previous_operator = char