241 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]

Solution

class Solution {
public:
    vector<int> calculate(vector<int> nums, vector<char> signs, int s1, int s2) {
        vector<int> res;
        if ( s1 > s2 ) {
            res.push_back(nums[s1]);
            return res;
        }
        for ( int i = s1; i <= s2; i++ ) {
            vector<int> res1 = calculate(nums, signs, s1, i-1);
            vector<int> res2 = calculate(nums, signs, i+1, s2);
            int n1 = res1.size(), n2 = res2.size();
            for ( int i1 = 0; i1 <= n1-1; i1++) {
                for ( int i2 = 0; i2 <= n2-1; i2++ ) {
                    if ( signs[i] == '+' ) res.push_back(res1[i1] + res2[i2]);
                    if ( signs[i] == '-' ) res.push_back(res1[i1] - res2[i2]);
                    if ( signs[i] == '*' ) res.push_back(res1[i1] * res2[i2]);
                }
            }
        }
        return res;
    }
    vector<int> diffWaysToCompute(string input) {
        int n = input.size();
        vector<int> res;
        if ( n == 0 ) return res;
        vector<int> nums;
        vector<char> signs;
        string tmp = "";
        for ( int i = 0; i <= n-1; i++ ) {
            if ( input[i] >= '0' and input[i] <= '9' ) tmp += input[i];
            else {
                nums.push_back(stoi(tmp));
                tmp = "";
                signs.push_back(input[i]);
            }
        }
        nums.push_back(stoi(tmp));
        int ns = signs.size();
        res = calculate(nums, signs, 0, ns-1);
        return res;
    }
};

Notes
Similar to "Catlan Number" problem.