给定一个含有数字和运算符的字符串,为表达式添加括号,改变其运算优先级以求出不同的结果。你需要给出所有可能的组合的结果。有效的运算符号包含
+
,-
以及*
。
解题思路
substring
方法使用public String substring(int beginIndex)
public String substring(int beginIndex, int endIndex)
beginIndex -- 起始索引(包括)。
endIndex -- 结束索引(不包括)。
- 运用递归函数的定义,确定递归函数的base case
static List<Integer> diffWaysToCompute(String input) {
List<Integer> res = new ArrayList<>();
for (int i = 0; i < input.length(); i++) {
char c = input.charAt(i);
// 扫描算式 input 中的运算符
if (c == '-' || c == '*' || c == '+') {
/****** 分 ******/
// 以运算符为中心,分割成两个字符串,分别递归计算
List<Integer>
left = diffWaysToCompute(input.substring(0, i));
List<Integer>
right = diffWaysToCompute(input.substring(i + 1));
/****** 治 ******/
// 通过子问题的结果,合成原问题的结果
for (int a : left) {
for (int b : right) {
if (c == '+') {
res.add(a + b);
} else if (c == '-') {
res.add(a - b);
} else if (c == '*') {
res.add(a * b);
}
}
}
}
}
// base case
// 如果 res 为空,说明算式是一个数字,没有运算符
if (res.isEmpty()) {
res.add(Integer.parseInt(input));
}
return res;
}
Q.E.D.