Leetcode 224. Basic Calculator

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.

Now consider '(1+(4+5+2)-3)+(6+8)'. We must handle nested parentheses correctly: innermost first (4+5+2)=11, then (1+11-3)=9, then (6+8)=14, finally 9+14=23.

Key constraints: The expression contains only digits 0-9, operators + and -, parentheses ( and ), and spaces. Unary minus is allowed (e.g., '-2+3' should return 1).

Edge cases: What about '- (3 + (4 + 5))' (unary minus before parentheses)? What about '1 - (-2)' (unary minus inside parentheses)? What about nested expressions like '((2))'?

When we encounter a '(', we're starting a new sub-expression that must be evaluated independently. When we hit the matching ')', we've completed that sub-expression.

This creates a nested structure where inner expressions must be resolved before outer ones. The key insight: we need to remember the context (current sum and sign) when entering a sub-expression, then restore it when exiting.

Without parentheses, we could just scan left-to-right keeping a running sum. But parentheses create nested scopes where we must pause our current calculation, evaluate the inner part, then resume.

The most recently opened parenthesis must be matched with the next closing parenthesis we encounter - this 'last-in, first-out' pattern is crucial for handling arbitrary nesting depth.

Imagine evaluating '2 + (3 - (4 + 5))' step by step:

1. We're computing 2 + ... when we hit '(' - we need to pause and remember 'we were adding to 2'
2. Now computing 3 - ... when we hit another '(' - pause again and remember 'we were subtracting from 3'
3. Compute 4 + 5 = 9, hit ')' - resume the previous context: 3 - 9 = -6
4. Hit another ')' - resume the outermost context: 2 + (-6) = -4

We need a way to save and restore these contexts in reverse order of how we encountered them.

Use a stack to handle nested parentheses and maintain calculation state. Scan the string character by character, building numbers digit by digit. When we encounter an operator or parenthesis, process the previous number with its sign. For opening parentheses, push the current result and sign onto the stack (saving context). For closing parentheses, pop from the stack to restore the previous context and combine it with the sub-expression result. This naturally handles arbitrary nesting depth and unary minus.

def calculate(s):
    """
    Evaluate string expression with +, -, parentheses, spaces, and unary minus.
    Uses stack to handle nested parentheses and maintain calculation state.
    """
    # Initialize stack and variables
    stack = []
    current_number = 0
    current_result = 0
    sign = 1
    
    # Process each character
    for i, char in enumerate(s):
        # Build multi-digit numbers
        if char.isdigit():
            current_number = current_number * 10 + int(char)
        
        # Handle operators and parentheses
        elif char == '+':
            current_result += sign * current_number
            current_number = 0
            sign = 1
        
        elif char == '-':
            current_result += sign * current_number
            current_number = 0
            sign = -1
        
        elif char == '(':
            # Push current state to stack
            stack.append(current_result)
            stack.append(sign)
            # Reset for sub-expression
            current_result = 0
            sign = 1
        
        elif char == ')':
            # Complete current number
            current_result += sign * current_number
            current_number = 0
            # Pop sign and previous result
            current_result *= stack.pop()
            current_result += stack.pop()
            sign = 1
    
    # Add final number
    current_result += sign * current_number
    
    return current_result

• Stack for state preservation in nested contexts: Use a stack to save and restore sign and accumulated result when entering/exiting parentheses - the stack naturally handles nested scopes by pushing current state before '(' and popping to restore when encountering ')', making it perfect for expression evaluation with arbitrary nesting depth.
• Sign propagation technique: Maintain a running sign variable that multiplies with the stack's top sign when processing operators - this elegantly handles both unary minus (like "-(3+5)") and sign changes through nested parentheses by treating signs as multiplicative state rather than trying to parse them structurally.
• Character-by-character parsing with lookahead: Build multi-digit numbers by accumulating digits (num = num * 10 + digit) and only apply operations when hitting a non-digit operator or end of string - this avoids complex tokenization while correctly handling numbers of any length without splitting them prematurely.
• Deferred operation pattern: Store the previous operator and only apply it when you encounter the next operator or closing parenthesis - this prevents off-by-one errors and naturally handles the last number in an expression without special-case logic at the end.
• O(n) single-pass with O(n) space: The stack only stores state at parenthesis boundaries (not every character), making space proportional to nesting depth in practice, while the single left-to-right pass ensures linear time - this is optimal since you must read every character at least once.
• Expression parser foundation: This stack-based state management pattern extends to building recursive descent parsers, AST evaluators, and formula engines in spreadsheets or calculators - understanding sign propagation and operator precedence handling here is fundamental to compiler design and expression evaluation systems.