# Leetcode 785 Solution

https://leetcode.com/problems/basic-calculator-iii

## Solution

class Solution:
def calculate(self, s: str) -> int:
i = 0

def get_next_token():
nonlocal s
nonlocal i

while i < len(s) and s[i] == ' ':
i += 1

if i == len(s):
return None

if s[i] in ['+', '-', '*', '/', '(', ')']:
i += 1
return s[i - 1]
elif '0' <= s[i] <= '9':
ans = 0
while i < len(s) and '0' <= s[i] <= '9':
ans = ans * 10 + int(s[i])
i += 1
return ans
else:
raise Exception("Unexpected token '{}'!".format(s[i]))

def evaluate():
nonlocal s
nonlocal i

vals = []
last_sign = '+'

while i < len(s):
token = get_next_token()

if token in ['+', '-', '*', '/']:
last_sign = token
elif isinstance(token, int) or token == '(':
if token == '(':
val = evaluate()
else:
val = token

if last_sign == '+':
vals.append(val)
elif last_sign == '-':
vals.append(-val)
elif last_sign == '*':
vals.append(vals.pop() * val)
elif last_sign == '/':
last_val = vals.pop()

if last_val * val < 0:
vals.append(-(-last_val // val))
else:
vals.append(last_val // val)
else:
raise Exception("Unexpected last sign '{}'!".format(last_sign))
elif token == ')':
break
else:
raise Exception("Unexpected position '{}'!".format(i))

return sum(vals)

return evaluate()