LeetCode 227: Basic Calculator II Solution in Python – A Step-by-Step Guide

What Is LeetCode 227: Basic Calculator II?

In LeetCode 227: Basic Calculator II, you’re given a string containing numbers and operators (+, -, *, /) and must compute the result. Unlike LeetCode 224: Basic Calculator, which includes parentheses, this problem focuses on basic operations with operator precedence (multiplication and division before addition and subtraction).

Problem Statement

• Input: A string s with numbers and operators (+, -, *, /).
• Output: An integer result of the expression.
• Rules:
• No parentheses.
• Evaluate * and / before + and -.
• Division truncates toward zero.

Constraints

• String length: 1 to 10^5.
• Numbers: 0 to 2^31 - 1.
• No leading zeros or invalid expressions.

Examples

• Input: "3+2*2"
• Output: 7 (2*2 = 4, then 3+4 = 7).
• Input: " 3/2 "
• Output: 1 (3/2 = 1, truncated).
• Input: " 3+5 / 2 "
• Output: 5 (5/2 = 2, then 3+2 = 5).

Understanding the Problem: Evaluating Expressions

To solve LeetCode 227: Basic Calculator II in Python, we need to process a string while respecting operator precedence. This isn’t a tree manipulation task like LeetCode 226: Invert Binary Tree—it’s about parsing and computing. We’ll use two approaches: 1. Best Solution (Stack-Based): O(n) time, O(n) space—handles precedence efficiently. 2. Alternative Solution (Two-Pass without Stack): O(n) time, O(1) space—processes high-priority operations first.

Let’s dive into the best solution.

Best Solution: Stack-Based Approach for Basic Calculator II

Why This Is the Best Solution

The stack-based approach is our top pick for LeetCode 227 because it processes the string in a single pass, uses a stack to defer addition and subtraction, and handles multiplication and division on the fly. It’s efficient, intuitive, and perfect for managing operator precedence.

How It Works

• Use a stack to store numbers.
• Parse the string character by character:
• For + or -, push the current number with its sign onto the stack.
• For * or /, compute immediately with the stack’s top number and push the result.
• Sum the stack at the end.

Step-by-Step Example

Example 1: "3+2*2"

• Stack: [], num = 0, sign = +.
• ‘3’: num = 3.
• ‘+’: Push 3 (sign +), num = 0, sign = +.
• ‘2’: num = 2.
• ‘*’: num = 2.
• ‘2’: Compute 2*2 = 4, push 4.
• End: Stack = [3, 4], sum = 7.

Example 2: "3+5/2"

• Stack: [], num = 0, sign = +.
• ‘3’: num = 3.
• ‘+’: Push 3, num = 0, sign = +.
• ‘5’: num = 5.
• ‘/’: num = 5.
• ‘2’: Compute 5/2 = 2, push 2.
• End: Stack = [3, 2], sum = 5.

Code with Detailed Line-by-Line Explanation

Here’s the Python implementation:

Copy codeclass Solution:
    def calculate(self, s: str) -> int:
        # Line 1: Initialize variables
        stack = []  # Store numbers for later addition
        num = 0     # Current number being built
        sign = '+'  # Previous operator, default to '+'

        # Line 2: Process each character in the string
        for i in range(len(s)):
            char = s[i]

            # Line 3: Build number from digits
            if char.isdigit():
                num = num * 10 + int(char)  # e.g., '12' -> 12

            # Line 4: Handle operators or end of string
            if char in '+-*/' or i == len(s) - 1:
                # Line 5: Process previous operation
                if sign == '+':
                    stack.append(num)
                elif sign == '-':
                    stack.append(-num)
                elif sign == '*':
                    stack.append(stack.pop() * num)  # Pop and multiply
                elif sign == '/':
                    # Handle division with truncation toward zero
                    stack.append(int(stack.pop() / num))  # e.g., 5/2 = 2

                # Line 6: Reset num and update sign
                num = 0
                sign = char if char in '+-*/' else '+'

        # Line 7: Return sum of stack
        return sum(stack)

• Time Complexity: O(n) – single pass through the string.
• Space Complexity: O(n) – stack stores numbers.

Alternative Solution: Two-Pass Approach without Stack

Why an Alternative Approach?

The two-pass approach avoids a stack by first handling high-precedence operations (* and /) and then computing the remaining additions and subtractions. It’s space-efficient and offers a fresh way to tackle the problem.

How It Works

• Pass 1: Compute * and /, storing intermediate results and signs.
• Pass 2: Sum the results with + and -.
• Use a list or variables to track numbers and operators.

Step-by-Step Example

Example: "3+5/2"

• Pass 1:
• “3+”: Store 3, sign +.
• “5/2”: Compute 5/2 = 2, store 2.
• Pass 2: 3 + 2 = 5.
• Result: 5.

Code for Two-Pass Approach

Copy codeclass Solution:
    def calculate(self, s: str) -> int:
        # Pass 1: Handle * and /
        nums = []
        ops = []
        num = 0

        for i in range(len(s)):
            char = s[i]
            if char.isdigit():
                num = num * 10 + int(char)
            if char in '+-*/' or i == len(s) - 1:
                if ops and ops[-1] in '*/':
                    prev_num = nums.pop()
                    if ops.pop() == '*':
                        num = prev_num * num
                    else:
                        num = int(prev_num / num)
                nums.append(num)
                if char in '+-':
                    ops.append(char)
                num = 0

        # Pass 2: Handle + and -
        result = nums[0]
        for i in range(1, len(nums)):
            if ops[i-1] == '+':
                result += nums[i]
            else:
                result -= nums[i]

        return result

• Time Complexity: O(n) – two passes through the string.
• Space Complexity: O(n) – stores numbers and operators (could optimize to O(1) with pointers).

Comparing the Two Solutions

• Best Solution (Stack-Based):
• Pros: Single pass, clear precedence handling.
• Cons: Uses O(n) space.
• Alternative Solution (Two-Pass):
• Pros: Can optimize space, explicit steps.
• Cons: Two passes, more complex logic.

The stack-based method is our best for its simplicity and efficiency.

Additional Examples and Edge Cases

Single Number

• Input: "42"
• Output: 42
• Both return the number directly.

All Operations

• Input: "1+2*3-4/2"
• Output: 5 (2*3 = 6, 4/2 = 2, 1+6-2 = 5).
• Both handle correctly.

Spaces

• Input: " 3 + 5 "
• Output: 8
• Both ignore spaces.

Complexity Breakdown

• Stack-Based:
• Time: O(n).
• Space: O(n).
• Two-Pass:
• Time: O(n).
• Space: O(n) (optimizable to O(1)).

Both are time-efficient; stack-based is simpler.

Key Takeaways for Beginners

• Precedence: * and / before + and -.
• Stack-Based: Defers low-priority operations.
• Two-Pass: Separates high and low priority.
• Python Tip: String parsing is key—see [Python Basics](/python/basics).

Final Thoughts: Crunch Numbers Like a Pro

LeetCode 227: Basic Calculator II in Python is a great way to practice string parsing and operator precedence. The stack-based solution offers a sleek, single-pass approach, while the two-pass method provides a space-conscious alternative. Want more calculator fun? Try LeetCode 224: Basic Calculator or LeetCode 20: Valid Parentheses. Ready to calculate? Head to Solve LeetCode 227 on LeetCode and compute away!