Basic Calculator

You're given a string s holding a valid arithmetic expression. Evaluate it and return the integer result. You may not use any built-in function that evaluates strings as code (such as eval).

The expression contains only:

• non-negative integers (possibly several digits long),
• the binary operators + and -,
• parentheses ( and ),
• spaces, which can appear anywhere and should be ignored.

A - may also be unary, negating what follows it, but only at the very start of the expression or right after an (. A + is never unary, and two operators never appear next to each other.

With only + and -, there's no precedence to worry about. Without parentheses you could just keep a running result and a sign (+1 or -1) for the next number: every time a number ends, add sign * number to result.

Parentheses are the only complication, and they nest like a stack. When you hit (, the work you've done so far is on hold: push the current result and the sign in front of the parenthesis, then start a fresh result of 0 for the inside. When you hit ), the inside is finished; pop the saved pair and fold it back in as saved_result + saved_sign * inside.

Unary minus falls out for free. At the start of the expression or right after (, result is 0, so a - just adds 0 and sets sign = -1 for what follows.

def calculate(s: str) -> int:
    result = 0
    number = 0
    sign = 1
    stack = []  # (result before "(", sign in front of "(")
    for ch in s:
        if ch.isdigit():
            number = number * 10 + int(ch)
        elif ch == "+" or ch == "-":
            result += sign * number
            number = 0
            sign = 1 if ch == "+" else -1
        elif ch == "(":
            stack.append((result, sign))
            result, sign = 0, 1
        elif ch == ")":
            result += sign * number
            number = 0
            saved, saved_sign = stack.pop()
            result = saved + saved_sign * result
    return result + sign * number

function calculate(s) {
  let result = 0;
  let number = 0;
  let sign = 1;
  const stack = []; // [result before "(", sign in front of "("]
  for (const ch of s) {
    if (ch >= '0' && ch <= '9') {
      number = number * 10 + (ch.charCodeAt(0) - 48);
    } else if (ch === '+' || ch === '-') {
      result += sign * number;
      number = 0;
      sign = ch === '+' ? 1 : -1;
    } else if (ch === '(') {
      stack.push([result, sign]);
      result = 0;
      sign = 1;
    } else if (ch === ')') {
      result += sign * number;
      number = 0;
      const [saved, savedSign] = stack.pop();
      result = saved + savedSign * result;
    }
  }
  return result + sign * number;
}

Clarify the grammar first: which operators, whether unary minus exists and where, and whether spaces can appear inside numbers (they can't here). Interviewers like hearing you pin that down.

Then explain the state you carry: "result so far, the number I'm reading, and the sign for it. A parenthesis pushes that state and starts fresh." Trace an example with a negated group, like -(4 - 10), since that's the case most solutions get wrong.