LeetCode 224: Basic Calculator Solution in Python Explained

Problem Statement

In LeetCode 224: Basic Calculator, you’re given:

• s: A string representing a valid arithmetic expression with digits, +, -, (, ), and spaces.
• Your task is to return the integer result of evaluating the expression.

The expression follows standard precedence (parentheses first, then left-to-right addition/subtraction). This differs from geometric calculations in LeetCode 223: Rectangle Area, focusing instead on string parsing and arithmetic evaluation.

Constraints

• 1 ≤ s.length ≤ 3 * 10⁵.
• s contains digits, +, -, (, ), and spaces.
• Result fits in a 32-bit integer.
• Expression is valid (no division, multiplication, or invalid syntax).

Examples

Let’s see some cases:

Copy codeInput: s = "1 + 1"
Output: 2
Explanation: 1 + 1 = 2.

Copy codeInput: s = " 2-1 + 2 "
Output: 3
Explanation: 2 - 1 + 2 = 3.

Copy codeInput: s = "(1+(4+5+2)-3)+(6+8)"
Output: 23
Explanation: (1 + (4 + 5 + 2) - 3) + (6 + 8) = 1 + 11 - 3 + 14 = 23.

These examples show we’re evaluating expressions with nested parentheses.

Understanding the Problem

How do we solve LeetCode 224: Basic Calculator in Python? For "(1+(4+5+2)-3)+(6+8)", we need to handle parentheses and compute step-by-step: 1 + (11) - 3 + 14 = 23. A naive approach might process character-by-character without structure, but stacks or recursion handle nesting efficiently. This isn’t a tree counting problem like LeetCode 222: Count Complete Tree Nodes; it’s about parsing and evaluating expressions. We’ll use: 1. Stack-Based Evaluation: O(n) time, O(n) space—our best solution. 2. Recursive Parsing: O(n) time, O(n) space—an alternative.

Let’s dive into the best solution.

Best Solution: Stack-Based Evaluation Approach

Explanation

The Stack-Based Evaluation approach uses stacks to manage nested expressions:

• Use two stacks: one for numbers (num_stack) and one for signs (sign_stack).
• Process the string left-to-right:
• Digits: Build the number.
• + or -: Apply the previous operation, push the new sign.
• (: Push current result and sign, reset for inner expression.
• ): Pop and apply the outer operation.
• At the end, compute the final result.

This runs in O(n) time (single pass through the string) and O(n) space (stacks store up to n elements), making it efficient and practical—our best solution.

For "(1+(4+5+2)-3)+(6+8)", it evaluates step-by-step using stacks.

Step-by-Step Example

Example 1: s = "(1+(4+5+2)-3)+(6+8)"

Goal: Return 23.

• Step 1: Initialize.
• num_stack = [], sign_stack = [], num = 0, result = 0, sign = 1.
• Step 2: Process each character.
• (: Push result=0, sign=1, reset result=0, sign=1.
• Stacks: num=[0], sign=[1].
• 1: num=1.
• +: result=0+1*1=1, num=0, sign=1.
• (: Push result=1, sign=1, reset result=0, sign=1.
• Stacks: num=[0,1], sign=[1,1].
• 4: num=4.
• +: result=0+1*4=4, sign=1.
• 5: num=5.
• +: result=4+1*5=9, sign=1.
• 2: num=2.
• ): result=9+1*2=11, pop result=1+1*11=12, sign=1.
• Stacks: num=[0], sign=[1].
• -: result=12+1*0=12, sign=-1.
• 3: num=3.
• ): result=12-1*3=9, pop result=0+1*9=9, sign=1.
• Stacks: empty.
• +: result=9+1*0=9, sign=1.
• (: Push result=9, sign=1, reset result=0, sign=1.
• 6: num=6.
• +: result=0+1*6=6, sign=1.
• 8: num=8.
• ): result=6+1*8=14, pop result=9+1*14=23, sign=1.
• Step 3: Final result.
• result=23+1*0=23.
• Output: 23.

Example 2: s = "2-1"

Goal: Return 1.

• Step 1: num_stack=[], sign_stack=[], result=0, sign=1.
• Step 2:
• 2: num=2.
• -: result=0+1*2=2, sign=-1.
• 1: num=1.
• End: result=2-1*1=1.
• Output: 1.

How the Code Works (Stack-Based Evaluation) – Detailed Line-by-Line Explanation

Here’s the Python code with a detailed breakdown:

Copy codedef calculate(s: str) -> int:
    # Line 1: Initialize variables
    num_stack = []
    # Stack for intermediate results (e.g., [])
    sign_stack = []
    # Stack for signs (e.g., [])
    result = 0
    # Current result (e.g., 0)
    sign = 1
    # Current sign (e.g., 1)
    num = 0
    # Current number being built (e.g., 0)

    # Line 2: Process each character
    for char in s:
        # Iterate string (e.g., char='1')
        if char.isdigit():
            # Digit (e.g., '4')
            num = num * 10 + int(char)
            # Build number (e.g., 0*10+4=4)
        elif char in '+-':
            # Operator (e.g., '+')
            result += sign * num
            # Apply previous operation (e.g., 0+1*1=1)
            num = 0
            # Reset number (e.g., 0)
            sign = 1 if char == '+' else -1
            # Set new sign (e.g., 1)
        elif char == '(':
            # Start nested expression (e.g., '(')
            num_stack.append(result)
            # Save current result (e.g., 1)
            sign_stack.append(sign)
            # Save current sign (e.g., 1)
            result = 0
            # Reset result (e.g., 0)
            sign = 1
            # Reset sign (e.g., 1)
        elif char == ')':
            # End nested expression (e.g., ')')
            result += sign * num
            # Compute inner result (e.g., 9+1*2=11)
            num = 0
            # Reset number (e.g., 0)
            result = num_stack.pop() + sign_stack.pop() * result
            # Apply outer operation (e.g., 1+1*11=12)

    # Line 3: Handle remaining number
    result += sign * num
    # Add final number (e.g., 23+1*0=23)

    # Line 4: Return result
    return result
    # Final value (e.g., 23)

This solution efficiently handles nested expressions with stacks.

Alternative: Recursive Parsing Approach

Explanation

The Recursive Parsing approach uses recursion for parentheses:

• Parse the string with an index:
• Numbers: Build and add/subtract based on sign.
• Parentheses: Recursively compute the inner expression.
• Return the final result.

It’s O(n) time (single pass) and O(n) space (recursion stack), elegant but slightly less intuitive.

Step-by-Step Example

For "1+(4+5)":

• i=0: result=1, sign=1.
• i=1: +.
• i=2: (: Recurse.
• i=3: result=4, sign=1.
• i=4: +.
• i=5: result=4+5=9, return 9.
• i=6: result=1+9=10.
• Output: 10.

How the Code Works (Recursive)

Copy codedef calculateRecursive(s: str) -> int:
    def evaluate(i):
        result = 0
        sign = 1
        num = 0
        while i < len(s):
            char = s[i]
            if char.isdigit():
                num = num * 10 + int(char)
            elif char in '+-':
                result += sign * num
                num = 0
                sign = 1 if char == '+' else -1
            elif char == '(':
                num, next_i = evaluate(i + 1)
                result += sign * num
                i = next_i
            elif char == ')':
                result += sign * num
                return result, i
            i += 1
        result += sign * num
        return result, i

    result, _ = evaluate(0)
    return result

Complexity

• Stack-Based Evaluation:
• Time: O(n) – single pass.
• Space: O(n) – stacks.
• Recursive Parsing:
• Time: O(n) – single pass.
• Space: O(n) – recursion stack.

Efficiency Notes

Stack-Based Evaluation is our best solution with O(n) time and clear iterative logic, avoiding recursion overhead. Recursive Parsing is elegant but less common in practice.

Key Insights

• Stacks: Manage nesting.
• Parentheses: Alter evaluation order.
• Sign: Tracks operation.

Additional Example

For "3-(2+1)":

• Stack: 3-3=0.
• Recursive: Same result.

Edge Cases

• Simple: "1", 1.
• Nested: "(1)", 1.
• Spaces: Ignored.

Both handle these well.

Final Thoughts

LeetCode 224: Basic Calculator in Python is a rewarding parsing challenge. Stack-Based Evaluation excels in efficiency, while Recursive Parsing offers elegance. Want more? Try LeetCode 227: Basic Calculator II or LeetCode 772: Basic Calculator III. Test your skills—Solve LeetCode 224 on LeetCode with "(1+(4+5+2)-3)+(6+8)" (expecting 23)—evaluate that expression today!