>>109174733
>>109173406
easy
the optimal solution is to remove recursion and use a stack instead, but this would pass an interview.
class Solution:
def calculate(self, s: str) -> int:
i = ans = 0
#returns the string offset and the result of evaluating the given expression
#so (1+1) returns (5, 2)
def evaluate(self, s: str, i: int) -> (int, int):
j = i
mul = 1; ans = cur = 0;
while j < len(s):
#print(s[j])
#digit
if s[j].isdigit():
cur *= 10
cur += int(s[j])
#base case
elif s[j] == ")":
j += 1
break
#recurse to solve the next parenthesis
elif s[j] == "(":
res = evaluate(self, s, j + 1)
j += res[0]
ans += (mul * res[1]); mul = 1
#addition or subtraction operation, add current values and clean states for next value
elif s[j] == "-" or s[j] == "+":
ans += mul * cur; cur = 0; mul = 1
if s[j] == "-":
mul = -1
j += 1
#print(mul, cur)
ans += (mul * cur)
return(j - i, ans)
while i < len(s):
res = evaluate(self, s, i)
i += res[0]
ans += res[1]
return ans
