basic calculator 2 leetcode

Unraveling LeetCode's Basic Calculator II: A Masterclass in Expression Parsing

Welcome, fellow problem-solvers and aspiring developers! Today, we're diving deep into a classic LeetCode challenge: "Basic Calculator II" (Problem 227). This problem serves as an excellent test of your understanding of expression parsing, operator precedence, and efficient algorithm design. While it might seem straightforward at first glance, correctly handling the order of operations without relying on built-in eval() functions requires a thoughtful approach.

Before we jump into the intricacies, feel free to try out our interactive calculator above, which implements the solution we're about to discuss!

The Challenge: Basic Calculator II

The core task is to evaluate a string expression s that contains non-negative integers, the operators +, -, *, /, and spaces. The key constraint is that integer division should truncate toward zero. Crucially, you cannot use any built-in library functions that evaluate mathematical expressions (like eval() in JavaScript or Python).

Example:

• "3 + 2 * 2" should evaluate to 7 (2 * 2 = 4, then 3 + 4 = 7)
• " 3 / 2 " should evaluate to 1 (integer division)
• " 3 + 5 / 2 " should evaluate to 5 (5 / 2 = 2, then 3 + 2 = 5)

Why is this Tricky? Operator Precedence!

The main difficulty lies in respecting the order of operations: multiplication and division must be performed before addition and subtraction. If we simply process the expression from left to right, we'd get incorrect results. For instance, 3 + 2 * 2 would become (3 + 2) * 2 = 10 if processed linearly, instead of the correct 3 + (2 * 2) = 7.

The Stack-Based Approach: Our Elegant Solution

To correctly handle operator precedence, a common and highly effective strategy is to use a stack. The idea is to process the expression character by character, keeping track of numbers and applying operations strategically. Here's the breakdown of our algorithm:

Algorithm Steps:

1. Initialization:
   • Create an empty stack to store intermediate numbers.
   • Initialize currentNumber = 0 to build multi-digit numbers.
   • Initialize operation = '+' as the default or "previous" operator. This helps handle the first number correctly.
2. Iterate Through the Expression:
   • Loop through each character char in the input string s.
   • If char is a digit: Append it to currentNumber. For example, if currentNumber is 1 and char is '2', currentNumber becomes 12.
   • If char is an operator (+, -, *, /) or if we've reached the end of the string: This signifies that currentNumber is complete and we need to apply the operation that preceded it.
     • Based on the operation:
       • If operation == '+': Push currentNumber onto the stack.
       • If operation == '-': Push -currentNumber onto the stack.
       • If operation == '*': Pop the top element from the stack, multiply it by currentNumber, and push the result back onto the stack.
       • If operation == '/': Pop the top element from the stack, perform integer division (Math.trunc()) by currentNumber, and push the result back onto the stack.
     • Update operation to the current char (this becomes the operator for the next number).
     • Reset currentNumber = 0 for the next number.
   • Skip Spaces: If char is a space, simply ignore it unless it's part of an operator/number parsing logic (which our current logic handles implicitly by only acting on digits or operators).
3. Final Calculation: After iterating through the entire string, the stack will contain numbers that are effectively ready for simple addition. Sum all elements in the stack to get the final result.

Example Walkthrough: "3 + 2 * 2 - 6 / 3"

Let's trace how our algorithm handles the expression 3 + 2 * 2 - 6 / 3.

s = "3 + 2 * 2 - 6 / 3"
stack = []
currentNumber = 0
operation = '+'

• '3': currentNumber = 3
• ' ': Skip
• '+': (End of number '3', previous operation was '+')
  • stack.push(3) -> stack = [3]
  • operation = '+'
  • currentNumber = 0
• ' ': Skip
• '2': currentNumber = 2
• ' ': Skip
• '*': (End of number '2', previous operation was '+')
  • stack.push(2) -> stack = [3, 2]
  • operation = '*'
  • currentNumber = 0
• ' ': Skip
• '2': currentNumber = 2
• ' ': Skip
• '-': (End of number '2', previous operation was '*')
  • operand1 = stack.pop() (which is 2)
  • result = operand1 * currentNumber (2 * 2 = 4)
  • stack.push(4) -> stack = [3, 4]
  • operation = '-'
  • currentNumber = 0
• ' ': Skip
• '6': currentNumber = 6
• ' ': Skip
• '/': (End of number '6', previous operation was '-')
  • stack.push(-6) -> stack = [3, 4, -6] (Note: -6 because the operation was '-')
  • operation = '/'
  • currentNumber = 0
• ' ': Skip
• '3': currentNumber = 3
• (End of string): (End of number '3', previous operation was '/')
  • operand1 = stack.pop() (which is -6)
  • result = Math.trunc(operand1 / currentNumber) (Math.trunc(-6 / 3) = -2)
  • stack.push(-2) -> stack = [3, 4, -2]
  • operation = char (no effect as loop ends)
  • currentNumber = 0

Final Summation:

result = 0
result += stack.pop() // -2 -> result = -2
result += stack.pop() // 4  -> result = 2
result += stack.pop() // 3  -> result = 5

The final result is 5. This matches the expected output for 3 + 2 * 2 - 6 / 3 which is 3 + 4 - 2 = 5. The key insight here is that + and - operations simply push numbers (or their negatives) onto the stack, while * and / immediately operate on the most recent number on the stack.

JavaScript Implementation

Here's the JavaScript code implementing this stack-based approach. This is the same logic powering the interactive calculator above.

function calculateLeetCodeBasicII(s) {
    s = s.trim(); // Remove leading/trailing spaces
    if (s.length === 0) return 0;

    const stack = [];
    let currentNumber = 0;
    let operation = '+'; // Default operation for the first number

    for (let i = 0; i < s.length; i++) {
        const char = s[i];

        // 1. Build currentNumber if char is a digit
        if (char >= '0' && char <= '9') {
            currentNumber = currentNumber * 10 + parseInt(char);
        }

        // 2. Process operator or end of string
        // This condition checks if char is an operator OR if it's the last character
        // AND char is not a space (so we don't accidentally process a space as an operator)
        if ((!/\s/.test(char) && (char === '+' || char === '-' || char === '*' || char === '/')) || i === s.length - 1) {
            if (operation === '+') {
                stack.push(currentNumber);
            } else if (operation === '-') {
                stack.push(-currentNumber);
            } else if (operation === '*') {
                stack.push(stack.pop() * currentNumber);
            } else if (operation === '/') {
                const prevNum = stack.pop();
                // Handle division by zero
                if (currentNumber === 0) {
                    throw new Error("Division by zero is not allowed.");
                }
                stack.push(Math.trunc(prevNum / currentNumber));
            }
            // Update the operation for the next number
            operation = char;
            // Reset currentNumber for the next number
            currentNumber = 0;
        }
    }

    // 3. Sum up all numbers in the stack
    let result = 0;
    while (stack.length > 0) {
        result += stack.pop();
    }

    return result;
}

Complexity Analysis

• Time Complexity: O(N), where N is the length of the input string s. We iterate through the string once. Each character is processed in constant time.
• Space Complexity: O(N), in the worst case. The stack could potentially store all numbers if the expression consists only of additions and subtractions (e.g., 1+1+1+...).

Conclusion

The Basic Calculator II problem is a fantastic exercise in understanding operator precedence and implementing efficient parsing logic. The stack-based approach provides an elegant and robust solution, demonstrating how a simple data structure can tame complex expression evaluation. Mastering such problems is crucial for anyone looking to build parsers, compilers, or even just improve their algorithmic thinking. Keep practicing, keep coding, and keep building!