Leetcode 785 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()