Problem Description

• LeetCode 227 Basic Calculator II

LeetCode 227 (Basic Calculator II) asks us to evaluate a mathematical expression containing integers and the operators +, -, *, and /. The expression is given as a string with possible spaces, and we need to follow standard operator precedence rules where multiplication and division have higher precedence than addition and subtraction.

Key constraints:

• No parentheses in the expression
• All intermediate results fit within a 32-bit integer
• Division truncates toward zero
• Input string is valid

Example: "3+2*2" should return 7, not 10, because multiplication has higher precedence.

Core Algorithm Walkthrough

The solution uses a stack-based approach to handle operator precedence elegantly. Instead of complex parsing, it processes operators immediately while deferring addition/subtraction operations.

Key Insight

• High precedence operators (*, /): Process immediately by operating on the stack's top element
• Low precedence operators (+, -): Defer by pushing values to the stack for later summation

Algorithm Steps

1. Initialize: Stack, current number (num = 0), and previous operator (operator = '+')

2. Process each character:

   • If digit: Build the current number: num = num * 10 + (c - '0')
   • If operator or end of string: Process the previous operator with current number:
     • +: Push num to stack
     • -: Push -num to stack
     • *: Pop from stack, multiply with num, push result back
     • /: Pop from stack, divide by num, push result back
   • Reset num = 0 and update operator = c

3. Final calculation: Sum all values remaining in the stack

Example Trace: "3+2*2"

i=0: c='3' → num=3
i=1: c='+' → Process prev '+' with num=3 → stack=[3], operator='+', num=0
i=2: c='2' → num=2  
i=3: c='*' → Process prev '+' with num=2 → stack=[3,2], operator='*', num=0
i=4: c='2' → num=2
i=5: End → Process prev '*' with num=2 → pop 2, compute 2*2=4 → stack=[3,4]
Final: sum stack = 3+4 = 7

Complexity Analysis

• Time Complexity: O(n) where n is the length of the input string. Each character is processed once.
• Space Complexity: O(n) in the worst case for the stack. In an expression with only addition/subtraction, each number gets pushed to the stack.

Full Solution (Java)

class Solution {
    public int calculate(String s) {
        Stack<Integer> st = new Stack<>();

        int num = 0;
        char operator = '+';

        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);

            if (Character.isDigit(c)) {
                num = num * 10 + (c - '0');
            }

            if (isOperator(c) || i == s.length() - 1) {
                if (operator == '+') st.push(num);
                else if (operator == '-') st.push(-num);
                else if (operator == '*') st.push(st.pop() * num);
                else if (operator == '/') st.push(st.pop() / num);

                num = 0;
                operator = c;
            }
        }

        int ans = 0;
        while (!st.isEmpty()) {
            ans += st.pop();
        }

        return ans;
    }

    private boolean isOperator(char c) {
        return c == '+' || c == '-' || c == '*' || c == '/';
    }
}