Leetcode 224. Basic Calculator

Problem

You are given a string representing a mathematical expression containing:

• Non-negative integers
• Addition operator +
• Subtraction operator -
• Opening and closing parentheses ( and )
• Whitespace characters (spaces)

Your task is to evaluate this expression and return the final integer result. The expression is guaranteed to be valid, but you must handle nested parentheses correctly and respect the order of operations (parentheses first, then left-to-right evaluation).

Note that the minus sign can appear as both a binary operator (subtraction) and a unary operator (negation). For example, -(1 + 2) means "negate the result of (1 + 2)".

Requirements

1. Parse and evaluate the expression without using built-in eval functions
2. Handle nested parentheses to arbitrary depth
3. Correctly handle unary minus (negation) when it appears at the start of the expression or after an opening parenthesis
4. Ignore whitespace characters in the input
5. Return the final result as an integer

Constraints

• 1 ≤ s.length ≤ 3 × 10⁵
• The expression contains only digits 0-9, +, -, (, ), and spaces
• The expression is guaranteed to be valid (balanced parentheses, no division by zero)
• All intermediate results fit in a 32-bit signed integer
• Target time complexity: O(n) where n is the length of the string
• Target space complexity: O(n) for the stack

Examples

Example 1:

Input: s = "1 + 1" Output: 2 Explanation: Simple addition of two numbers.

Example 2:

Input: s = " 2-1 + 2 " Output: 3 Explanation: Evaluate left to right: 2 - 1 = 1, then 1 + 2 = 3. Whitespace is ignored.

Example 3:

` Input: s = "(1+(4+5+2)-3)+(6+8)" Output: 23 Explanation:

• Innermost parentheses: (4+5+2) = 11
• Next level: (1+11-3) = 9
• Right group: (6+8) = 14
• Final: 9 + 14 = 23 `

Example 4:

Input: s = "-(1 + 2)" Output: -3 Explanation: Unary minus negates the result of (1 + 2), giving -3.

Hint 1: Stack-Based Approach Consider using a stack to store running totals and signs when you encounter parentheses. When you see an opening parenthesis, push the current result and sign onto the stack. When you see a closing parenthesis, pop from the stack and combine with the current result.

Hint 2: Tracking Sign Maintain a "sign" variable that tracks whether the next number should be added or subtracted. When you encounter a minus sign, flip the sign. For unary minus, the sign should affect everything within the following parentheses.

Hint 3: Building Multi-Digit Numbers Numbers can have multiple digits. Scan consecutive digits to build the complete number before applying the operation. Remember to handle the accumulated number when you encounter an operator, parenthesis, or reach the end of the string.

Full Solution `` Explanation:

The solution uses a stack-based approach to handle nested parentheses:

1. State Variables:

   • result: Accumulates the computed value at the current parenthesis level
   • sign: Tracks whether to add (+1) or subtract (-1) the next number
   • num: Builds multi-digit numbers character by character
   • stack: Stores previous results and signs when entering parentheses

2. Algorithm Flow:

   • For digits: Build the current number by multiplying previous value by 10
   • For '+' or '-': Apply the previous number to result, then update the sign
   • For '(': Push current result and sign to stack, then reset for new level
   • For ')': Complete current level, pop stack, and apply previous context

3. Handling Unary Minus: When we see -(expr), the minus is parsed as an operator that sets sign = -1. Then '(' pushes this sign to the stack. When ')' is encountered, the result inside parentheses is multiplied by this sign.

Time Complexity: O(n) where n is the length of the string, as we process each character once.

Space Complexity: O(n) in the worst case for deeply nested parentheses, where we push to the stack for each opening parenthesis.

def calculate(s: str) -> int:
    """
    Evaluate a mathematical expression with +, -, and parentheses.
    
    Approach:
    - Use a stack to handle nested parentheses
    - Track the current result and sign at each level
    - When we hit '(', push the current state and reset
    - When we hit ')', pop the previous state and apply it
    
    Time: O(n), Space: O(n)
    """
    stack = []  # Stack stores (previous_result, sign_before_parenthesis)
    result = 0  # Current result being computed
    sign = 1    # Current sign: 1 for +, -1 for -
    num = 0     # Current number being built
    
    for char in s:
        if char.isdigit():
            # Build multi-digit numbers
            num = num * 10 + int(char)
            
        elif char == '+':
            # Apply the previous number with its sign
            result += sign * num
            num = 0
            sign = 1  # Next number will be added
            
        elif char == '-':
            # Apply the previous number with its sign
            result += sign * num
            num = 0
            sign = -1  # Next number will be subtracted
            
        elif char == '(':
            # Save current state and reset for the sub-expression
            stack.append(result)
            stack.append(sign)
            result = 0
            sign = 1
            
        elif char == ')':
            # Finalize current level
            result += sign * num
            num = 0
            
            # Pop the sign and previous result
            result *= stack.pop()  # Apply the sign before '('
            result += stack.pop()  # Add the result before '('
            
        # Ignore spaces
    
    # Don't forget the last number
    result += sign * num
    
    return result