224. Basic Calculator

Evaluate a valid expression string containing non-negative integers, '+', '−', '(', ')' and spaces. '−' may also be unary. Don't use eval.

Accumulate result with the current sign. On '(' push the running result and the sign before it, then start fresh. On ')' multiply the inner result by the saved sign and add the saved result back.

1function calculate(s: string): number {
2  const stack: number[] = [];
3  let result = 0, sign = 1, num = 0;
4  for (const c of s) {
5    if (c >= "0" && c <= "9") num = num * 10 + +c;
6    else if (c === "+" || c === "-") { result += sign * num; num = 0; sign = c === "+" ? 1 : -1; }
7    else if (c === "(") { stack.push(result, sign); result = 0; sign = 1; }
8    else if (c === ")") { result += sign * num; num = 0; result = result * stack.pop()! + stack.pop()!; }
9  }
10  return result + sign * num;
11}

result = 0sign = 1num = 0

s

(

)

(

)

stack (result, sign pairs)

empty

result = 0, sign = +, num = 0.

1 / 0

Space: play/pause · ←/→: step