241. Different Ways to Add Parentheses - cocoder39/coco39_LC GitHub Wiki

class Solution {
public:
    vector<int> diffWaysToCompute(string input) {
        return helper(input, 0, input.length() - 1);
    }
private:
    vector<int> helper(string& input, int start, int end) {
        vector<int> res;
        
        for (int i = start + 1; i < end; i++) {
            if (input[i] == '+' || input[i] == '-' || input[i] == '*') {
                vector<int> lefts = helper(input, start, i - 1);
                vector<int> rights = helper(input, i + 1, end);
                for (auto left : lefts) {
                    for (auto right : rights) {
                        int num;
                        switch (input[i]) {
                            case '+':   num = left + right;
                                        break;
                            case '-':   num = left - right;
                                        break;
                            case '*':   num = left * right;
                                        break;
                        }
                        res.push_back(num);
                    }
                }
            }
        }
        
        if (res.empty()) { //pure digits
            string str = input.substr(start, end - start + 1);
            res.push_back(stoi(str));
        }
        return res;
    }
};