无法通过递归枚举所有的算术表达式

Question

我想根据给定的有序数字集生成涉及 +、-、* 和 / 的所有可能表达式：

class Node:
    def __init__(self, data):
        self.left = None
        self.right = None
        self.data = data

    def is_leaf(self):
        if self.left is None:
            assert self.right is None
            return True
        return False

    def __repr__(self):
        if self.is_leaf():
            return repr(self.data)
        return '(%s%s%s)' % (self.left, self.data, self.right)


def enumerate_trees(numbers):
    n = len(numbers)
    if n == 1:
        yield Node(numbers[0])
    else:
        for i in range(1, n):
            left_subtrees = enumerate_trees(numbers[:i])
            right_subtrees = enumerate_trees(numbers[i:])
            for left in left_subtrees:
                for right in right_subtrees:
                    for op in ['+', '-', '*', '/']:
                        root = Node(op)
                        root.left = left
                        root.right = right
                        yield root


if __name__ == '__main__':
    for tree in enumerate_trees([5, 7, 10, 1]):
        print(repr(tree)[1:-1])

输出为：

5+(7+(10+1))
5-(7+(10+1))
5*(7+(10+1))
5/(7+(10+1))
5+(7-(10+1))
5-(7-(10+1))
5*(7-(10+1))
5/(7-(10+1))
5+(7*(10+1))
5-(7*(10+1))
5*(7*(10+1))
5/(7*(10+1))
5+(7/(10+1))
5-(7/(10+1))
5*(7/(10+1))
5/(7/(10+1))
5+(7+(10-1))
5-(7+(10-1))
5*(7+(10-1))
5/(7+(10-1))
5+(7-(10-1))
5-(7-(10-1))
5*(7-(10-1))
5/(7-(10-1))
5+(7*(10-1))
5-(7*(10-1))
5*(7*(10-1))
5/(7*(10-1))
5+(7/(10-1))
5-(7/(10-1))
5*(7/(10-1))
5/(7/(10-1))
5+(7+(10*1))
5-(7+(10*1))
5*(7+(10*1))
5/(7+(10*1))
5+(7-(10*1))
5-(7-(10*1))
5*(7-(10*1))
5/(7-(10*1))
5+(7*(10*1))
5-(7*(10*1))
5*(7*(10*1))
5/(7*(10*1))
5+(7/(10*1))
5-(7/(10*1))
5*(7/(10*1))
5/(7/(10*1))
5+(7+(10/1))
5-(7+(10/1))
5*(7+(10/1))
5/(7+(10/1))
5+(7-(10/1))
5-(7-(10/1))
5*(7-(10/1))
5/(7-(10/1))
5+(7*(10/1))
5-(7*(10/1))
5*(7*(10/1))
5/(7*(10/1))
5+(7/(10/1))
5-(7/(10/1))
5*(7/(10/1))
5/(7/(10/1))
5+((7+10)+1)
5-((7+10)+1)
5*((7+10)+1)
5/((7+10)+1)
5+((7+10)-1)
5-((7+10)-1)
5*((7+10)-1)
5/((7+10)-1)
5+((7+10)*1)
5-((7+10)*1)
5*((7+10)*1)
5/((7+10)*1)
5+((7+10)/1)
5-((7+10)/1)
5*((7+10)/1)
5/((7+10)/1)
(5+7)+(10+1)
(5+7)-(10+1)
(5+7)*(10+1)
(5+7)/(10+1)
(5+7)+(10-1)
(5+7)-(10-1)
(5+7)*(10-1)
(5+7)/(10-1)
(5+7)+(10*1)
(5+7)-(10*1)
(5+7)*(10*1)
(5+7)/(10*1)
(5+7)+(10/1)
(5+7)-(10/1)
(5+7)*(10/1)
(5+7)/(10/1)
(5+(7+10))+1
(5+(7+10))-1
(5+(7+10))*1
(5+(7+10))/1

从输出中我至少可以看到两个问题：

有些树没有到达，例如(((5 7) 10) 1)。
对于某棵树，有可能没有覆盖到所有的表达式。例如对于树 ((5 (7 10)) 1)，只有
```
(5+(7+10))+1
(5+(7+10))-1
(5+(7+10))*1
(5+(7+10))/1
```
已达到。

这是什么原因？谢谢。

Answer 1

您的递归调用如下所示：

left_subtrees = enumerate_trees(numbers[:i])
right_subtrees = enumerate_trees(numbers[i:])
for left in left_subtrees:
    for right in right_subtrees:
        #...

enumerate_trees returns 生成器对象，只能迭代一次。因此，right_subtrees 上的 for 循环只会在第一次工作，并且不会在外部 for 循环的下一次迭代中给出任何结果。

要解决这个问题，您可以将递归调用直接放在 for 语句中，以便每次都执行它们，或者您可以使用 list(enumerate_trees(...)) 将结果复制到列表中。

无法通过递归枚举所有的算术表达式

Cannot enumerate all arithmetic expressions by recursion

python

recursion

binary-tree

generator