Problem:

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 .

You may assume that the given expression is always valid.

Some examples:

"1 + 1" = 2

" 2-1 + 2 " = 3

"(1+(4+5+2)-3)+(6+8)" = 23

Note: Do not use the eval built-in library function.

Directly Calculation

Attention the sign

def calculate(self, s):
res, num, sign, stack = 0, 0, 1, [1]
for i in s+"+":
if i.isdigit():
num = 10*num + int(i)
elif i in "+-":
res += num * sign * stack[-1]
sign = 1 if i=="+" else -1
num = 0
elif i == "(":
stack.append(sign * stack[-1])
sign = 1
elif i == ")":
res += num * sign * stack[-1]
num = 0
stack.pop()
return res


Recursive Calculation

def calculateBracket(expression, leftStartIndex):
pos = leftStartIndex
res = 0
sign = "+"
while pos < len(expression) and expression[pos] != ")":
tempRes = 0
if expression[pos] == "(":
pos, tempRes = calculateBracket(expression, pos+1)
else:
if expression[pos].isdigit():
while pos<len(expression) and expression[pos].isdigit():
tempRes = tempRes*10 + int(expression[pos])
pos += 1
else:
if expression[pos] == "+" or expression[pos] == "-":
sign = expression[pos]
pos += 1
if sign == "+":
res += tempRes
elif sign == "-":
res -= tempRes
return pos+1, res
pos, result  = calculateBracket(s, 0)
return result


Reverse Polish

def calculate(self, s):
s = s.replace(' ', '')
oper = {"+": lambda y, x: x + y, "-": lambda y, x: x - y}
oper_stack, num_stack = [], []
tmp = ''
for c in s:
if c.isdigit():
tmp += c
continue
if tmp:
num_stack.append(int(tmp))
tmp = ''
if c == '(':
oper_stack.append(c)
else:
while oper_stack and oper_stack[-1] != '(':
num_stack.append(oper[oper_stack.pop()](num_stack.pop(), num_stack.pop()))
if c in oper:
oper_stack.append(c)
else:
oper_stack.pop()
if tmp:
num_stack.append(int(tmp))
while oper_stack:
num_stack.append(oper[oper_stack.pop()](num_stack.pop(), num_stack.pop()))
return num_stack[0]