LeetCode Solutions Blog

Basic Calculator

Number: 224

Difficulty: Hard

Paid? No

Problem Description

Evaluate a valid mathematical expression given as a string containing non-negative integers, '+', '-', parentheses, and spaces. The expression may include nested parentheses and unary negatives, and must be computed without using built-in evaluation functions.

Key Insights

Use a stack to save previous results and signs when encountering parentheses.
Process the string left-to-right by accumulating multi-digit numbers and applying the current sign.
When encountering a '(', push the current result and sign onto the stack and reset them.
When encountering a ')', complete the current sub-expression then pop the previous state to incorporate the computed value.
Handle whitespaces by simply skipping them.

Space and Time Complexity

Time Complexity: O(n) where n is the length of the input string, since we process each character once. Space Complexity: O(n) in the worst-case scenario due to the use of a stack for nested parentheses.

Solution

The solution uses an iterative approach with a stack:

Initialize variables: result to keep the running total, sign to handle addition/subtraction, and index to iterate over the string.
As you iterate, build multi-digit numbers by checking for consecutive numerical characters.
Adjust the total by adding the product of the current number and its sign.
When encountering a '(', push the current result and sign onto the stack, then reset results and sign for the new sub-expression.
When encountering a ')', complete the sub-expression by popping the previous result and sign, then combine.
Skip over spaces.
The final result is the computed value after the end of the string.

This approach effectively simulates recursion and correctly handles nested expressions and negation.

Code Solutions

# Python solution for the Basic Calculator problem

def calculate(s: str) -> int:
    # Stack to store pairs of (current result, current sign) before a '('
    stack = []
    result = 0  # Running total
    number = 0  # Current number being processed
    sign = 1    # Current sign (1 or -1)
    
    # Iterate through each character in the string
    for char in s:
        if char.isdigit():
            # Build number digit by digit 
            number = number * 10 + int(char)
        elif char in "+-":
            # Add the complete number with its sign to result
            result += sign * number
            # Reset number for the next potential number
            number = 0
            # Update the sign based on the operator
            sign = 1 if char == '+' else -1
        elif char == '(':
            # Push the current result and sign onto the stack
            stack.append(result)
            stack.append(sign)
            # Reset result and sign for the new sub-expression
            result = 0
            sign = 1
        elif char == ')':
            # Complete the number before the parentheses close
            result += sign * number
            number = 0
            # The top of the stack is the sign before the parenthesis
            prev_sign = stack.pop()
            # The next value on the stack is the result before the parenthesis
            prev_result = stack.pop()
            # Combine the result of the previous expression with the sub-expression evaluated
            result = prev_result + prev_sign * result
        # Skip spaces implicitly when no if condition is met

    # Add any number left after the loop ends
    result += sign * number
    return result

# Example usage:
print(calculate("1 + 1"))  # Expected output: 2
print(calculate(" 2-1 + 2 "))  # Expected output: 3
print(calculate("(1+(4+5+2)-3)+(6+8)"))  # Expected output: 23