题解 | #表达式求值#

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 返回表达式的值
# @param s string字符串 待计算的表达式
# @return int整型
#
class Solution:
    def solve(self , s: str) -> int:
        # write code here
        # 转后缀
        pos=[]
        pos_sta=[]
        i=0
        while i<len(s):
            if s[i]=='+' or s[i]=='-':
                while pos_sta and pos_sta[-1] in ['*','+','-']:
                    pos.append(pos_sta.pop())
                pos_sta.append(s[i])
            elif s[i]=='*':
                pos_sta.append(s[i])
            elif s[i]=='(':
                pos_sta.append(s[i])
            elif s[i]==')':
                while pos_sta:
                    if pos_sta[-1]=='(':
                        pos_sta.pop()
                        break
                    pos.append(pos_sta.pop())
            else: # 数字
                tmp=''
                while i<len(s) and s[i] not in ['+','-','*','(',')']:
                    tmp+=s[i]
                    i+=1
                pos.append(tmp)
                i-=1
            i+=1
        while pos_sta:
            pos.append(pos_sta.pop())
        print(f"pos:{pos}")
        i=0
        sta=[]
        while i<len(pos):
            if pos[i] not in ['+','-','*']:
                sta.append(int(pos[i]))
            else:
                num2=sta.pop()
                num1=sta.pop()
                if pos[i]=='+':
                    sta.append(num1+num2)
                elif pos[i]=='-':
                    sta.append(num1-num2)
                else:
                    sta.append(num1*num2)
            i+=1
        return sta[0]

中缀表达式求值，先转后缀表达式，再用后缀表达式求值。

中缀转后缀：

用到一个栈由于当前运算符只有+-*括号，而括号单独处理，*比+-的优先级高。

遍历中缀表达式，遇到数字时，加入后缀表达式中，遇到符号，要把连续的数字字符变为一个数。

若为+-，判断栈顶是否为+-*，是的话弹出，只到看到（，然后加入栈中。

若为*，加入栈中。

若为），一直弹出，只到弹出（。

弹出的符号除了括号外需要加入后缀表达式。

后缀求值

用到一个新的栈，遍历后缀表达式，若是数字，加入栈

若是符号，弹出栈顶的两个元素，运算后压入栈中，栈顶元素在后，第二个元素在前。

最终结果为栈中剩下的唯一元素