为什么这里有用于递归的double 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

• One for 5+6*7

的

• One

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

• 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)

当我们在左侧选择...and时，再选择两个(2*3)-4，再次更改右侧：

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

这正是双for循环所要做的:在左侧迭代可能性，对每个可能性在右侧进行迭代。

在代码的故障版本中，您只考虑左边的第一种可能性(使用leftPart[0])和右边的第一种可能性(使用leftPart[0])，而忽略涉及leftPart或rightPart中其他条目的所有组合。