public List<Integer> diffWaysToCompute(String input){
  List<Integer> res=new LinkedList<>();
  for (int i=0; i < input.length(); i++) {
    char c=input.charAt(i);
    if (c == '*' || c == '-' || c == '+') {
      List<Integer> left=diffWaysToCompute(input.substring(0,i));
      List<Integer> right=diffWaysToCompute(input.substring(i + 1,input.length()));
      for (int j=0; j < left.size(); j++) {
        for (int k=0; k < right.size(); k++) {
          res.add(calculate(c,left.get(j),right.get(k)));
        }
      }
    }
  }
  if (res.size() == 0) {
    res.add(Integer.parseInt(input));
  }
  return res;
}

public List < Integer > diffWaysToCompute ( String input ) { List < Integer > res = new LinkedList < > ( ) ; for ( int i = 0 ; i < input . length ( ) ; i ++ ) { char c = input . charAt ( i ) ; if ( c == '*' || c == '-' || c == '+' ) { List < Integer > left = diffWaysToCompute ( input . substring ( 0 , i ) ) ; List < Integer > right = diffWaysToCompute ( input . substring ( i + 1 , input . length ( ) ) ) ; for ( int j = 0 ; j < left . size ( ) ; j ++ ) { for ( int k = 0 ; k < right . size ( ) ; k ++ ) { res . add ( calculate ( c , left . get ( j ) , right . get ( k ) ) ) ; } } } } if ( res . size ( ) == 0 ) { res . add ( Integer . parseInt ( input ) ) ; } return res ; }
divide and conquer . divide the input into sub - strings according to the operator : left and right . stop until there is no operator in the string , parse the integer and add it to result list . then combine left and right result lists with the operator to generate result .
