python - 如何从节点和叶子列表中创建一个新的 N 元 ExpressionTree 对象？

Question

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

我有一个名为 ExpressionTree 的类，它是一个 N 元表达式树，这样每个节点不仅限于只有两个子节点；它可以有超过 2 个，但不能少于 2 个。

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

所有叶子要么是单个字母字符串，要么是整数，所有父母都是“+”或“-”。

我正在尝试创建的方法称为 create_tree，它接受一个名为 lst 的列表，其类型为：List[List[Union[int, str]]]，并返回一个成功创建的由参数创建的 ExpressionTree : 第一。

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

树 1

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

树 2

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

标签： pythonlisttreeexpression-trees

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']]]]]