题解 | #表达式求值#

#
# 返回表达式的值
# @param s string字符串 待计算的表达式
# @return int整型
#
class Solution:
    def solve(self , s: str) -> int:
        # 对符号和数字进行分离
        arr = []
        for i in s:
            if len(arr) >= 1 and arr[-1][0] in "0123456789" and '0' <= i <= '9':
                temp = arr.pop()
                arr.append(temp+i)
            else:
                arr.append(i)
        # 维持两个栈，一个保存符号，一个保存数字
        stack1,stack2 = [],[]
        i = 0
        while i < len(arr):
            # 左括号直接入符号栈( 3 + ( 33 * 2 + 3 ) ) - 2 / 1 * 2
            if arr[i] == '(':
                stack1.append(arr[i])
            # 遇到运算符
            elif  arr[i] in ['+','-','*','/']:
                if not stack1:
                    stack1.append(arr[i])
                else:
                    temp = stack1[-1]
                    # 若没有大于或等于的符号，则加入
                    if temp not in ['+','-','*','/']:
                        stack1.append(arr[i])
                    # 若有，则判断优先级大小
                    else:
                        # 乘除计算
                        if temp in ['*','/']:
                            b = stack2.pop()
                            a = stack2.pop()
                            temp = stack1.pop()
                            stack1.append(arr[i])
                            if temp == '*': stack2.append(int(a)*int(b))
                            else: stack2.append(int(a)/int(b))
                        # 加减
                        if temp in ['+','-']:
                            if arr[i] in ['*','/']:
                                stack1.append(arr[i])
                            else:
                                b = stack2.pop()
                                a = stack2.pop()
                                temp = stack1.pop()
                                stack1.append(arr[i])
                                if temp == '+': stack2.append(int(a) + int(b))
                                else: stack2.append(int(a) - int(b))
            # 右括号
            elif arr[i] == ')':
                # stack1弹出到（为止
                while True :
                    op = stack1.pop()
                    if op == '(': break
                    else:
                        b = stack2.pop()
                        a = stack2.pop()
                        # 加减乘除
                        if op == '+':
                            stack2.append(int(a) + int(b))
                        elif op == '-':
                            stack2.append(int(a) - int(b))
                        elif op == '*':
                            stack2.append(int(a) * int(b))
                        else:
                            stack2.append(int(a) / int(b))
            # 数字
            else:
                stack2.append(int(arr[i]))
            i += 1
        # 判断stack1是否还有元素
        while stack1:
            op = stack1.pop()
            b = stack2.pop()
            a = stack2.pop()
            # 加减乘除
            if op == '+':
                stack2.append(int(a) + int(b))
            elif op == '-':
                stack2.append(int(a) - int(b))
            elif op == '*':
                stack2.append(int(a) * int(b))
            else:
                stack2.append(int(a) / int(b))
                
        return stack2.pop()