241. Design priorities for operational expressions

solution:

        recursive + Divide and conquer

① Recursively save all the combinations of numbers generated on the left and right of the symbol

② Calculate the number combination of each layer through the return value

③ Recursively, only numbers are saved directly

class Solution {
public:
    vector<int> diffWaysToCompute(string expression) {
        vector<int> res;    // Define the return value 
        for(int i = 0;i < expression.size();i++) {
            char c = expression[i];
            if(c == '+' || c == '-' || c == '*') {
                auto res1 = diffWaysToCompute(expression.substr(0, i)); // Recursive decomposition 
                auto res2 = diffWaysToCompute(expression.substr(i + 1));
                
                // Yes res1 and res2 Conduct calculation results 
                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);
                    }
            }
        }

        // Recursion to the innermost layer , Save numbers directly 
        if(res.empty()){
        res.push_back(stoi(expression));
    }   
        return  res;
    }
};