241. 为运算表达式设计优先级

241. 为运算表达式设计优先级

原始题目链接：https://leetcode.cn/problems/different-ways-to-add-parentheses/

给你一个由数字和运算符组成的字符串 expression ，按不同优先级组合数字和运算符，计算并返回所有可能组合的结果。你可以 按任意顺序 返回答案。

示例 1：

输入：expression = “2-1-1”
输出：[0,2]
解释：
((2-1)-1) = 0
(2-(1-1)) = 2
示例 2：

输入：expression = “23-45”
输出：[-34,-14,-10,-10,10]
解释：
(2*(3-(45))) = -34
((23)-(45)) = -14
((2(3-4))5) = -10
(2((3-4)5)) = -10
(((23)-4)*5) = 10

提示：

1 <= expression.length <= 20
expression 由数字和算符 ‘+’、‘-’ 和 ‘*’ 组成。
输入表达式中的所有整数值在范围 [0, 99]

解题思路：

分治算法，以运算符为界限，分成左右两边子表达式，再继续分，直到是数字（递归结束标志），再判断运算符进行合并。

代码实现：

class Solution:
    def diffWaysToCompute(self, expression: str) -> List[int]:
        # 递归结束标志：只有数字，直接返回数字
        if expression.isdigit():
            return [int(expression)]

        ans = []

        for i, c in enumerate(expression):
            # 遇到运算符就拆分，分别计算左右两侧的子表达式的值
            if c in "+-*":
                left = self.diffWaysToCompute(expression[:i])
                right = self.diffWaysToCompute(expression[i + 1:])

                # 合并拆分子表达式的值
                for l in left:
                    for r in right:
                        if c == '+':
                            ans.append(l + r)
                        if c == '-':
                            ans.append(l - r)
                        if c == '*':
                            ans.append(l * r)
        return ans

参考文献：
https://leetcode.cn/problems/different-ways-to-add-parentheses/solution/pythongolang-fen-zhi-suan-fa-by-jalan/