leetcode241.运算表达式设计优先级的一些解惑

题目——leetcode241

给定一个含有数字和运算符的字符串，为表达式添加括号，改变其运算优先级以求出不同的结果。你需要给出所有可能的组合的结果。有效的运算符号包含 +, - 以及 * 。

链接：力扣（LeetCode）241题

示例

示例1

输入: “2-1-1”
输出: [0, 2]
解释:
((2-1)-1) = 0
(2-(1-1)) = 2

示例2

输入: “2 * 3- 4 * 5”
输出: [-34, -14, -10, -10, 10]
解释:
(2 * (3 - (4 * 5))) = -34
((2 * 3) - (4 * 5)) = -14
((2 * (3 - 4)) * 5) = -10
(2 * ((3 - 4) * 5)) = -10
(((2 * 3) - 4) * 5) = 10

思路——分治算法

算式结果的不同是由不同的组合形成的，我们可以碰到一个运算符就把式子分成左右两部分，分别计算出结果后，再用分隔的那个运算符对两个结果进行计算。如2-1-1，在第一个减号，分成2和1-1，于是得到2-0=2；再往后走，在第二个减号把式子分成2-1和1，于是得到1-1=0。

所以我们可以用分治算法把整个式子分解成一个一个小式子，计算后合并得到结果。用for循环扫描整个式子，遇到运算符则分成左右两个式子，左边式子得到左边部分计算得到的所有结果，右边式子得到右边部分计算得到的所有结果。然后左边的结果和右边的结果进行组合得到整个式子的所有结果。我们用递归一步步实现它。

代码

class Solution {
public List<Integer> diffWaysToCompute(String input) {
return partition(input);
}
private List<Integer> partition(String input)
{
List<Integer> result=new ArrayList<>();
//如果只有数字了，则直接返回，这时result的size=1
if(!input.contains("+")&&!input.contains("-")&&!input.contains("*"))
{
result.add(Integer.parseInt(input));
return result;
}
for(int i=0;i<input.length();i++)
if(input.charAt(i)=='+'||input.charAt(i)=='-'||input.charAt(i)=='*')
//左右两边的结果进行组合
for(int left:partition(input.substring(0,i))) //存放input特定操作符左边部分所有结果的列表
for(int right:partition(input.substring(i+1,input.length()))) //存放input特定操作符右边部分所有结果的列表
if(input.charAt(i)=='+')
result.add(left+right);
else if(input.charAt(i)=='-')
result.add(left-right);
else //if(input.charAt(i)=='*')
result.add(left*right);
return result;
}
}

可能的疑惑

leetcode上所有解答大同小异，最初我在leetcode上看到解答代码时，我就觉得它返回的时候ArrayList总是只有一个数啊，因为在只有数字时返回的确实只有一个数。但是在left和right那里左右可能结果怎么变成多个数的。
于是我模拟了一遍，发现最初是在最外层for循环那里实现的：最外层for循环一直add，所以每次把字符串循环完了之后才返回的结果列表，其实在有两个运算符的字符串中最后就返回的有两个结果的列表。比如2 * 3 - 4 *5，在第三个运算符（ * ）那里，分成2 * 3 - 4和5。然后在计算2 * 3 - 4，它会先计算2（left）乘以3-4（right），result.add(-2)。但这时还没完，不会返回，因为for循环还没完。之后会计算2 * 3（left）减4（right），result.add(2)。这时这一层递归才回溯返回(-2,2)，然后分别和5组合。其实2 * 3 - 4 *5在到第一个运算符时的右边3 - 4 *5也是如此了，会返回两个结果再回溯和左边组合。就这样，回溯到最外层add右一个可能性后，最外层for循环前进，开始分割下一个操作符成左右两个子串进行递归。这样递归回溯得到最终结果。

最后

以上就是机灵万宝路为你收集整理的leetcode241.运算表达式设计优先级的一些解惑的全部内容，希望文章能够帮你解决leetcode241.运算表达式设计优先级的一些解惑所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。