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

---

一、题目描述

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

生成的测试用例满足其对应输出值符合 32 位整数范围，不同结果的数量不超过 10⁴ 。

示例 1

输入：expression = "2-1-1"
输出：[0,2]
解释：
((2-1)-1) = 0 
(2-(1-1)) = 2
1
2
3
4
5

示例 2

输入：expression = "2*3-4*5"
输出：[-34,-14,-10,-10,10]
解释：
(2*(3-(4*5))) = -34 
((2*3)-(4*5)) = -14 
((2*(3-4))*5) = -10 
(2*((3-4)*5)) = -10 
(((2*3)-4)*5) = 10
1
2
3
4
5
6
7
8

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

二、代码

代码如下：

class Solution:
    def diffWaysToCompute(self, expression: str) -> List[int]:
        def dfs(expression):
            result = []
            # 如果表达式中只有常数项，则添加进入结果中
            if '+' not in expression and '-' not in expression and '*' not in expression and '/' not in expression:
                result.append(expression)
            for i in range(len(expression)):
                if expression[i] in ['+', '-', '*', '/']:
                    for num_left in dfs(expression[:i]):
                        for num_right in dfs(expression[i + 1:]):
                            num = str(eval(num_left + expression[i] + num_right))
                            result.append(num)
            return result
        result = dfs(expression)
        print([int(e) for e in result])
        return [int(e) for e in result]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

---

三、解题思路

本题实际考验字符串中所有运算符的先后运算顺序，有多少个运算符，就有多少个对应数量的全排列结果。所以本题解采用递归的思想，通过字符串中所有的运算符运算的不同先后顺序来计算结果，将运算符左边和右边的表达式再分别进行递归操作，实现所有可能的运算结果，其中，使用eval()函数将字符串形式的表达式计算其结果。