Different Ways to Add Parenthese

https://leetcode.com/problems/different-ways-to-add-parentheses/
给定一个数学计算式，求出这个计算式所有可能的值，这些不同的值是因为可以在不同的计算式之间加括号，计算符号包括加减乘
Example 1:
Input: "2-1-1"
Output: [0, 2]
Explanation:
((2-1)-1) = 0
(2-(1-1)) = 2
Example 2:
Input: "23-45"
Output: [-34, -14, -10, -10, 10]
Explanation:
(2(3-(45))) = -34
((23)-(45)) = -14
((2(3-4))5) = -10
(2((3-4)5)) = -10

解析

看起来像是一个加括号计算加减乘除的问题，实则是一个分治

func(String s){
  for(char c: String s){
    if (c is operator){
              left = fun( left substring);
              right = fun( right substring);
             out = left operator right;//加减乘
             res.add(out)
      }
  }
  if(res is empty){
      res.add(atoi(s))
  }
}

public List<Integer> diffWaysToCompute(String input) {

        List<Integer> res = new ArrayList<Integer>();
        for (int i = 0; i < input.length(); i++) {
            if (input.charAt(i) != '+' && input.charAt(i) != '-' && input.charAt(i) != '*') {
                continue;
            }
            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++) {
                    if (input.charAt(i) == '+') {
                        res.add(left.get(j) + right.get(k));
                    } else if (input.charAt(i) == '-') {
                        res.add(left.get(j) - right.get(k));
                    } else {
                        res.add(left.get(j) * right.get(k));
                    }
                }
            }
        }
        if (res.isEmpty()) {
            res.add(Integer.valueOf(input));
        }
        return res;
    }