为什么这里的双for循环用于递归？

Question

def diff_ways_to_evaluate_expression(s):
    result = []
    if "+" not in s and "-" not in s and "*" not in s:
        result.append(int(s))

    for i in range(len(s)):
        char = s[i]
        if not char.isdigit():
            leftPart = diff_ways_to_evaluate_expression(s[0:i])
            rightPart = diff_ways_to_evaluate_expression(s[i+1:])

            for part1 in leftPart:  #<---- 
                for part2 in rightPart:   #<-----
                    if char == "+":
                        result.append(part1 + part2)
                    elif char == "-":
                        result.append(part1 - part2)
                    elif char == "*":
                        result.append(part1 * part2)
    return result

def main():
    print("Expression evaluations: " + str(diff_ways_to_evaluate_expression("2*3-4-5")))

main()

这段代码接受一系列数字和运算，并打印出它能打印出的所有可能的值。例如2*（3-（4-5））=8

我试着在纸上画出来，看看递归在做什么，但就我的一生而言，我不明白为什么要像代码中指出的那样做double for循环。他们到底在做什么？如果我做了以下事情，为什么我会得到不同的答案（对我来说，他们似乎做了相同的事情）：

def diff_ways_to_evaluate_expression(s):
    result = []
    if "+" not in s and "-" not in s and "*" not in s:
        result.append(int(s))

    for i in range(len(s)):
        char = s[i]
        if not char.isdigit():
            leftPart = diff_ways_to_evaluate_expression(s[0:i])
            rightPart = diff_ways_to_evaluate_expression(s[i+1:])


            if char == "+":
                result.append(leftPart[0] + rightPart[0])
            elif char == "-":
                result.append(leftPart[0] - rightPart[0])
            elif char == "*":
                result.append(leftPart[0] * rightPart[0])
    return result


def main():
    print("Expression evaluations: " + str(diff_ways_to_evaluate_expression("2*3-4-5")))

main()

答案是错误的，但他们不是在做同样的事情吗？双for循环到底在做什么

Answer 1

让我们举一个例子：

2*3-4-5+6*7

外部循环用于从这五个操作符中选择一个操作符。我们找到的第一个运算符位于i==1。但是让我们关注一下当i==5时会发生什么。进行两次递归调用：

• 一个用于2*3-4
• 一个用于5+6*7

现在让我们暂时假设这些递归调用正确地完成了它们的工作，然后我们返回：

• leftPart=[-2, 2]因为我们可以做2*(3-4)或(2*3)-4
• rightPart=[47, 77]因为我们可以做5+(6*7)或(5+6)*7

对于i==5，我们有-操作符。因为我们有两种方法来计算它的左侧，还有两种方法来计算它的右侧，所以我们总共有2x2=4种可能性来应用这个中心-操作符：

当我们在左侧选择2*(3-4)时，有两种可能性；改变右侧：

• (2*(3-4))-(5+(6*7))
• (2*(3-4))-((5+6)*7)

…当我们选择左侧的(2*3)-4时，还有两个，同样改变右侧：

• (2*3)-4)-(5+(6*7))
• (2*3)-4)-((5+6)*7)

这正是double for循环所做的：在左侧迭代可能性，在右侧迭代每个可能性

在代码的错误版本中，您只考虑左边的第一个可能性（使用{{CD20>}），以及右边的第一个可能性（使用{{CD20>}），并且忽略与{{CD22>}或^ {CD2>}中的其他条目有关的所有组合。