241. Different Ways to Add Parentheses

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

((2-1)-1) = 0
(2-(1-1)) = 2

Output: [0, 2]

Example 2

Input: "2*3-4*5"

(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

Output: [-34, -14, -10, -10, 10]




Solution:

Recursion:

Example 2:

2*3-4*5,

First operator:

Left = diffWaysToCompute("2");  result: {2};

Right= diffWaysToCompute("3-4*5") result {3- diffWaysToCompute("4*5"), diffWaysToCompute("3-4") *5)  => {3-(4*5), (3-4)*5} => {-17,-5}

So Result Left* Right => {-34,-10}

Second operator:

Left=diffWaysToCompute("2*3") => {6}

Right=diffWaysToCompute("4*5") =>{20}

Result Left-Right => {-14}

Third operator:

Left= diffWaysToCompute("2*3-4"); similarly => {(2*3)-4, 2*(3-4)}=> {2,-2}

Right=diffWaysToCompute(5); => {5}

Result Left * Right=> {10,-10}

So the final result should be {-34,-10,-14,-10,10}

 public List<Integer> diffWaysToCompute(String input) {  
     if(input==null || input.length()==0) return new ArrayList<Integer>();  
     List<Integer> res=new ArrayList<Integer>();  
     for(int i=0;i<input.length();i++){  
       char c=input.charAt(i);  
       if(!Character.isDigit(c)){  
         List<Integer> op1=diffWaysToCompute(input.substring(0,i));  
         List<Integer> op2=diffWaysToCompute(input.substring(i+1));  
           for(int m: op1){  
             for(int n: op2){  
               if(c=='+') res.add(m+n);  
               else if(c=='-') res.add(m-n);  
               else res.add(m*n);  
             }  
           }  
       }  
     }  
     if(res.size()==0) res.add(Integer.parseInt(input));  
     return res;  
   }