iterative solution
"""
main idea: By utilizing there is only + - in the expression. we can use stack to track sign in front of a parenthesis. each time a nom-digit number appear, res will need to be added with num. Note the sign is affected by its previous operator(+,-)
and global sign ahead of the parenthesis.
"""
class Solution:
def calculate(self, s: str) -> int:
res = 0
num = 0
st = []
sign = 1
st.append(sign)
for i in range(len(s)):
if s[i].isdigit():
num = num * 10 + int(s[i])
if s[i] in ['+','-'] or i == len(s)-1:
res = res + sign * num
sign = st[-1] * (1 if s[i]=='+' else -1)
num = 0
if s[i] == '(':
st.append(sign)
if s[i] == ')':
st.pop()
return res
recursive solution
class Solution:
def calculate(self, s: str) -> int:
def helper(s):
st = []
sign = '+'
num = 0
while 0 < len(s):
c = s.pop(0)
if c.isdigit():
num = num * 10 + int(c)
if (not c.isdigit() and c!=' ') or len(s) == 0 :
if c == '(':
num = helper(s)
if sign == '+':
st.append(num)
elif sign == '-':
st.append(-num)
elif sign == '*':
st[-1] = st[-1]*num
elif sign == '/':
st[-1] = int(st[-1]/float(num))
sign = c
num = 0
if c == ')':
break
return sum(st)
return helper(list(s))