# Question

Implement a basic calculator to evaluate a simple expression string.

The expression string may contain open ( and closing parentheses ), the plus + or minus sign -, non-negative integers and empty spaces .

Example 1:

Input: "1 + 1"
Output: 2


Example 2:

Input: " 2-1 + 2 "
Output: 3


Example 3:

Input: "(1+(4+5+2)-3)+(6+8)"
Output: 23


Note:

• You may assume that the given expression is always valid.
• Do not use the eval built-in library function.

# Solution

class Solution(object):
def calculate(self, s):
"""
:type s: str
:rtype: int
"""
if len(s) == 0:
return 0

stack = list()
curr_num = 0
in_number = False
for c in s:
if c.isdigit():
curr_num = curr_num * 10 + int(c)
in_number = True
elif c == '+' or c == '-':
if in_number:
stack.append(curr_num)
in_number = False
curr_num = 0
stack.append(c)

elif c == '(':
if in_number:
stack.append(curr_num)
curr_num = 0
in_number = False
stack.append(c)
elif c == ')':
if in_number:
stack.append(curr_num)
curr_num = 0
in_number = False

res = 0
curr = 0
while stack[-1] != '(':
v = stack.pop()
if v == '+':
res += curr
elif v == '-':
res -= curr
else:
curr = v
stack.pop() # remove corresponding (
res += curr
stack.append(res)
if c == ' ':
if in_number:
stack.append(curr_num)
curr_num = 0
in_number = False

if in_number:
stack.append(curr_num)

res = 0
curr = 0
while len(stack) > 0:
v = stack.pop()
if v == '+':
res += curr
elif v == '-':
res -= curr
else:
curr = v
res += curr
return res