题解 | #表达式求值#

解题思路：

1. 模拟栈
2. 字符串转表达式元素列表
3. 处理基本的运算问题
4. 运算符优先级比较
5. 考虑特殊情况（有括号，有些是负号）
6. 暴力提交，找到出错的用例，不断改进优化（以下代码不是最优的，但是能过所有用例，能力有限，惭愧。。。）

class Solution:
    def __init__(self):
        self._ch_list = list("+-*/()")
        self._oper_list = list("+-*/")
        self._digits_list = list("0123456789")

    def __get_labmbda_list(self, ch_list):
        """ 字符串转列表，合并对应的数字 """

        rnt = list()
        tmp_num = None
        for i in range(len(ch_list)):
            if ch_list[i] in self._ch_list:
                if tmp_num is not None:
                    rnt.append(str(tmp_num))
                    tmp_num = None
                rnt.append(ch_list[i])
            else:
                if tmp_num is None:
                    tmp_num = int(ch_list[i])
                else:
                    tmp_num = tmp_num*10 + int(ch_list[i])
        if tmp_num is not None:
            rnt.append(str(tmp_num))

        # 处理一些负数
        neg_rnt = list()
        for i in range(len(rnt)):
            if rnt[i].isdigit() and i > 0:
                if rnt[i-1] == "-":
                    if i == 1 or (i > 1 and rnt[i-2] == "("):
                        neg_rnt.pop()
                        neg_rnt.append(str(int(rnt[i]) * -1))
                        continue
            neg_rnt.append(rnt[i])
        return neg_rnt

    def __compare(self, oper_1, oper_2):
        """ 比较两个操作符的大小 """
        if oper_1 in ["+", "-"]:
            if oper_2 in ["+", "-"]:
                return 1
            else:
                return -2
        else:
            if oper_2 in ["+", "-"]:
                return 2
            else:
                return 1

    def __calc(self, num_1, num_2, oper_tmp):
        """ 计算 """
        if oper_tmp == "+":
            return num_1 + num_2
        elif oper_tmp == "-":
            return num_1 - num_2
        elif oper_tmp == "*":
            return num_1 * num_2
        else:
            return num_1 // num_2


    def solve(self, ch_list):
        """表达式计算"""


        # 1. 字符串转列表，合并对应的数字
        lambda_list = self.__get_labmbda_list(ch_list)

        # 2. 遍历表达式，压入数字栈和操作符栈
        stack_num, stack_oper = list(), list()
        for lam in lambda_list:
            if lam.isdigit() or len(lam) > 1:
                stack_num.append(int(lam))

                if len(stack_oper) > 0 and stack_oper[-1] in ["*", "/"]:
                    oper_tmp = stack_oper.pop()
                    num_2 = stack_num.pop()
                    num_1 = stack_num.pop()
                    stack_num.append(self.__calc(num_1, num_2, oper_tmp))
            else:
                if lam == ")":
                    # 优先括号里面的运算

                    while stack_oper[-1] != "(":
                        oper_tmp = stack_oper.pop()
                        if len(stack_num) >= 2:
                            num_2 = stack_num.pop()
                            num_1 = stack_num.pop()
                            stack_num.append(self.__calc(num_1, num_2, oper_tmp))
                        else:
                            break
                    stack_oper.pop()

                elif lam == "(":
                    # 左括号添加到栈
                    stack_oper.append(lam)
                else:
                    if lam in self._oper_list:
                        if len(stack_oper) > 0 and stack_oper[-1] in self._oper_list:
                            if self.__compare(stack_oper[-1], lam) > 0:
                                oper_tmp = stack_oper.pop()
                                num_2 = stack_num.pop()
                                num_1 = stack_num.pop()
                                stack_num.append(self.__calc(num_1, num_2, oper_tmp))
                                stack_oper.append(lam)
                                continue
                    stack_oper.append(lam)

        # 解决剩余的表达式, 基本符合从右到左进行运算
        while len(stack_oper) > 0:
            oper_tmp = stack_oper.pop()
            if oper_tmp == "(":
                continue
            num_2 = stack_num.pop()
            num_1 = stack_num.pop()
            result_tmp = self.__calc(num_1, num_2, oper_tmp)
            stack_num.append(result_tmp)

        # return lambda_list
        # return stack_num, stack_oper
        return stack_num[0]

import sys
if __name__ == '__main__':
    is_IDE = False
    if is_IDE:
        fr = open("data/HJ54.txt", "r", encoding="utf-8")
    else:
        fr = sys.stdin

    solution = Solution()
    while True:
        line = fr.readline().strip().replace(" ", "")
        if line == "":
            break
        print(solution.solve(line))

    if is_IDE:
        fr.close()