从列表定义创建 N-ary 表达式树

Question

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

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

class的私有变量是：_root即Optional[Union[str, int]]和_subtrees即List[ExpressionTree]。我已经成功地实现了 __eq__、is_empty、evaluate_tree、__str__ 和追加等基本方法，但我永远停留在一种方法上。

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

所有叶子要么是单字母串，要么是整数，所有parents要么是“+”要么是“-”。此外，所有叶子都是 ExpressionTrees，但 self._subtrees.

的列表为空

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

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

Tree 1

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

Tree 2

我知道 Queue 会很有用，但我不知道从哪里开始。我认为这段代码不一定需要递归，但如果正确实现它也可以使用它。

我不希望使用任何导入或创建新的 classes，List 除外。

我的doctest是这样的：

>>> lst = [['*'], [3, '*' , '*'], [5, 1], ['b', 'c']]
>>> express_tree = create_tree(lst)
>>> print(express_tree) == (3 * (5 * 1) * (b * c))
True
>>> express_tree._root == '*'
True
>>> express_tree._subtrees == [ExpressionTree(3, []), 
                               ExpressionTree('*', [ExpressionTree(5, []), 
                                                    ExpressionTree(1, [])]), 
                               ExpressionTree('*', [ExpressionTree('b', []), 
                                                    ExpressionTree('c', [])])]
True

在过去的 12 个小时里，我一直在努力正确地实现它，但我没有运气，我认为我的大脑没有正常工作。非常感谢对代码的任何帮助。请帮助这个可怜的家伙，这样我就可以摆脱这个 class 的噩梦，并从事更有趣的编码项目。提前致谢！

Answer 1

在递归函数中，可以通过将形成的级别传递给 ExpressionTree:

来构建树

class ExpressionTree:
   def __init__(self, _root, _subtrees):
      self._root, self._subtrees = _root, _subtrees
   def __repr__(self):
      return f'{self.__class__.__name__}({self._root}, {self._subtrees})'

def to_tree(d):
   k = [ExpressionTree(i, [] if i not in {'+', '*'} else d.pop(0)) for i in d.pop(0)]
   for i in range(len(k)):
      if k[i]._root in {'+', '*', '-'}: 
         d = [k[i]._subtrees, *d]
         if len(d) == 1:
            k[i]._subtrees = [ExpressionTree(i, []) for i in k[i]._subtrees]
         else:
            k[i]._subtrees = to_tree(d)
   return k


lst = [['*'], [3, '*' , '*'], [5, 1], ['b', 'c']]
lst1 = [['+'], ['+', '+'], ['1', '2'], ['3', '4']]
lst2 = [['+'], ['3', '+', '+'], ['5', '*'], ['b', 'c'], ['6', 'a']]
lst3 = [['+'], ['3', 'c', '+'], ['5', 'a']]
for i in [lst, lst1, lst2, lst3]:
   print(to_tree(i))
   print('-'*20)

输出：

[ExpressionTree(*, [ExpressionTree(3, []), ExpressionTree(*, [ExpressionTree(5, []), ExpressionTree(1, [])]), ExpressionTree(*, [ExpressionTree(b, []), ExpressionTree(c, [])])])]
--------------------
[ExpressionTree(+, [ExpressionTree(+, [ExpressionTree(1, []), ExpressionTree(2, [])]), ExpressionTree(+, [ExpressionTree(3, []), ExpressionTree(4, [])])])]
--------------------
[ExpressionTree(+, [ExpressionTree(3, []), ExpressionTree(+, [ExpressionTree(5, []), ExpressionTree(*, [ExpressionTree(6, []), ExpressionTree(a, [])])]), ExpressionTree(+, [ExpressionTree(b, []), ExpressionTree(c, [])])])]
--------------------
[ExpressionTree(+, [ExpressionTree(3, []), ExpressionTree(c, []), ExpressionTree(+, [ExpressionTree(5, []), ExpressionTree(a, [])])])]
--------------------

从列表定义创建 N-ary 表达式树

Creating N-ary Expression Tree from List definition

python

list

recursion

tree

expression-trees