Different Ways to Add Parentheses

Given a string of numbers and operators, return all possible results from computing all the different possible ways to group numbers and operators. The valid operators are+, - and *.
Example 1

Input: "2-1-1".

((2-1)-1) = 0
(2-(1-1)) = 2

Output: [0, 2]
Example 2

Input: "2*3-4*5"

(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

Output: [-34, -14, -10, -10, 10]

Credits:
Special thanks to @mithmatt for adding this problem and creating all test cases.

DFS approach. Divide and conquer.

Each time we split the input string into two parts separated by an operator.

Evaluate left part and right part separately, then merge their results according to the current operator that separates them.

//contain negative numbers?
//result overflow?
class Solution {
public:
    vector<int> diffWaysToCompute(string input) {
        vector<int> ans;
        ans = DFS(input);
        return ans;
    }
    vector<int> DFS(string input){
        vector<int> ans;
        if(input.size() == 0) return ans;
        int pos = 0;
        bool foundAnOperator = false;
        while(pos < input.size()){
            if(input[pos] <= '9' && input[pos] >= '0'){
                pos++;
            }else{
                // input[pos] is an operator
                foundAnOperator = true;
                vector<int> left = DFS(input.substr(0, pos));
                vector<int> right = DFS(input.substr(pos + 1, -1));
                //to be continued.
                for(auto it0 = left.begin(); it0 != left.end(); it0++){
                    for(auto it1 = right.begin(); it1 != right.end(); it1++){
                        switch(input[pos]){
                            case '+':
                                ans.push_back(*it0 + *it1);
                                break;
                            case '/':
                                ans.push_back(*it0 / *it1);
                                break;
                            case '-':
                                ans.push_back(*it0 - *it1);
                                break;
                            case '*':
                                ans.push_back(*it0 * *it1);
                                break;
                        }
                    }
                }
                pos++;
            }
        }
        if(foundAnOperator == false){
            // input string only contains one number, base condition
            ans.push_back(atoi(input.c_str()));
        }
        return ans;
    }
};