# Bottom up dp AC solution

• ``````  public List<Integer> diffWaysToCompute(String input) {
List<String> tokens = tokenize(input);
int size = tokens.size() / 2;
List<List<List<Integer>>> result = new ArrayList<>();
// init
for(int i = 0; i < input.length(); i++)

for(int row = 0; row <= size; row++){
for(int col = 0; col <= size; col++){
}
}

for(int row = size; row >= 0; row--){
for(int col = row; col <= size; col++){
if(col == row)
else{
for(int split = col - 1; split >= 0; split--){
List<Integer> tmp = cross_result(tokens.get(split*2+1), result.get(row).get(split), result.get(split+1).get(col));
}
}
}
}
return result.get(0).get(size);
}

// Given two lists and an operator, we apply operator on each pair from l1 and l2
private List<Integer> cross_result(String op, List<Integer> l1, List<Integer> l2){
List<Integer> result = new ArrayList<>();
for(int i1 : l1){
for(int i2 : l2)
}
return result;
}

private int compute(String op, int arg1, int arg2){
int val = 0;
if(op.equals("+")) val = arg1 + arg2;
else if(op.equals("-")) val = arg1 - arg2;
else val = arg1 * arg2;
return val;
}

// Convert expression to a list of tokens, each token is either a number or an operator
private List<String> tokenize(String input){
List<String> list = new ArrayList<>();
int start = 0, end = 0;
while(end < input.length()){
char cur = input.charAt(end);
if(is_char(cur)){
start = end + 1;
end = start;
}else{
end++;
}
}