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"Output: [0, 2]Explanation: ((2-1)-1) = 0 (2-(1-1)) = 2

Example 2:

Input: "2*3-4*5"Output: [-34, -14, -10, -10, 10]Explanation: (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

 

Approach #1: 

namespace studycat {    int add(int x, int y) { return x + y; }    int sub(int x, int y) { return x - y; }    int mul(int x, int y) { return x * y; }}class Solution {public:    vector
     
       diffWaysToCompute(string input) {        return helper(input);    }    private:    unordered_map
      

> memo; const vector

& helper(const string& input) { if (memo.count(input)) return memo[input]; vector

ans; for (int i = 0; i < input.length(); ++i) { char op = input[i]; if (op == '+' || op == '-' || op == '*') { const string left = input.substr(0, i); const string right = input.substr(i+1); const vector

& l = helper(left); const vector

& r = helper(right); std::function

f; switch(op) { case '+': f = studycat::add; break; case '-': f = studycat::sub; break; case '*': f = studycat::mul; break; } for (int i : l) for (int j : r) ans.push_back(f(i, j)); } } if (ans.empty()) ans.push_back(std::stoi(input)); memo[input].swap(ans); return memo[input]; }};