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

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

我试图将其绘制在纸上以查看递归在做什么，但对于我的一生，我不明白为什么这必须执行代码中指示的双重 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 我们有 - 运算符。由于我们有 2 种方法来计算它的左侧，有 2 种方法来计算它的右侧，我们总共有 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)

这正是双 for 循环所做的：在左侧迭代可能性，并针对每个可能性在右侧迭代可能性。

在故障版本的代码中，你只会考虑左边的第一种可能性（使用leftPart[0]）和右边的第一种可能性（使用leftPart[0]），而忽略leftPart 或 rightPart.

中涉及其他条目的所有组合

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

why the double for loop here for recursion?

python

recursion

for-loop

nested-loops