题解 | #表达式求值#

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


class Solution:
    def solve(self, s: str) -> int:
        # write code here
        """
        整体思路是将字符串转化为中缀表达式
        然后将中缀表达式转化为计算机可以计算的后缀表达式，
        然后写一个后缀表达式计算的算法，进行计算
        """

        L = []
        L2 = []
        stack2 = []
        num = ""
        operations = ["+", "-", "*", "(", ")"]

        # 定义符号的优先级，便于转化为前缀表达式时进行优先级的比较
        prioprity = {"(": 0, "+": 1, "-": 1, "*": 2}
        for x in s:
            # 将连续的数字进行累加
            if x.isdigit():
                num += x
            else:
                # 如果s不是数字，那么前面累计的数字作为一个整体输入到L2中，Num置为空，
                # 然后再添加非数字
                if num:
                    L2.append(num)
                    num = ""
                L2.append(x)
        # 最后遍历完记得把最后的数字添加上，如果num不为空
        if num:
            L2.append(num)

        # s = list(s)
        # 遍历L2中的元素，如果是数字，进行添加L,如果是符号和stack2中的符号的优先级进行比较，如果优先级高，入栈；如果优先级低，栈顶元素出栈。直到优先级比栈顶元素高，再进栈。如果是左括号，直接入栈，如果是右括号，将栈中的符号到右括号为止顺序出栈，右括号和左括号不做特殊处理
        for i in L2:
            if i not in operations:
                L.append(i)

            if i in operations:
                """
                先处理i是扩号的情况,后处理i是加减乘的情况
                """
                # 如果是左括号，直接入栈
                if i == "(":
                    stack2.append(i)
                # 将栈中的符号到右括号为止顺序出栈，添加到L中
                elif i == ")":
                    x = i
                    while x != "(":
                        x = stack2.pop()
                        L.append(x)
                    # 最后多添加一个左括号记得进行删除
                    L.pop()

                # 处理i是+-*的情况,比较i的优先级和栈顶元素
                elif stack2 and prioprity[i] <= prioprity[stack2[-1]]:
                    #栈有可能在出站的过程中变成空栈
                    while stack2 and prioprity[i] <= prioprity[stack2[-1]]:
                        x = stack2.pop()
                        L.append(x)
                    #出栈完以后需要将高优先级的元素入栈
                    stack2.append(i)
                else:
                    stack2.append(i)

        # 当遍历完后，将stack2中的元素全部添加到L中
        if stack2:
            x = stack2.pop()
            L.append(x)
        # print(L)
        # L = L[::-1]
        stack = []
		#从左到右取后缀表达式，遇到操作数入栈，遇到符号出栈，进行运算
        for x in L:
            if x in operations:
                y = stack.pop()
                z = stack.pop()
                res = eval(z + x + y)
                stack.append(str(res))
            else:
                stack.append(x)
        return int(stack.pop())