Leetcode 227. Basic Calculator II

Let's trace through a concrete example: given the string '3+2*2', we need to evaluate it correctly.

If we just compute left-to-right, we'd get (3+2)*2 = 10, but that's wrong! The correct answer is 3+(2*2) = 7 because multiplication has higher precedence than addition.

Let's trace step-by-step: we see '3' (a number), then '+' (an operator), then '2' (another number), then '*' (higher precedence operator!), then '2' (final number). We must compute 2*2=4 first, then add 3+4=7.

Key constraints: No parentheses in the input, only +, -, *, / operators allowed, division truncates toward zero (so 7/2=3, not 3.5), and spaces may appear anywhere.

Edge cases: What about '42+8' (multi-digit numbers)? What about ' 3 + 2 ' (spaces around numbers)? What about '14/3*2' (multiple operations of same precedence - should evaluate left-to-right: (14/3)*2 = 4*2 = 8)?

When we encounter + or -, we can't immediately compute the result because the next operator might have higher precedence.

For example, in 3+2*5, when we see +, we can't compute 3+2 yet because * comes next and must be done first. But when we see * or /, we can immediately apply it to the previous number because no operator has higher precedence.

This suggests we need to remember pending operations that can't be computed yet. When we see 3+2*5, we should save +3 for later, then compute 2*5=10, then finally add 3+10=13.

The key insight: * and / can be computed immediately with the previous number, while + and - must wait until we've resolved all higher-precedence operations that follow.

Imagine reading the expression left-to-right and maintaining a running list of numbers to sum at the end:

• For 3+2*5: Start with [3]. See +, so next number will be added → but wait, see * next! Compute 2*5=10 first → list becomes [3, 10] → final sum is 13
• For 6-3/2: Start with [6]. See -, so next number will be subtracted → but wait, see / next! Compute 3/2=1 first → list becomes [6, -1] → final sum is 5

The pattern: accumulate numbers (applying * and / immediately), then sum everything at the end.

Parse the string character by character, building numbers and tracking the last operator seen. When we encounter * or /, immediately apply it to the last number pushed (by popping and pushing the result). For + and -, push the number as-is (or its negation). This way, all multiplication and division are resolved during parsing, and the final result is the sum of all numbers in the stack. This respects operator precedence without needing multiple passes or complex parsing.

def calculate(s):
    """
    Evaluate arithmetic expression with +, -, *, / operators.
    Respects operator precedence without using eval.
    """
    # Initialize stack and tracking variables
    stack = []
    current_number = 0
    last_operator = '+'
    
    # Parse expression character by character
    for i, char in enumerate(s):
        # Build multi-digit numbers
        if char.isdigit():
            current_number = current_number * 10 + int(char)
        
        # Process operator or end of string
        if char in '+-*/' or i == len(s) - 1:
            # Apply last operator with current number
            if last_operator == '+':
                stack.append(current_number)
            elif last_operator == '-':
                stack.append(-current_number)
            elif last_operator == '*':
                stack.append(stack.pop() * current_number)
            elif last_operator == '/':
                # Truncate toward zero
                stack.append(int(stack.pop() / current_number))
            
            # Update operator and reset number
            if char in '+-*/':
                last_operator = char
            current_number = 0
    
    # Sum all values in stack
    result = sum(stack)
    return result

• Stack for operator precedence: Use a stack to handle operator precedence without recursion by immediately evaluating high-precedence operations (* and /) while deferring low-precedence ones (+, -). Push positive numbers for addition, negative numbers for subtraction, and immediately compute and push results for multiplication/division - this naturally respects precedence when you sum the stack at the end.
• State tracking with previous operator: Maintain a `prevOperator` variable (initialized to '+') to determine how to process the current number. This delayed processing pattern lets you decide whether to push, negate, multiply, or divide based on the operator that *precedes* each number, not follows it - critical for handling the last number correctly.
• Character-by-character parsing with number accumulation: Build multi-digit numbers by accumulating digits (`num = num * 10 + digit`) as you iterate, then process the complete number when you encounter an operator or reach the end of the string. This handles variable-length integers without tokenization overhead.
• End-of-string boundary handling: Treat the end of the string as an implicit operator trigger by checking `i == len(s) - 1` alongside operator detection. This common pitfall - forgetting to process the last accumulated number - causes off-by-one errors since there's no trailing operator to trigger processing.
• Space complexity optimization through immediate evaluation: By evaluating * and / operations immediately and pushing results to the stack (rather than pushing operators), you keep stack size O(n) worst-case but typically much smaller. This contrasts with postfix conversion approaches that require storing all operators separately.
• Expression parsing pattern for DSLs: This stack-based precedence handling extends to parsing any expression language (configuration files, formula evaluators, query languages) where you need to respect operator precedence without building a full abstract syntax tree - useful for building calculators, spreadsheet engines, or rule evaluation systems.