# Leetcode Different Ways to Add Parentheses problem solution

In this Leetcode Different Ways to Add Parentheses problem solution we have 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.

## Problem solution in Python.

```class Solution(object):
def __init__( self):
self.d = dict()

def diffWaysToCompute(self, input):
"""
:type input: str
:rtype: List[int]
"""
if input in self.d:
return self.d[input]
if input.isnumeric():
return [ int(input) ]
i = 0
curr = ""
res = []

while( i < len( input ) ):
if not input[i].isnumeric():
x = self.diffWaysToCompute( curr )
y = self.diffWaysToCompute( input[i+1:])
for xi in x:
for yi in y:
if input[i] == "-":
res.append( xi-yi )
elif input[i] == "+":
res.append( xi+yi )
elif input[i] == "*":
res.append( xi*yi )
curr += input[i]
i+=1
self.d[input] = res
return res
```

## Problem solution in Java.

```class Solution {
Map<String, List<Integer>> cache;

public List<Integer> diffWaysToCompute(String input) {
//create cache
cache = new HashMap<>(input.length()*input.length());

return compute(input);
}

private List<Integer> compute(String string) {
List<Integer> result = cache.get(string);
if (result != null)
//return result from cache
return result;

result = new ArrayList<>();

for (int pos = 0; pos < string.length(); pos++) {
//trick to avoid mutiple comparisons with +/-/*
if (string.charAt(pos) < '0') {
List<Integer> leftList = compute(string.substring(0, pos));
List<Integer> rightList = compute(string.substring(pos+1));

for (int left : leftList) {
for (int right : rightList) {

switch(string.charAt(pos)) {
}

}
}
}

}

cache.put(string, result);
return result;
}

}
```

## Problem solution in C++.

```class Solution {
public:
vector<int> diffWaysToCompute(string input) {
if(input.length()==0)return {};
return helper(input, 0, input.length());
}
vector<int>helper(string str, int start, int end){
vector<int>res, left, right;
for(int i=start; i< end; i++ ){
if(str[i]=='+'||str[i]=='-'||str[i]=='*'){
left=helper(str, start, i);
right=helper(str, i+1, end);
for(auto & l :left)
for(auto & r: right){
if(str[i]=='+')res.push_back(l+r);
else if(str[i]=='-')res.push_back(l-r);
else res.push_back(l*r);
}
}
}
if(res.empty())res.push_back(stoi(str.substr(start, end-start+1)));

return res;
}
};
```

## Problem solution in C.

```int* diffWaysToCompute(char* input, int* returnSize) {
int len=strlen(input);
int *ret=(int*)calloc(2000,sizeof(int));
int *left=NULL;
int *right=NULL;
int left_count=0;
int right_count=0;
*returnSize=0;
int count=0;
bool isNum=true;
for(int i=0;i<len;i++){
if(input[i]<'0'||input[i]>'9'){
isNum=false;
char temp=input[i];
input[i]='\0';
left=diffWaysToCompute(input,&left_count);
right=diffWaysToCompute(&input[i+1],&right_count);
for(int l=0;l<left_count;l++){
for(int r=0;r<right_count;r++){
if(temp=='+'){
ret[(*returnSize)++]=left[l]+right[r];
}else if(temp=='-'){
ret[(*returnSize)++]=left[l]-right[r];
}else if(temp=='*'){
ret[(*returnSize)++]=left[l]*right[r];
}
}
}
input[i]=temp;
}
}
if(isNum){
ret[(*returnSize)++]=atoi(input);
}
return ret;
}
```