题解 | #表达式求值#

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 返回表达式的值
# @param s string字符串 待计算的表达式
# @return int整型
#
# 思路：先将中缀表达式转换为后缀表达式，再对后缀表达式进行计算。
class Solution:
    def solve(self , s: str) -> int:
        # write code here
        # 去掉字符串头尾的空格或换行符
        s = s.strip() 
        
        # 将字符串转换为列表
        # 先对字符串s进行预处理 防止将'10+1'分割为['1','0','+','1']导致计算错误
        # num是数字字符串
        num = ''
        # chars是对s处理后的列表
        chars = list()
        for i in s:
            # 如果遇到数字，就先把它拼接到num字符串中，先不急着放入chars
            if i.isdigit():
                num += i
            # 如果遇到左括号就直接放入chars中
            elif i == "(":
                chars.append(i)
            # 如果遇到右括号 num为空时直接放入chars中，否则先把num放入chars中，然后清空num，再把括号放入chars中
            elif i == ")":
                if num == '':
                    chars.append(i)
                else:
                    chars.append(num)
                    num = ''
                    chars.append(i)
            # 如果遇到运算符也是一样，与遇到右括号一致
            else:
                if num == '':
                    chars.append(i)
                else:
                    chars.append(num)
                    num = ''
                    chars.append(i)
        # 最后如果num中还有数字就拼接上去
        if num != '':
            chars.append(num)

        # 建立运算符栈
        ls = list()
        # 建立后缀表达式
        token = list()
        # 先通过运算符栈将中缀表达式转换为后缀表达式
        for i,val in enumerate(chars):
            # 1.遇到数字就直接放入后缀表达式中，因为中缀转后缀操作数的顺序不会改变
            if val != '+' and val != '-' and val != '*' and val != '(' and val != ')':
                token.append(val)
            # 2.处理运算符和界限符(就是括号)
            # 对于左括号来说 遇到就加入运算符栈中
            elif val == "(":
                ls.append(val)
            # 对于右括号 就依次将运算符栈中的操作符弹出到后缀表达式中，直到遇见左括号为止，然后删掉左括号
            elif val == ")":
                while ls[-1] != '(':
                    token.append(ls.pop())
                ls.pop()
            # 对于+-来说，运算优先级最低，当前运算符优先级<=栈顶运算符的优先级时，依次弹出运算符栈中的运算符加入后缀表达式中，直到遇见优先级更低的运算符或者左括号为止，再将当前运算符入栈
            elif val in ['+','-']:
                if len(ls) == 0:
                    ls.append(val)
                else:
                    # while len(ls) != 0 or ls[-1] != '(':
                    while len(ls) != 0 :
                        if ls[-1] != '(':
                            token.append(ls.pop())
                        else:
                            break
                    ls.append(val)
            # 对于*来说，运算优先级最高，当优先级>栈顶运算符时，直接入栈，否则依次弹出运算符栈中的运算符加入后缀表达式中，直到遇见优先级更低的运算符或者左括号为止，再将当前运算符入栈
            elif val == '*':
                if len(ls) == 0 or ls[-1] in ['+','-','(']:
                   ls.append(val)
                elif ls[-1] == '*':
                    while ls[-1] not in ['+','-','(']:
                        token.append(ls.pop())
                    ls.append(val)
        # 最后将运算符中剩余的运算符依次弹出到后缀表达式中
        while len(ls) != 0:
            token.append(ls.pop())
        # 最后得到后缀表达式token

        # 接着再对token进行值运算
        for i,val in enumerate(token):
            # 数字就入栈
            if (val != '+' and val != '-' and val != '*'):
                ls.append(val)
            # 运算符就出栈并运算，运算结果再入栈
            elif val == '+':
                new_num = int(ls.pop(-2)) + int(ls.pop(-1))
                ls.append(new_num)
            elif val == '-':
                new_num = int(ls.pop(-2)) - int(ls.pop(-1))
                ls.append(new_num)
            elif val == '*':
                new_num = int(ls.pop(-2)) * int(ls.pop(-1))
                ls.append(new_num)
        # 返回值也要记得int强转！！！不然会返回null
        return int(ls[-1])