Basic Calculator Solutions & Complexity

1. Define the problem

Basic Calculator

You are given a string holding a simple sum, and you must work out its value. The string can contain digits, plus, minus, spaces and round brackets . There is no multiplication or division. Brackets are the hard part, because a bracket pauses the sum you were adding up. "1+(4-2)" means you must finish 4-2 before you can add it to the 1. Keep a running result and a sign that says whether the next number is added or subtracted. When you meet an opening bracket, push the running result and the sign onto a stack and start fresh from zero. When you meet a closing bracket, pop them back — multiply the inner result by the popped sign and add the popped result. A minus sign in front of a bracket flips the whole bracket, and this handles that on its own.

Constraints

1 ≤ s.length ≤ 3 × 10⁵
s contains digits, '+', '-', '(', ')' and spaces
s is a valid expression and the brackets are balanced
Every number in s is a non-negative integer
The answer fits in a normal integer

Example

Inputs = "1+(4-2)"

Output3

Explanation The bracket works out to 4 - 2 = 2, and adding the 1 in front of it gives 3.

2. Know the words first

In plain terms

Running result: The total of everything added or subtracted so far at the current bracket level.
Sign: Either +1 or -1. It records whether the number you are about to read should be added or taken away.
Stack: A pile where you add and remove only at the top. Here it parks the unfinished outer sum while an inner bracket is worked out.
Nested brackets: Brackets inside brackets. The innermost one always has to be finished first.

3. Visualize the solution

The row is the stack of parked work: a saved result and a saved sign for each open bracket

0—

1—

2—

3—

Statusinit

Start with an empty stack, a result of 0 and a sign of +1.

What happens in this step

s = "1+(4-2)"
stack = []
result = 0, number = 0, sign = +1

Nothing has been parked yet, so every slot shows a dash.

Step 1 of 6

Steps to visualize

Each filled cell is one parked value. A dash means an empty slot.
An opening bracket parks two cells: the result so far, then the sign in front of the bracket.
After parking, result restarts at 0 and sign restarts at +1, so the bracket is worked out on its own.
A closing bracket pops the sign and the saved result and folds the inner answer back into the outer one.
The variables result, number and sign are shown in the step detail, since they are not on the stack.

4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

The row is the stack of parked work: a saved result and a saved sign for each open bracket

0—

1—

2—

3—

Statusinit

Start with an empty stack, a result of 0 and a sign of +1.

What happens in this step

s = "1+(4-2)"
stack = []
result = 0, number = 0, sign = +1

Nothing has been parked yet, so every slot shows a dash.

Step 1 of 6

5. Solution

Solution

solution.tsTypeScript

function calculate(s) {
  const stack = [];
  let result = 0;
  let number = 0;
  let sign = 1;

  for (const ch of s) {
    if (ch >= '0' && ch <= '9') {
      number = number * 10 + Number(ch);
    } else if (ch === '+') {
      result += sign * number;
      number = 0;
      sign = 1;
    } else if (ch === '-') {
      result += sign * number;
      number = 0;
      sign = -1;
    } else if (ch === '(') {
      stack.push(result);
      stack.push(sign);
      result = 0;
      sign = 1;
    } else if (ch === ')') {
      result += sign * number;
      number = 0;
      result = result * stack.pop() + stack.pop();
      sign = 1;
    }
  }

  return result + sign * number;
}

Time: O(n)
Space: O(n)

6. Test cases

Test cases

Input	Expected	Covers
`s = "1+(4-2)"`	`3`	example from the description
`s = "42"`	`42`	smallest input, one number with no operator
`s = " 2-1 + 2 "`	`3`	spaces that must be ignored
`s = "2-(5-6)"`	`3`	a minus sign in front of a bracket flipping the whole bracket
`s = "(1+(4+5+2)-3)+(6+8)"`	`23`	brackets inside brackets, plus a second bracket group
`s = "1-(3+5)"`	`-7`	a result that ends up below zero

Basic Calculator