题解 | 表达式求值

"""
https://blog.nowcoder.net/n/c8c1ff4ecfb44ca4958b1ecbdcbf2021
#print(ss.solve("(2*(3-4))*5"))  # -10
#print(ss.solve("(22*(3-4))*5"))  # 有多位数
#print(ss.solve("-5+10*2"))  # 第一个数为负数
print(ss.solve("(3+4)*(5+(2-3))"))  # 28

"""


import collections

class Solution:
    def calc(self,nums: collections.deque, ops: collections.deque):
        if len(nums) == 0 or len(nums) < 2:
            return
        if len(ops) == 0:
            return
        b = nums.pop()
        a = nums.pop()
        op = ops.pop()
        ans = 0
        if op == '+':
            ans = a + b
        elif op == '-':
            ans = a - b
        elif op == '*':
            ans = a * b
        nums.append(ans)
    def solve(self, s: str) -> int:
        map = dict()
        # 加减的优先级一样 ，乘的优先级为2
        map['+'] = 1
        map['-'] = 1
        map['*'] = 2
        # 将所有空格去掉
        s = s.replace(" ", "")
        n = len(s)
        # 存入所有数字
        nums = collections.deque()
        # 为了防止第一个数为负数 ，将0添加到队列
        nums.append(0)
        # 队列二 存入所有非数字
        ops = collections.deque()
        # 遍历字符
        #  字符为为“）”
        #for i in range(n):  # 多个数字会有问题
        i = 0
        while i < n:
            ch = s[i]
            if ch == '(':  #左括号
                ops.append(ch)
            elif ch == ')':  # 右括号
                # 计算到最后一个括号为止
                # 操作不为空/c
                while ops:
                    if ops[-1] != '(':
                        self.calc(nums, ops)

                    else:
                        ops.pop()
                        break# 弹出对应的左括号
            else:
                if ch.isdigit():
                    u = 0
                    j = i
                    # 将连续数字拼接
                    # 将 （- 替换为（0-
                    # (+ 替换为（0+
                    while j < n and s[j].isdigit():
                        u = u * 10 + int(s[j])
                        j = j + 1
                    i = j - 1
                    # 数字添加到nums
                    nums.append(u)
                else:  # 加减处理
                    if i > 0 and (s[i - 1] == '(' or s[i - 1] == '+' or s[i - 1] == '-'):
                        nums.append(0)

                    # 有一个新操作时候将栈内的可以计算的计算掉
                    # 只有满足【栈内运算符】比【当前运算符】优先计算
                    while len(ops) > 0 and ops[-1] != '(':
                        prev = ops[-1]
                        if map[prev] >= map[ch]:
                            self.calc(nums, ops)
                        else:
                            break
                    ops.append(ch)
            i += 1  # 指向下一个位置
        while len(ops) > 0 and ops[-1] != '(':
            self.calc(nums, ops)
        return nums[-1]