Pseudo-code

text
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.

Core Insight for Basic Calculator II

The primary challenge in LeetCode 227 is handling operator precedence without parentheses. We cannot simply process the expression from left to right because a + operation cannot be executed until we ensure the right-hand operand isn't part of a subsequent * or / operation (e.g., in 3 + 2 * 5, we cannot add 3 and 2 immediately).

The core insight is to treat the expression as a sum of terms. We can use a stack to store these terms.

1. Addition/Subtraction: These have the lowest precedence. When we encounter these, we push the number (or its negative for subtraction) onto the stack. We effectively say, "I will add this later."
2. Multiplication/Division: These have high precedence. When we encounter these, we must evaluate them immediately with the last number processed. We pop the top of the stack (the left operand), perform the operation with the current number (the right operand), and push the result back.

Visual Description: Imagine the stack as a list of numbers waiting to be summed. As we iterate through 3 + 2 * 5:

• We see 3, push 3. Stack: [3].
• We see +, note it.
• We see 2. Previous op was +, so push 2. Stack: [3, 2].
• We see *, note it.
• We see 5. Previous op was *. We don't push 5. Instead, we pop 2, calculate 2 * 5 = 10, and push 10. Stack: [3, 10].
• At the end, we sum the stack: 3 + 10 = 13.

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.

Reference Implementation

C++ Solution for LeetCode 227

cpp
class Solution {
public:
    int calculate(string s) {
        stack<int> myStack;
        char lastOp = '+';
        int currentNumber = 0;
        int n = s.length();
        
        for (int i = 0; i < n; ++i) {
            char c = s[i];
            
            if (isdigit(c)) {
                currentNumber = currentNumber * 10 + (c - '0');
            }
            
            // Trigger processing if current char is an operator or it's the last character.
            // Note: We skip spaces unless it's the last character.
            if ((!isdigit(c) && !isspace(c)) || i == n - 1) {
                if (lastOp == '+') {
                    myStack.push(currentNumber);
                } else if (lastOp == '-') {
                    myStack.push(-currentNumber);
                } else if (lastOp == '*') {
                    int top = myStack.top();
                    myStack.pop();
                    myStack.push(top * currentNumber);
                } else if (lastOp == '/') {
                    int top = myStack.top();
                    myStack.pop();
                    myStack.push(top / currentNumber);
                }
                lastOp = c;
                currentNumber = 0;
            }
        }
        
        int result = 0;
        while (!myStack.empty()) {
            result += myStack.top();
            myStack.pop();
        }
        return result;
    }
};

Java Solution for LeetCode 227

java
class Solution {
    public int calculate(String s) {
        if (s == null || s.length() == 0) return 0;
        
        Deque<Integer> stack = new ArrayDeque<>();
        int currentNumber = 0;
        char lastOp = '+';
        int n = s.length();
        
        for (int i = 0; i < n; i++) {
            char c = s.charAt(i);
            
            if (Character.isDigit(c)) {
                currentNumber = currentNumber * 10 + (c - '0');
            }
            
            if ((!Character.isDigit(c) && c != ' ') || i == n - 1) {
                if (lastOp == '+') {
                    stack.push(currentNumber);
                } else if (lastOp == '-') {
                    stack.push(-currentNumber);
                } else if (lastOp == '*') {
                    stack.push(stack.pop() * currentNumber);
                } else if (lastOp == '/') {
                    stack.push(stack.pop() / currentNumber);
                }
                lastOp = c;
                currentNumber = 0;
            }
        }
        
        int result = 0;
        for (int num : stack) {
            result += num;
        }
        return result;
    }
}

Python Solution for LeetCode 227

python
class Solution:
    def calculate(self, s: str) -> int:
        stack = []
        current_number = 0
        last_op = '+'
        n = len(s)
        
        for i, char in enumerate(s):
            if char.isdigit():
                current_number = current_number * 10 + int(char)
            
            # If current char is operator or last char in string
            if (not char.isdigit() and char != ' ') or i == n - 1:
                if last_op == '+':
                    stack.append(current_number)
                elif last_op == '-':
                    stack.append(-current_number)
                elif last_op == '*':
                    top = stack.pop()
                    stack.append(top * current_number)
                elif last_op == '/':
                    top = stack.pop()
                    # Python // floors, but problem requires truncation toward zero
                    # e.g., -3 // 2 = -2, but we want -1
                    stack.append(int(top / current_number))
                
                last_op = char
                current_number = 0
        
        return sum(stack)