题目：
给定一个含有数字和运算符的字符串，为表达式添加括号，改变其运算优先级以求出不同的结果。你需要给出所有可能的组合的结果。有效的运算符号包含 +, - 以及 * 。
示例：
image.png
思路：
分治法：
遍历字符串，以运算符作为划分值，将依次计算 运算符 左右两边的值；
一旦遇到运算符，进入划分，直到左、右子字符串是一个数字，例如：划分至 2 - 3
计算完以后，将结果存放到返回的数组里。
代码：
class Solution {
public List<Integer> diffWaysToCompute(String input) {
//创建一个新list集合，存储运算后的值
List<Integer> ways = new ArrayList<>();
//遍历字符串
for (int i = 0;i < input.length(); i++) {
char sp = input.charAt(i);
//如果遍历到运算符
if (sp == '+' || sp =='-' || sp == '*') {
//进行划分
//计算运算符左边的值
List<Integer> left = diffWaysToCompute(input.substring(0, i));
//计算运算符右边的值
List<Integer> right = diffWaysToCompute(input.substring(i + 1));
for (int l : left) {
for (int r : right) {
switch(sp) {
case '+':
ways.add(l + r);
break;
case '-':
ways.add(l - r);
break;
case '*':
ways.add(l * r);
break;
}
}
}
}
}
//递归出口，只剩下一个字符的时候
if (ways.size() == 0) {
ways.add(Integer.valueOf(input));
}
return ways;
}
}
时间复杂度：O(nlogn)，空间复杂度：O(n)
