Basic calculator with parentheses

Hard TimeO(n) SpaceO(n)

Given a string s of digits, plus and minus signs, balanced parentheses and spaces, return its value without calling eval. There is no multiplication, so precedence is not in play — but a minus in front of a bracket flips the sign of everything inside it. Spaces may appear anywhere and mean nothing.

Examples

Example 1

Input
s = "(1+(4+5+2)-3)+(6+8)"
Output
23
4 + 5 + 2 is 11, so the first bracket is 1 + 11 − 3 = 9, and 9 + 14 = 23.

Example 2

Input
s = "2-(5-6)"
Output
3
5 − 6 is −1, and 2 − (−1) is 3 — the minus flips what is inside the bracket.

The Code

function calculate(s) {
  let result = 0;
  let sign = 1;
  let i = 0;
  const stack = [];
  while (i < s.length) {
    const ch = s[i];
    if (ch >= "0" && ch <= "9") {
      let num = 0;
      while (i < s.length && s[i] >= "0" && s[i] <= "9") {
        num = num * 10 + Number(s[i]);
        i++;
      }
      result += sign * num;
      continue;
    }
    if (ch === "+") sign = 1;
    else if (ch === "-") sign = -1;
    else if (ch === "(") {
      stack.push(result);
      stack.push(sign);
      result = 0;
      sign = 1;
    } else if (ch === ")") {
      const outerSign = stack.pop();
      const outerResult = stack.pop();
      result = outerResult + outerSign * result;
    }
    i++;
  }
  return result;
}
calculate("(1+(4+5+2)-3)+(6+8)");
Done

The first 19 calls, of 35. This one does not fit on a page.

Step through calculate("(1+(4+5+2)-3)+(6+8)") call by call

More like this

All stacks & queues examples (8) →