The O(n) Club: Stack Your Sanity with LeetCode 224’s Basic Calculator

The O(n) Club: Stack Your Sanity with LeetCode 224’s Basic Calculator

⚡ TL;DR

Can you evaluate arithmetic strings with ‘+’, ‘-‘, ‘(‘, ‘)’ and more white space than your old resume? You can—if you treat parentheses like mental checkpoints and wield a Java stack. Don’t even think about eval().

// Stack saves your math bacon (Java version)
public int calculate(String s) {
    Stack
<integer> stack = new Stack<>();
    int result = 0, sign = 1;
    for (int i = 0; i < s.length(); i++) {
        char c = s.charAt(i);
        if (Character.isDigit(c)) {
            int num = 0;
            while (i < s.length() && Character.isDigit(s.charAt(i))) {
                num = num * 10 + (s.charAt(i) - '0');
                i++;
            }
            i--;
            result += sign * num;
        } else if (c == '+') sign = 1;
        else if (c == '-') sign = -1;
        else if (c == '(') {
            stack.push(result);
            stack.push(sign);
            result = 0;
            sign = 1;
        } else if (c == ')') {
            result = stack.pop() * result + stack.pop();
        }
    }
    return result;
}</integer>

🧠 How Devs Usually Mess This Up

Most devs treat arithmetic like it’s their grocery list: add as you go, hope it works out. That’s fine until a wild parenthesis shows up. People forget to snapshot BOTH the total and sign, or try to smash numbers together before dealing with inner expressions. Bonus points for ignoring multi-digit numbers (you can’t really solve 23+7 if you read it as 2, 3, 7). Spaces trip up the lazy. Short version: if you rush, you’ll break something.

🔍 What’s Actually Going On

Think of the stack as your expression’s Undo button. When you see ‘(‘, you push your current result and sign onto the stack—like putting your math spreadsheet on hold while you handle what’s in the parenthesis. When ‘)’ rolls around, you pop the sign, pop the outside result, and combine them with the latest calculation explosion. You parse whole numbers (not just single digits), skip whitespace, and ONLY do calculations when you hit a sign, parenthesis, or the end. Like a chef prepping all the ingredients before lighting the stove, it’s about setup before action.

🛠️ PseudoCode

• Start with: result = 0, sign = 1, stack = empty
• For each character in the string:
  • If digit: parse the whole number, then result += sign * num
  • If ‘+’: sign = 1 (ready to add whatever’s next)
  • If ‘-‘: sign = -1 (ready to subtract whatever’s next)
  • If ‘(‘: Push result, then sign. Reset result, sign = 1
  • If ‘)’: result = stack.pop() * result + stack.pop()
  • If ‘ ‘ (space): Ignore like that recruiter’s LinkedIn message
• Return result with all the parentheses drama resolved

💻 The Code

public int calculate(String s) {
    Stack
<integer> stack = new Stack<>();
    int result = 0;
    int sign = 1;
    for (int i = 0; i < s.length(); i++) {
        char c = s.charAt(i);
        if (Character.isDigit(c)) {
            int num = 0;
            while (i < s.length() && Character.isDigit(s.charAt(i))) {
                num = num * 10 + (s.charAt(i) - '0');
                i++;
            }
            i--;
            result += sign * num;
        } else if (c == '+') {
            sign = 1;
        } else if (c == '-') {
            sign = -1;
        } else if (c == '(') {
            stack.push(result);
            stack.push(sign);
            result = 0;
            sign = 1;
        } else if (c == ')') {
            result = stack.pop() * result + stack.pop();
        }
    }
    return result;
}</integer>

⚠️ Pitfalls, Traps & Runtime Smacks

• Boring whitespace: Don’t skip parsing just because it’s a space. Ignore those, but don’t remove them; you’ll regret it.
• Multi-digit numbers: Don’t break apart 123 into 1, 2, 3. Build the full number each time.
• Premature calculation: Don’t apply a number until you hit an operator, parenthesis, or the end.
• Stack mistakes: Save BOTH result and sign before ‘(‘. Miss one, and say hello to bug city.
• Time/Space: One pass, O(n) time, stack for state: O(n) space. If you see O(n²)… debug your stack, not your laptop.

🧠 Interviewer Brain-Tattoo

If evaluating parentheses isn’t like stacking save files in a game, you’re playing the wrong bug-hunt. Use the stack, save your sanity.