The O(n) Club: When String Calculators Attack (a.k.a. LeetCode 227, but Funnier)

The O(n) Club: When String Calculators Attack (a.k.a. LeetCode 227, but Funnier)

⚡ TL;DR

Given a string with numbers and +, -, *, /, compute its value like a grown-up calculator—NOT like a kid pressing keys at random. Parse left-to-right, deal with operator precedence (order matters!), and absolutely no eval(), unless you want an interviewer to faint.

// Brute force (wrong!): ignores precedence
int res = 0, num = 0;
char op = '+';
for (char c : expr.toCharArray()) {
    if (Character.isDigit(c)) num = num * 10 + (c - '0');
    else if (c == '+' || c == '-') {
        res = calc(res, op, num); // Misses * and /
        op = c;
        num = 0;
    }
}
// Fails for '3+2*2'

🧠 How Devs Usually Mess This Up

If you’re tempted to just march from left to right, doing math as you go, let me save you from heartache (and a bad first impression). That “3 + 2 * 2” example? Most folks see 10—not the correct 7—because they forget that multiplication/division always pull rank over mere addition/subtraction.

Classic rookie error #2: setting num = digit each time and forgetting multi-digit numbers. Congrats, “23 + 5” is now 2 + 3 + 5 = 10. Try not to brag about that one.

Finally: using eval() in an interview is the fastest way to end up writing documentation for printers.

🔍 What’s Actually Going On

Operators are like impatient cooks: multiplication and division want their meals served hot and NOW. Addition and subtraction? They’re fine waiting in the “to plate” stack until the dinner rush is over.

As you parse each character:

🛠️ PseudoCode

• Initialize: stack, num = 0, sign = ‘+’
  

  Stack<integer> stack = new Stack<>();
  int num = 0;
  char sign = '+';</integer>

• For each character:
  

  for (int i = 0; i < s.length(); i++) {...}

  If digit, keep building the number! If space, ignore. If operator (or last char), time to unleash operator logic.
• Operator Logic: On operator or end:
  • If ‘+’, push num
  • If ‘-‘, push -num
  • If ‘*’, pop, multiply, push result
  • If ‘/’, pop, integer-divide, push result

if (sign == '+') stack.push(num);
if (sign == '-') stack.push(-num);
if (sign == '*') stack.push(stack.pop() * num);
if (sign == '/') stack.push(stack.pop() / num);

int sum = 0;
while (!stack.isEmpty()) sum += stack.pop();

💻 The Code

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

⚠️ Pitfalls, Traps & Runtime Smacks

• Whitespace: ignore it—or suffer.
• Multi-digit numbers: don’t break up “123” as 1, then 2, then 3. Seriously.
• Division: Java integer division rounds toward zero (-3/2 = -1). Don’t get clever with Math.floor.
• Trailing number/edge chars: Always process the last sneaky number after finishing your loop.
• Performance: O(n) time, and O(n) space for the stack (unless you go full Jedi and do O(1)).

🧠 Interviewer Brain-Tattoo

eval() is the answer… if you want job security as a security risk. For everyone else, parsing and proper precedence is how you show you can actually code (and not just code dangerously).