<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 {
    int op(int num1, int num2, char sym) const noexcept {
        switch(sym) {
            case '+':
                return num1 + num2;
            case '-':
                return num1 - num2;
            case '*':
                return num1 * num2;
            default:
                cout << num1 << " " << sym << " " << num2 << "\n";
                throw invalid_argument("not expected");
        }
    }

    template<typename T>
    using Iterator = vector<T>::iterator;

    vector<int> getComputations(Iterator<int> numsBegin, Iterator<int> numsEnd, Iterator<char> symsBegin) const {
        if (next(numsBegin) == numsEnd) {
            return { *numsBegin };
        }

        if (next(numsBegin, 2) == numsEnd) {
            return { op(*numsBegin, *(++numsBegin), *symsBegin) };
        }

        vector<int> results;
        auto itrNums = numsBegin;
        ++itrNums;
        auto itrSyms = symsBegin;
        for (; itrNums != numsEnd ; ++itrNums, ++itrSyms) {
            auto firstHalf = getComputations(numsBegin, itrNums, symsBegin);
            auto secondHalf = getComputations(itrNums, numsEnd, next(itrSyms));

            for (auto num1: firstHalf) {
                for (auto num2: secondHalf) {
                    results.push_back(op(num1, num2, *itrSyms));
                }
            }
        }
        return results;
    }

    pair<vector<int>, vector<char>> parse(const string& expression) const {
        auto* first = expression.c_str();
        auto* last = first + expression.size();

        vector<int> nums;
        vector<char> syms;
        int value;
        auto ptr = from_chars(first, last, value).ptr;
        while (ptr != last) {
            nums.push_back(value);
            syms.push_back(*ptr);
            first = ptr + 1;
            ptr = from_chars(first, last, value).ptr;
        }
        nums.push_back(value);

        return { nums, syms };
    } 

public:
    vector<int> diffWaysToCompute(string expression) {
        auto [nums, syms] = parse(expression);
        return getComputations(nums.begin(), nums.end(), syms.begin());
    }
};
11900