<p>Given a string <code>expression</code> of numbers and operators, return <em>all possible results from computing all the different possible ways to group numbers and operators</em>. You may return the answer in <strong>any order</strong>.</p>

<p>The test cases are generated such that the output values fit in a 32-bit integer and the number of different results does not exceed <code>10<sup>4</sup></code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> expression = &quot;2-1-1&quot;
<strong>Output:</strong> [0,2]
<strong>Explanation:</strong>
((2-1)-1) = 0 
(2-(1-1)) = 2
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> expression = &quot;2*3-4*5&quot;
<strong>Output:</strong> [-34,-14,-10,-10,10]
<strong>Explanation:</strong>
(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
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= expression.length &lt;= 20</code></li>
	<li><code>expression</code> consists of digits and the operator <code>&#39;+&#39;</code>, <code>&#39;-&#39;</code>, and <code>&#39;*&#39;</code>.</li>
	<li>All the integer values in the input expression are in the range <code>[0, 99]</code>.</li>
</ul>

class Solution {
public:
    int getNumFromString(string str) {
        int num = 0, n = str.length();
        if (n == 0) return num;
        bool neg = str[0] == '-';
        for (int i = neg ? 1 : 0; i < n; i++) {
            num *= 10;
            num += (int)str[i] - 48;
        }
        return neg ? 0 - num : num;
    }

    vector<string> tokenize(string expression) {
        vector<string> tokens;
        string num = "";
        for (char c : expression) {
            if (isdigit(c))
                num += c;
            else {
                tokens.push_back(num);
                num = "";
                tokens.push_back(string(1, c));
            }
        }
        if (num != "")
            tokens.push_back(num);
        return tokens;
    }

    vector<int> operate(vector<int> &a, vector<int> &b, string op, vector<int> &res) {
        for (int i = 0; i < (int)a.size(); i++) {
            for (int j = 0; j < (int)b.size(); j++) {
                if (op == "+")
                    res.push_back(a[i] + b[j]);
                else if (op == "-")
                    res.push_back(a[i] - b[j]);
                else
                    res.push_back(a[i] * b[j]);
            }
        }
        return res;
    }

    vector<int> func(vector<string> &tokens, int l, int r) {
        // cout << l << " " << r  << endl;
        if (l == r)
            return {getNumFromString(tokens[l])};
        vector<int> res;
        for (int i = l; i <= r; i++) {
            char test = tokens[i][0];
            if (!isdigit(test)) {
                string op = tokens[i];
                vector<int> left = func(tokens, l, i - 1);
                vector<int> right = func(tokens, i + 1, r);
                operate(left, right, op, res);
            }
        }
        return res;
    }

    vector<int> diffWaysToCompute(string expression) {
        vector<string> tokens = tokenize(expression);
        return func(tokens, 0, tokens.size() - 1);
    }
};
14900