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

solution:

        递归+分治

① 递归保存符号左边和右边产生的所有数字组合方式

② 通过返回值计算每一层的数字组合

③ 递归的到只有数字直接保存

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 == '*') {
                auto res1 = diffWaysToCompute(expression.substr(0, i)); //递归分解
                auto res2 = diffWaysToCompute(expression.substr(i + 1));
                
                //对res1和res2进行计算结果
                for(auto &x : res1)
                    for(auto &y : res2) {
                        if(c == '+') res.push_back(x + y);
                        else if(c == '-') res.push_back(x - y);
                        else if(c == '*') res.push_back(x * y);
                    }
            }
        }

        //递归到最里面一层,直接保存数字
        if(res.empty()){
        res.push_back(stoi(expression));
    }   
        return  res;
    }
};