分治算法——241. 为运算表达式设计优先级-526互联

分治思路：
对于一个算式来说,总是可以根据运算符分为左右两部分算式,接着分别计算结果并合并；
每一个结果都是一个数组,包含这个算式的所有可能结果,计算时将左右两部分排列组合；
递归的终点是字符串是纯数字（即分到一个算式中只剩下一个数字）,直接返回。

比如示例中的2*3-4*5,有下面的分法：

1、分为2与3-4*5,对于3-4*5,继续细分

　　3-4*5可以分为3与4*5,或者3-4与5,所以结果为{-17,-5}
　　则这种分法产生的最终结果就是{-34,-10} （2*-17=-34, 2*-5=-10)

2、分为2*3与4*5,这种分法产生的结果就是{-14}
3、分为2*3-4与5,对于2-3*4,继续细分

2*3-4可以分为2与3-4,或者2*3与4,所以结果为{-2,2}
则这种分法产生的最终结果就是{-10,10}

最终结果是它们的结合,也就是{-34,-10,-14,-10,10},本题是不需要我们去重的。
不论是多复杂的算式,总是可以不断分而治之,递归得到各个部分的解。

class Solution {
public:
    vector<int> diffWaysToCompute(string expression) {
        vector<int> res;
        for (int i = 0; i < expression.size(); 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 m : left) {
                    for (int n : right) {
                        switch(c){
                        case '+': 
                            res.push_back(m + n);
                            break;  // 注意！一定要加break
                        case '-': 
                            res.push_back(m - n);
                            break;
                        case '*': 
                            res.push_back(m * n);
                            break;
                        }
                    }
                }
            }
        }

        if (res.empty()) {  // 递归出口：表达式中没有运算符，即只有一个纯数字
            res.push_back(std::stoi(expression));  
        }

        return res;
    }
};