题解 | #表达式求值#

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
# 返回表达式的值
# @param s string字符串 待计算的表达式
# @return int整型
#
class Solution:
    #判断读入的字符是否为操作符
    def is_operation(self,item):
        if item in {'+','-','*','(',')'}:
            return True
        else:
            return False
        
    def cal(self,operand1,operand2,stack_top_opnd):
        operand1 = int(operand1)
        operand2 = int(operand2)
        if stack_top_opnd == '+':
            res = operand1 + operand2 
        elif stack_top_opnd == '-':
            res = operand1 - operand2
        elif stack_top_opnd == '*':
            res = operand1 * operand2
        return res
    
    #比较操作符的优先级
    def operation_compare(self,current_opnd,stack_top_opnd):
        if stack_top_opnd == "(" and current_opnd == ")":
            return 0 #括号匹配直接消除
        elif stack_top_opnd in {"+","-","*"} and current_opnd == ")":
            return 1 #计算括号里面的值
        elif stack_top_opnd == "("&nbs***bsp;current_opnd == "(": 
            return -1#继续向前走
        elif current_opnd == stack_top_opnd:
            return 1 #可以计算
        elif stack_top_opnd =="*":
            return 1 #也可以计算
        elif current_opnd =="*":
            return -1 #继续向前
        else:#最后两者都为加减运算
            return 1#也可以计算
        
    def solve(self , s ):
        # write code here
        #使用deque定义两个堆栈，分别存放操作符和操作数
        from collections import deque
        operation = deque()
        operand = deque()
        current_operand=""
        s='('+s+')' #加入括号，作为结尾标志
        for i in range(len(s)):
            if self.is_operation(s[i]) is False:
                #如果为非操作符,则s[i]为操作数部分
                current_operand+=s[i]
            #如果为操作符，则比较当前操作符与operation栈顶操作符的优先级
            else:
                if current_operand!='':
                    operand.append(current_operand)
                current_operand=""
                current_opnd = s[i]
                is_continue = True
                while(is_continue):
                    if len(operation)==0:#栈顶为空，则将当前操作符入栈，并退出循环
                        operation.append(current_opnd)
                        is_continue = False
                    else:
                        stack_top_opnd = operation.pop()
                        result = self.operation_compare(current_opnd,stack_top_opnd)
                        if result == 0:#此处考虑左右括号匹配的情况,则当前操作符不入栈，且栈顶元素出栈
                            is_continue = False                        
                        elif result == 1:#此处考虑栈顶操作符可运算的情况
                            operand2 = operand.pop()
                            operand1 = operand.pop()
                            #进行计算
                            res = self.cal(operand1,operand2,stack_top_opnd)
                            operand.append(res)
                            is_continue = True#计算之后继续比较栈顶元素与当前元素的优先级
                        elif result == -1:#此处考虑栈顶操作符仍然不可运算的情况,将当前操作符入栈
                            operation.append(stack_top_opnd)
                            operation.append(current_opnd)
                            is_continue = False
        return operand.pop()