如何从节点和叶子列表创建新的 N-ary ExpressionTree object？

Question

这里是代码新手，我正在 Python 中创建一个项目。

我有一个叫做 ExpressionTree 的 class，它是一个 N-ary 表达式树，这样每个节点不仅限于只有两个 children；可以多于2个，但不能少于2个

我会在此树中使用的唯一运算符是“+”和“-”（但代码应该适用于任何运算符）。

所有叶子要么是单字母串，要么是整数，所有parents要么是“+”要么是“-”。

我尝试创建的方法称为 create_tree，它接收一个名为 lst 的列表，其类型为：List[List[Union[int, str]]]，以及 returns 成功创建的 ExpressionTree 由参数制成：lst.

lst中的每个列表代表一个级别，但对于列表中的每个运算符，接下来的列表是每个运算符的children。例如，如果 lst = [[+], [+, +], [1, 2], [3, 4]]，那么树应该类似于：

Tree 1

在一个更嵌套的例子中，如果我要运行 create_class([[+], [3, +, +], [5, *], [b, c], [6, a]])，我应该得到的树是：

Tree 2

我知道队列会很有用，但我不知道从哪里开始。我认为这段代码不一定需要递归，但如果实现正确，它也可以使用递归。非常感谢对代码的任何帮助。提前致谢！

Answer 1

您可以递归地对列表进行分区以构建树：

from collections import deque
def to_tree(d):
   k = [[i, [] if i not in {'+', '*'} else d.popleft()] for i in d.popleft()]
   for i in range(len(k)):
     if k[i][0] in {'+', '*'}: 
        d = deque([k[i][-1], *d])
        k[i][-1] = k[i][-1] if len(d) == 1 else to_tree(d)
   return [[a, b] if b else a for a, b in k]
   

lst = [['+'], ['+', '+'], ['1', '2'], ['3', '4']]
lst1 = [['+'], ['3', '+', '+'], ['5', '*'], ['b', 'c'], ['6', 'a']]
lst2 = [['+'], ['3', 'c', '+'], ['5', 'a']]
print(to_tree(deque(lst)))
print(to_tree(deque(lst1)))
print(to_tree(deque(lst2)))

输出：

[['+', [['+', ['1', '2']], ['+', ['3', '4']]]]]
[['+', ['3', ['+', ['5', ['*', ['6', 'a']]]], ['+', ['b', 'c']]]]]
[['+', ['3', 'c', ['+', ['5', 'a']]]]]

如何从节点和叶子列表创建新的 N-ary ExpressionTree object？

How to create a new N-ary ExpressionTree object from a list of nodes and leaves?

python

list

tree

expression-trees