题解 | #表达式求值#

"表达式求值”问题，两个核心关键点：

1. 双栈，一个操作数栈，一个运算符栈；
2. 运算符优先级，栈顶运算符，和，即将入栈的运算符的优先级比较：
1. 如果栈顶的运算符优先级低，新运算符直接入栈
2. 如果栈顶的运算符优先级高，先出栈计算，新运算符再入栈

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 返回表达式的值
# @param s string字符串 待计算的表达式
# @return int整型
#

level = {"+": 1, "-": 1, "*": 2, "/": 2, "(": 3, ")": -1}

#中缀表达式求值
class Solution:
    def solve(self , s: str) -> int:
        # write code here
        s = s + ')'

        n = len(s)
        i = 0

        opt = []
        opt.append('(')
        num = []

        while i < n:
            t = i
            while s[t].isdigit():
                t += 1
            if(t != i):
                num.append(int(s[i:t]))
                i = t
                continue

            if opt[-1] == '(' and s[i] != ')':
                opt.append(s[i])
                i += 1
            elif level[s[i]] > level[opt[-1]]:
                opt.append(s[i])
                i += 1
            elif level[s[i]] <= level[opt[-1]]:
                if s[i] == ')' and opt[-1] == '(':
                    opt.pop()
                    i += 1
                else:
                    b = int(num.pop())
                    a = int(num.pop())
                    signal = opt.pop()
                    num.append(eval("{} {} {}".format(a, signal, b)))

        return num[-1]