Basic Calculator II

LeetCode 227: Basic Calculator II Solution & Explanation

Problem Overview

TL;DR: By utilizing a stack to store additive terms and resolving multiplicative operations immediately upon discovery, we can evaluate the expression in a single linear pass.

The LeetCode 227 problem, known as Basic Calculator II, asks us to evaluate a string expression containing non-negative integers and the operators +, -, *, and /. The evaluation must respect the standard order of operations (operator precedence), meaning multiplication and division must be performed before addition and subtraction. We are not allowed to use built-in evaluation functions like eval().

Brute Force Approach for Basic Calculator II

A naive or brute force approach to solving Basic Calculator II often involves recursively searching for the operator with the lowest precedence to split the expression.

1. Scan the entire string to find the last occurrence of + or -.
2. Split the string into a left and right part and recursively evaluate both.
3. If no + or - exists, scan for * or / and split similarly.
4. If no operators exist, parse the number.

Pseudo-code

function solve(expression):
    if expression is just a number: return parsed number
    
    // Find split point (lowest precedence, rightmost)
    idx = find_last_plus_or_minus(expression)
    if idx != -1:
        return solve(left_part) + solve(right_part) (or -)
        
    idx = find_last_mul_or_div(expression)
    return solve(left_part) * solve(right_part) (or /)

Time Complexity: $O(N^2)$. In the worst case (e.g., 1+2+3+...), the algorithm scans the string linearly to find the split point, performs the split, and recurses. This repeated scanning leads to quadratic time complexity. Why it fails: While semantically correct, this approach effectively constructs an Abstract Syntax Tree (AST) implicitly through recursion. For constraints where string length s is up to $3 \cdot 10^5$, an $O(N^2)$ solution will result in a Time Limit Exceeded (TLE) error.

Algorithm Strategy: Stack Patterns

1. State Maintenance: We maintain a stack to hold integers. We also need a currentNumber variable to build multi-digit numbers from characters, and a lastOperator variable to store the operator immediately preceding the current number.
2. Initialization: Initialize lastOperator to +. This is a trick to treat the first number as a positive term (e.g., 3... becomes 0 + 3...).
3. Iteration: Traverse the string character by character.
   • If the character is a digit, update currentNumber (handle currentNumber * 10 + digit).
   • If the character is an operator or we have reached the end of the string:
     • Check lastOperator (the operator before the current number).
     • If +: Push currentNumber to stack.
     • If -: Push -currentNumber to stack.
     • If *: Pop the top element, multiply by currentNumber, push result.
     • If /: Pop the top element, divide by currentNumber (truncating towards zero), push result.
     • Update lastOperator to the current character.
     • Reset currentNumber to 0.
4. Final Aggregation: The stack now contains all additive terms. Sum the elements in the stack to get the final result.

Execution Flow

Consider the input s = "3+2*2".

1. Init: stack = [], lastOp = '+', currNum = 0.
2. Process '3': It's a digit. currNum becomes 3.
3. Process '+': It's an operator.
   • Check lastOp (+). Push 3 to stack. stack = [3].
   • Update lastOp to +. Reset currNum to 0.
4. Process '2': It's a digit. currNum becomes 2.
5. Process '*': It's an operator.
   • Check lastOp (+). Push 2 to stack. stack = [3, 2].
   • Update lastOp to *. Reset currNum to 0.
6. Process '2': It's a digit. currNum becomes 2.
7. End of String: Treat as if we hit a delimiter.
   • Check lastOp (*).
   • Pop top (2). Calculate 2 * 2 = 4.
   • Push 4. stack = [3, 4].
8. Result: Sum stack 3 + 4 = 7.

Proof of Correctness

The algorithm correctly implements operator precedence by ensuring that multiplication and division bind tighter than addition and subtraction.

• Invariant: At any point, the stack contains terms that are meant to be added together.
• When we encounter * or /, we effectively "merge" the current number with the last term on the stack. This prevents the previous term from being added to the overall sum until the higher-precedence operation is complete.
• When we encounter + or -, we "seal" the previous number as a complete term and push it, making it available for future addition.
• Since standard math is associative for addition (a + b) + c = a + (b + c), deferring the sum until the end produces the correct result.

Pattern Reuse Notes

The Stack - Expression Evaluation pattern is highly versatile and appears in several popular interview questions.

• LeetCode 150: Evaluate Reverse Polish Notation - Uses a stack to evaluate Postfix expressions directly. Simpler than 227 as precedence is already handled by the notation.
• LeetCode 224: Basic Calculator - Handles parentheses () and +/-. Requires handling nested contexts, often by pushing the current local sum onto the stack when ( is found.
• LeetCode 772: Basic Calculator III - The ultimate variation combining precedence (*, /) and parentheses (). This requires a robust application of the stack pattern or conversion to RPN.

Reference Implementation

C++ Solution for LeetCode 227

1class Solution {
2public:
3    int calculate(string s) {
4        stack<int> myStack;
5        char lastOp = '+';
6        int currentNumber = 0;
7        int n = s.length();
8        
9        for (int i = 0; i < n; ++i) {
10            char c = s[i];
11            
12            if (isdigit(c)) {
13                currentNumber = currentNumber * 10 + (c - '0');
14            }
15            
16            // Trigger processing if current char is an operator or it's the last character.
17            // Note: We skip spaces unless it's the last character.
18            if ((!isdigit(c) && !isspace(c)) || i == n - 1) {
19                if (lastOp == '+') {
20                    myStack.push(currentNumber);
21                } else if (lastOp == '-') {
22                    myStack.push(-currentNumber);
23                } else if (lastOp == '*') {
24                    int top = myStack.top();
25                    myStack.pop();
26                    myStack.push(top * currentNumber);
27                } else if (lastOp == '/') {
28                    int top = myStack.top();
29                    myStack.pop();
30                    myStack.push(top / currentNumber);
31                }
32                lastOp = c;
33                currentNumber = 0;
34            }
35        }
36        
37        int result = 0;
38        while (!myStack.empty()) {
39            result += myStack.top();
40            myStack.pop();
41        }
42        return result;
43    }
44};

Java Solution for LeetCode 227

1class Solution {
2    public int calculate(String s) {
3        if (s == null || s.length() == 0) return 0;
4        
5        Deque<Integer> stack = new ArrayDeque<>();
6        int currentNumber = 0;
7        char lastOp = '+';
8        int n = s.length();
9        
10        for (int i = 0; i < n; i++) {
11            char c = s.charAt(i);
12            
13            if (Character.isDigit(c)) {
14                currentNumber = currentNumber * 10 + (c - '0');
15            }
16            
17            if ((!Character.isDigit(c) && c != ' ') || i == n - 1) {
18                if (lastOp == '+') {
19                    stack.push(currentNumber);
20                } else if (lastOp == '-') {
21                    stack.push(-currentNumber);
22                } else if (lastOp == '*') {
23                    stack.push(stack.pop() * currentNumber);
24                } else if (lastOp == '/') {
25                    stack.push(stack.pop() / currentNumber);
26                }
27                lastOp = c;
28                currentNumber = 0;
29            }
30        }
31        
32        int result = 0;
33        for (int num : stack) {
34            result += num;
35        }
36        return result;
37    }
38}

Python Solution for LeetCode 227

1class Solution:
2    def calculate(self, s: str) -> int:
3        stack = []
4        current_number = 0
5        last_op = '+'
6        n = len(s)
7        
8        for i, char in enumerate(s):
9            if char.isdigit():
10                current_number = current_number * 10 + int(char)
11            
12            # If current char is operator or last char in string
13            if (not char.isdigit() and char != ' ') or i == n - 1:
14                if last_op == '+':
15                    stack.append(current_number)
16                elif last_op == '-':
17                    stack.append(-current_number)
18                elif last_op == '*':
19                    top = stack.pop()
20                    stack.append(top * current_number)
21                elif last_op == '/':
22                    top = stack.pop()
23                    # Python // floors, but problem requires truncation toward zero
24                    # e.g., -3 // 2 = -2, but we want -1
25                    stack.append(int(top / current_number))
26                
27                last_op = char
28                current_number = 0
29        
30        return sum(stack)