Java 表达式求值中左右嵌套循环的区别

Question

基本上，我们有数字和运算符的字符串表达式，并且输出必须通过计算对数字和运算符进行分组的所有不同可能方式来返回所有可能的结果。通过将运算放在括号中可以得到不同的结果。

Example 1:
Input: expression = "2-1-1"
Output: [0,2]
Explanation:
((2-1)-1) = 0
(2-(1-1)) = 2
Example 2:

Input: expression = "2*3-4*5"
Output: [-34,-14,-10,-10,10]
Explanation:
(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

这是我的代码片段

class Solution {
    public List<Integer> diffWaysToCompute(String expression) {
        ArrayList <Integer> result = new ArrayList<Integer>();
        if (!expression.contains("+") && !expression.contains("-") && !expression.contains("*")) {
            result.add(Integer.parseInt(expression));            
        }
        
        for(int i=0 ; i<expression.length()-1 ; i++){
            if(expression.charAt(i) == '+' || expression.charAt(i) == '-' || expression.charAt(i) == '*'){
                String leftpart = expression.substring(0,i);
                String rightpart = expression.substring(i+1);                
                List <Integer> leftresults = diffWaysToCompute(leftpart);
                List <Integer> rightresults = diffWaysToCompute(rightpart);
                for (int left : leftresults) {
                    for (int right : rightresults) {
                        if (expression.charAt(i) == '+') {
                            result.add(left + right);
                        } else if (expression.charAt(i) == '-') {
                            result.add(left - right);
                        } else if (expression.charAt(i) == '*') {
                            result.add(left * right);
                        }
                    }
                }
            }                
        }                            
        return result;
    }
}

我不明白右循环的部分嵌套在左循环中。如果我们尝试将左侧嵌套在右侧会发生什么？这两者有什么区别？

for (int left : leftresults) {
    for (int right : rightresults) {

for (int right : rightresults) {
    for (int left : leftresults) {

Answer 1

您的代码采用数学表达式（例如“23-45”）并找到所有可能的计算方法。

工作原理：

1. 检查表达式中是否有运算符（+、-、*）。如果不是，只需将其转换为数字即可。

2. 查看表达式中的每个字符。如果是运营商： 在该运算符处将表达式拆分为两部分。

3. 递归计算每个部分的所有可能结果。 使用运算符（+、-、*）合并两个部分的结果。

问题： 如果您首先调用右列表，则代码会混淆两部分结果的顺序。它应该将左侧部分的结果与右侧部分的结果配对，而不是将右侧部分的结果与左侧部分的结果配对。

示例： 表达：“23-45” 正确配对：(23) - (45) 错误配对：(45) - (23)

由于正确的顺序很重要，我按照从右到左的顺序运行了上面的代码 -

代码-

class Solution {
public List<Integer> diffWaysToCompute(String expression) {
    ArrayList<Integer> result = new ArrayList<>();
    if (!expression.contains("+") && !expression.contains("-") && !expression.contains("*")) {
        result.add(Integer.parseInt(expression));
    }
    
    for (int i = expression.length() - 1; i > 0; i--) {
        if (expression.charAt(i) == '+' || expression.charAt(i) == '-' || expression.charAt(i) == '*') {
            String leftpart = expression.substring(0, i);
            String rightpart = expression.substring(i + 1);
            List<Integer> leftresults = diffWaysToCompute(leftpart);
            List<Integer> rightresults = diffWaysToCompute(rightpart);
            for (int right : rightresults) {
                for (int left : leftresults) {
                    if (expression.charAt(i) == '+') {
                        result.add(left + right);
                    } else if (expression.charAt(i) == '-') {
                        result.add(left - right);
                    } else if (expression.charAt(i) == '*') {
                        result.add(left * right);
                    }
                }
            }
        }
    }
    return result;
}

} 输出 - [-34, -10, 10, -14]