227. 基本计算器 II

给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。
整数除法仅保留整数部分。
输入：s = "3+22"
输出：7
提示：
1 <= s.length <= 3 * 105
s 由整数和算符 ('+', '-', '', '/') 组成，中间由一些空格隔开
s 表示一个 有效表达式
表达式中的所有整数都是非负整数，且在范围 [0, 231 - 1] 内
题目数据保证答案是一个 32-bit 整数

难点在于加减和乘除运算具有不同的优先级。一个简单的解决办法是使用两个栈。首先只处理乘法和除法，第二次再处理加法和减法。时间和空间复杂度均为O(n)。

class Solution:
    '''
    227. Basic Calculator II
    Two stacks.
    '''
    def calculate(self, s: str) -> int:
        first_stack = list()
        idx = 0
        while idx < len(s):
            if s[idx] == ' ':
                # ignore all the spaces
                idx += 1
                continue
            if s[idx] >= '0' and s[idx] <= '9':
                # get the number if it has more
                # than one digit
                num_str = ''
                while idx < len(s) and s[idx] >= '0' and s[idx] <= '9':
                    num_str += s[idx]
                    idx += 1
                num = int(num_str)
                if len(first_stack) == 0 or first_stack[-1] in ('+', '-'):
                    # if it's either + or - on top 
                    # of the stack, just push it
                    # into the stack
                    first_stack.append(num)
                else:
                    # otherwise, evaluate and push the result
                    # back into the stack
                    operator = first_stack.pop()
                    left_operand = first_stack.pop()
                    first_stack.append(
                        left_operand * num if operator == '*' else left_operand // num
                    )
                continue
            # for all the operators, just
            # push it into the stack
            first_stack.append(s[idx])
            idx += 1

        # have the scond stack to handle all
        # the plus and minus calculation
        second_stack = list()
        for each in first_stack:
            if type(each) == int:
                if len(second_stack) == 0:
                    second_stack.append(each)
                else:
                    operator = second_stack.pop()
                    left_operand = second_stack.pop()
                    second_stack.append(
                        left_operand + each if operator == '+' else left_operand - each
                    )
            else:
                second_stack.append(each)
        
        return second_stack[0]