```
# Recursively, TLE
# every time find the most inner parentheses and compute
# the value inside it, do this process recursively
def calculate1(self, s):
r = s.find(")")
if r == -1:
return self.cal(s)
l = s.rfind("(", 0, r)
return self.calculate(s.replace(s[l:r+1], str(self.cal(s[l+1:r])), 1))
def calculate(self, s):
stack, i = [], 0
while i < len(s):
while i < len(s) and s[i] != ")":
stack.append(s[i])
i += 1
tmp = ""
while stack and stack[-1] != "(":
tmp = stack.pop() + tmp
t = self.cal(tmp)
if stack:
stack.pop() # pop out "("
if t < 0 and stack:
# tackle case like "2--1"
if stack[-1] == "-":
stack[-1] = "+"
# tackle case like "2+-1"
else:
stack[-1] = "-"
stack.append(str(-t))
else:
stack.append(str(t))
i += 1
return self.cal("".join(stack))
# calculate the value of a string without parentheses,
# like: " +1 - 3 + 4 " = 2
def cal(self, s):
res, i = 0, 0
while i < len(s):
sign = 1
if s[i] in ["-", "+"]:
if s[i] == "-":
sign = -1
i += 1
while i < len(s) and s[i] == " ":
i += 1
tmp = 0
while i < len(s) and s[i].isdigit():
tmp = 10*tmp + int(s[i])
i += 1
res += sign*tmp
return res
```