题目描述：

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

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

示例 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 {
public:
    vector<int> diffWaysToCompute(string expression) {
        vector<int> ans;//存储结果
        int n=expression.size();
        for(int i=0;i<n;++i){
            char c=expression[i];
            //遇到运算符进行计算
            if(c=='+'||c=='-'||c=='*'){
                //运算符左边
                vector<int> left=diffWaysToCompute(expression.substr(0,i));
                //运算符右边
                vector<int> right=diffWaysToCompute(expression.substr(i+1));
                //进行计算
                for(int& l : left){
                    for(int& r : right){
                        switch(c){
                            case '+':
                                ans.emplace_back(l+r);
                                break;
                            case '-':
                                ans.emplace_back(l-r);
                                break;
                            case '*':
                                ans.emplace_back(l*r);
                                break;
                        }
                    }
                }
            }
        }
        //若是单独的数字可以直接放到ans中
        if(ans.size()==0) ans.emplace_back(stoi(expression));
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

参考链接
https://leetcode.cn/problems/different-ways-to-add-parentheses/solution/cfen-zhi-by-heroding-3v1c/