题解 | 表达式求值

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 返回表达式的值
# @param s string字符串 待计算的表达式
# @return int整型
#
class Solution:
    def solve(self , s: str) -> int:
        # write code here
        priority = {
            '+' : 1,
            '-' : 1,
            '*' : 2,
        }
        #优先级高的操作符压入操作符栈；优先级相等、低的操作符，弹出栈顶操作符，并计算；
        z_num = []
        z_op = []
        num = ''
        i=0
        while i < len(s):
            ch = s[i]
            if ch == '(':
                z_op.append(ch)
            elif ch not in '+-*)':
                num = ''
                while i<len(s) and  s[i].isdigit():
                    num += s[i]
                    i += 1
                z_num.append(int(num))
                continue
            #如果是“）”，一直计算到“（”为止；计算括号内的
            elif ch == ')':
                while z_op and z_op[-1] != '(' :
                    op = z_op.pop()
                    b = z_num.pop()
                    a = z_num.pop()
                    z_num.append(self.apply(a,b,op))
                z_op.pop() #弹出“（”

            # 若ch优先级<= 栈顶操作符优先级，则一直计算到 >栈顶操作符优先级 或“（”出现
             #如果操作符栈为空，或ch优先级比栈顶操作符优先级高，则压入栈中。
            else:
                while  len(z_op) != 0  and z_op[-1] != '(' and priority[ch] <= priority[z_op[-1]]:
                    op = z_op.pop()
                    b = z_num.pop()
                    a = z_num.pop()
                    z_num.append(self.apply(a,b,op))
                z_op.append(ch)
            i += 1
        
        #遍历完字符串后，若操作符栈不为空，则继续计算
        while z_op:
            op = z_op.pop()
            b = z_num.pop()
            a = z_num.pop()
            z_num.append(self.apply(a,b,op))
        
        return z_num[-1]
    
    def apply(self,a:int,b:int,op:chr) -> int:
            if op == '+':
                return a+b
            elif op == "-":
                return a-b
            elif op == '*':
                return a*b
            return 0