力扣每日一题2022-07-01中等题：为运算表达式设计优先级

• • 题目描述
  • 思路
  • • 记忆化搜索
    • • Python实现

为运算表达式设计优先级

对expression进行预处理，把所有数字和运算符放入数组ops中，因为题目数据满足每个数字都在[0, 99]这个范围内，且运算符总共有三个，分别用-1，-2，-3分别表示+、-、*。因为对于表达式中某一个运算符op，将其左边可能的计算结果用left表示，右边的可能的计算结果用right表示。则以该运算符为该表达式的最后一步运算的情况的全部可能结果就是对应left和right中的元素对应该运算符操作的组合数。枚举表达式中全部运算符来作为left和right的分隔符来求得对应的集合，则该表达式的最终结果集就是这些集合的并集。

ADDITION = -1
SUBTRACTION = -2
MULTIPLICATION = -3

class Solution:
    def diffWaysToCompute(self, expression: str) -> List[int]:
        ops = []
        i, n = 0, len(expression)
        while i < n:
            if expression[i].isdigit():
                x = 0
                while i < n and expression[i].isdigit():
                    x = x * 10 + int(expression[i])
                    i += 1
                ops.append(x)
            else:
                if expression[i] == '+':
                    ops.append(ADDITION)
                elif expression[i] == '-':
                    ops.append(SUBTRACTION)
                else:
                    ops.append(MULTIPLICATION)
                i += 1
        @lru_cache(None)
        def dfs(l, r):
            if l == r:
                return [ops[l]]
            ans = []
            for i in range(l, r, 2):
                left = dfs(l, i)
                right = dfs(i+2, r)
                for x in left:
                    for y in right:
                        if ops[i + 1] == ADDITION:
                            ans.append(x + y)
                        elif ops[i + 1] == SUBTRACTION:
                            ans.append(x - y)
                        else:
                            ans.append(x * y)
            return ans
        return dfs(0, len(ops) - 1)