Given a string expression of numbers and operators, return all possible results from computing all the different possible ways to group numbers and operators. You may return the answer in any order.

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 104.

&nbsp;
Example 1:

Input: expression = "2-1-1"
Output: [0,2]
Explanation:
((2-1)-1) = 0 
(2-(1-1)) = 2


Example 2:

Input: expression = "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


&nbsp;
Constraints:


	1 &lt;= expression.length &lt;= 20
	expression consists of digits and the operator '+', '-', and '*'.
	All the integer values in the input expression are in the range [0, 99].


class Solution(object):
    def diffWaysToCompute(self, input):
        m = {}
        return self.dfs(input, m)
        
    def dfs(self, input, m):
        if input in m:
            return m[input]
        if input.isdigit():
            m[input] = int(input)
            return [int(input)]
        ret = []
        for i, c in enumerate(input):
            if c in "+-*":
                l = self.diffWaysToCompute(input[:i])
                r = self.diffWaysToCompute(input[i+1:])
                ret.extend(eval(str(x)+c+str(y)) for x in l for y in r)
        m[input] = ret
        return ret
class Solution {
    Map<String, List<Integer>> memo = new HashMap<>();
    public List<Integer> diffWaysToCompute(String expression) {
        List<Integer> res = new LinkedList<>();
        if(memo.containsKey(expression)) return memo.get(expression);

        for(int i = 0; i<expression.length(); i++){
            char c = expression.charAt(i);
            if(c == '*' || c == '+' || c == '-'){
                //divide
                List<Integer> left = diffWaysToCompute(expression.substring(0, i));
                List<Integer> right = diffWaysToCompute(expression.substring(i+1));

                //conquer
                for(int a : left){
                    for(int b : right){
                        if(c == '+'){
                            res.add(a+b);
                        }else if(c == '-'){
                            res.add(a - b);
                        }else if(c == '*'){
                            res.add(a * b);
                        }
                    }
                }
                
            }
        }
        //base case, when there is no operator
        if(res.isEmpty()){
            res.add(Integer.parseInt(expression));
        }
        memo.put(expression, res);
        return res;     
    }
}
class Solution {
public:
    
    int stoi1(string &s, int i, int j)
    {
        int num = 0;
        for (int k = i; k <= j; k++)
        {
            num = num * 10 + (s[k] - '0');
        }
        return num;
    }

    vector<int> rec(string &s, int i, int j, vector<vector<vector<int>>> &dp)
    {
        if(dp[i][j].size() > 0){
            return dp[i][j];
        }
        vector<int> ans;
        for (int k = i; k <= j; k++)
        {
            if(s[k] == '+' || s[k] == '*' || s[k] == '-'){
                vector<int> v1 = rec(s, i, k - 1, dp);
                vector<int> v2 = rec(s, k + 1, j, dp);
                for (int m = 0; m < v1.size(); m++)
                {
                    for (int n = 0; n < v2.size(); n++)
                    {
                        if (s[k] == '-')
                        {
                            ans.push_back(v1[m] - v2[n]);
                        }
                        else if (s[k] == '*')
                        {
                            ans.push_back(v1[m] * v2[n]);
                        }
                        else
                        {
                            ans.push_back(v1[m] + v2[n]);
                        }
                    }
                }
            }
        }
        if(ans.empty()){
            ans.push_back(stoi1(s,i,j));
        }
        return dp[i][j] = ans;
    }
    
    vector<int> diffWaysToCompute(string expression) {
        int n = expression.length() + 1;
        vector<vector<vector<int>>> dp(n, vector<vector<int>>(n, vector<int>()));
        return rec(expression, 0, expression.length()-1, dp);
    }
};
var diffWaysToCompute = function(expression) {
//     We can iterate through the expression character-by-character.
// we can break the expression into two halves whenever we get an operator (+, -, *).
// The two parts can be calculated by recursively calling the function.
// Once we have the evaluation results from the left and right halves, we can combine them to produce all results.
    
    return diffWaysRec({},expression)
    
};

function diffWaysRec(map, expression){
    if(expression in map){
        return map[expression]
    }
    let result = [];
    
    
    if(!(expression.includes("+")) && !(expression.includes("-")) && !(expression.includes("*"))){
        result.push(parseInt(expression))
    }else {
        
        for(let i =0; i<expression.length; i++){
            let char = expression[i];
            
            if(isNaN(parseInt(char,10))){
                //not a number , must it expression
                //calculate lest and right now
                let leftParts = diffWaysRec(map,expression.substring(0,i));
                let rightParts = diffWaysRec(map, expression.substring(i+1));
                for(let l = 0; l<leftParts.length; l++){
                    for(let r = 0; r<rightParts.length; r++){
                        let left = leftParts[l];
                        let right = rightParts[r];
                        
                        if(char === "+"){
                            result.push(parseInt(left) + parseInt(right))
                        }
                        if(char === "-"){
                            result.push(parseInt(left) - parseInt(right))
                        }
                        if(char === "*"){
                            result.push(parseInt(left) * parseInt(right))
                        }
                    }
                }
                
            }
        }
    }
    
    map[expression] = result;
    return result;
    
}
Different Ways to Add Parentheses