Different ways to add parenthesis

Problem : Given a string of numbers and operators return all possible results from computing all the different possible ways to group numbers and operators, all the valid operators are '+',  '-',  '*'.
Basic Idea is to start from left and move towards right recursively while calculating the result of every pair bases on the operator in between them. for ex :
(2-(1-1))
(2-1) -1)
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]

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72

public class Solution { public List<Integer> diffWaysToCompute(String input) { List<Integer> result = new ArrayList<Integer>(); for(int i = 0;i < input.length(); i++){ if(input.charAt(i) == '+' || input.charAt(i) == '-' || input.charAt(i) == '*'){ List<Integer> left = diffWaysToCompute(input.substring(0,i)); List<Integer> right = diffWaysToCompute(input.substring(i+1)); for(int j = 0; j < left.size(); j++){ for(int k = 0; k < right.size(); k++){ switch (input.charAt(i)){ case '+' : result.add(left.get(j) + right.get(k)); break; case '-' : result.add(left.get(j) - right.get(k)); break; case '*' : result.add(left.get(j) * right.get(k)); break; default : break; } } } } } if(result.size() == 0 ){ result.add(atoi(input)); } return result; } public static int atoi(String str) { if (str == null || str.length() < 1) return 0; // trim white spaces str = str.trim(); char flag = '+'; // check negative or positive int i = 0; if (str.charAt(0) == '-') { flag = '-'; i++; } else if (str.charAt(0) == '+') { i++; } // use double to store result double result = 0; // calculate value while (str.length() > i && str.charAt(i) >= '0' && str.charAt(i) <= '9') { result = result * 10 + (str.charAt(i) - '0'); i++; } if (flag == '-') result = -result; // handle max and min if (result > Integer.MAX_VALUE) return Integer.MAX_VALUE; if (result < Integer.MIN_VALUE) return Integer.MIN_VALUE; return (int) result; } }