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

题目：

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

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

---

示例 1：

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

---

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

---

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/different-ways-to-add-parentheses
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

---

思路：

本题，将字符串的运算符作为中间节点，左侧分为一组，右侧分为一组。
递归得到，左边字符串的组合结果和右边字符串的结果。
然后将左右字符串的结果通过运算符合并起来。

---

代码：

class Solution {
public:
    vector<int> diffWaysToCompute(string expression) {
        vector<int> ways;
        int len=expression.size();
        //到达边界
        if(len==1||len==2){
            ways.push_back(stoi(expression));
            return ways;
        }
        for(int i=0;i<len;i++){
            int c=expression[i];
            if(c=='+'||c=='-'||c=='*'){
                //分解得到左边字符串的组合结果
               vector<int> left_ways=diffWaysToCompute(expression.substr(0,i));
                //分解得到右边字符串的组合结果
                vector<int> right_ways=diffWaysToCompute(expression.substr(i+1));
                //将组合结果通过运算符组合
                for(auto &l:left_ways){
                    for(auto &r:right_ways){
                        switch(c){
                            case '+': ways.push_back(l+r); break;
                            case '-': ways.push_back(l-r); break;
                            case '*': ways.push_back(l*r); break;
                        }
                    }
                }
            }
        }
        //返回合并后的结果
        return ways;
    }
};