题目要求的是运算的不同顺序，所以即使两个运算顺序相同也是不同去重的。我们考虑两种运算顺序只要最后一个运算的运算符是不同位置的，那么就可以保证这两种运算顺序绝对不同，对吧！所以我们可以首先确定最后一个运算符，这样字符串就被分成了两部分，即子问题。我们对子问题递归求解就可以得到所有可能的运算结果。我们根据子问题的运算结果整合一下就是最终答案啦！
public class DiffWaysToCompute {
public static void main(String[] args) {
System.out.println(new DiffWaysToCompute().diffWaysToCompute("2*3-4*5"));
}
public List diffWaysToCompute(String expression) {
ArrayList res = new ArrayList<>(8);
boolean flag = true;
for (int i = 0; i < expression.length(); i++) {
if (expression.charAt(i) < '0' || expression.charAt(i) > '9') {
flag = false;
List lefts = diffWaysToCompute(expression.substring(0, i));
List rights = diffWaysToCompute(expression.substring(i + 1, expression.length()));
switch (expression.charAt(i)) {
case '+':
for (Integer left : lefts) {
for (Integer right : rights) {
res.add(left + right);
}
}
break;
case '-':
for (Integer left : lefts) {
for (Integer right : rights) {
res.add(left - right);
}
}
break;
case '*':
for (Integer left : lefts) {
for (Integer right : rights) {
if (left == null || right == null) {
}
res.add(left * right);
}
}
break;
}
}
}
if (flag) {
// 如果表达式中没有运算符，那么就直接返回表达式本身的值
res.add(Integer.parseInt(expression));
}
return res;
}
}
以上程序存在一些小问题，比如"-2"会递归错误，但是能通过 leetcode 所有测试
