Basic Calculator

Hard#224evaluate

You get a correct expression as a string: non-negative integers, + and −, brackets and spaces; a minus may also stand before a number or a bracket on its own. Work out its value without any built-in eval. Our example: "12-(3-(4+1))+2" — the answer is 16.

224 Basic CalculatorWalkthrough · 1×

Example: "12-(3-(4+1))+2". Under the string are result, the sign of the next number and num, the number being read; under them the stack, where each "(" saves the result and the sign in front of it.

12-(3-(4+1))+2result0sign1num0stack—
not read yetch, read now; what this step changedreadsaved on the stackthe "(" being closed; popped at ")"

Start: result 0, the next number counts with sign +1, no digits read, nothing saved

01/40
restart · back · play · step
Speed
1function calculate(s):
2 result = 0, sign = 1, num = 0, stack = empty stack
3 for each ch in s:
4 if ch is a digit:
5 num = num * 10 + digit(ch)
6 else if ch is "+" or ch is "-":
7 result = result + sign * num, num = 0
8 sign = 1 if ch is "+" else -1
9 else if ch is "(":
10 push result, then sign onto stack
11 result = 0, sign = 1
12 else if ch is ")":
13 result = result + sign * num, num = 0
14 result = result * pop from stack
15 result = result + pop from stack
16 return result + sign * num
state
s
"12-(3-(4+1))+2"
ch
–
num
0
sign
1
result
0
stack
[]
historyclick a step to go back

← → step · space play/pause

Why it works

  1. With only + and −, the value is a sum of numbers, each with its sign. A number is added once it ends, at the next sign, at ")" or at the end of the string.
  2. A bracket is a sum of its own, so at "(" the outer result and the sign in front are saved and the inside starts from 0. At ")" the inner sum is multiplied by that sign and added back: the latest "(" is the first to close, so the saved pair is on top.
  3. A minus at the very start or right after "(" needs no special case: it adds num = 0 and sets the sign to −1.

Complexity

Time O(n): each character is read once. Memory O(n): two numbers on the stack for every bracket open at once, at most n.

nextNow solve it yourself, no hints.

Solve on LeetCode ↗

The problem and its statement belong to LeetCode. Here are our own retelling, example and solution. Patterns Hero is not affiliated with LeetCode.