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

Question

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

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

该类的私有变量是：_rootwhich isOptional[Union[str, int]]和_subtreeswhich is List[ExpressionTree]。我已经成功地实现了基本的方法，例如 __eq__、is_empty、evaluate_tree、__str__ 和 append，但我一直停留在一个方法上。

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

所有叶子要么是单个字母字符串，要么是整数，所有父母都是“+”或“-”。此外，所有叶子都是 ExpressionTrees，但 self._subtrees 的列表为空。

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

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

树 1

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

树 2

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

我不希望使用任何导入或创建新类，除了 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 个小时里，我一直在尝试正确地实现这一点，但我没有运气，我认为我的大脑工作不正常。非常感谢您对代码的任何帮助。请帮助这个可怜的家伙，这样我就可以摆脱课堂的噩梦，从事更有趣的编码项目。提前致谢！

标签： pythonlistrecursiontreeexpression-trees

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, [])])])]
--------------------