Creating N-ary Expression Tree from List definition

Question

Code newbie here, and I am creating a project in Python.

I have a class called ExpressionTree which is, an N-ary expression tree, such that each node is not merely restricted to having only two children; it can have more than 2, but not less than 2.

The class's private variables are: _root which is Optional[Union[str, int]] and _subtrees which is List[ExpressionTree]. I have successfully implemented basic methods such as __eq__, is_empty, evaluate_tree, __str__, and append, but I am stuck permanently on one single method.

The only operators I would use in this tree are "+" and "-" (but the code should work for any operator).

All leaves are either a single letter string, or an integer, and all parents are either "+" or "-". Also, all leaves are ExpressionTrees but with an empty list for self._subtrees.

The method I am trying to create is called create_tree, which takes in a list called lst, for which the type is: List[List[Union[int, str]]], and returns a successfully created ExpressionTree that was made from the parameter: lst.

Each list in lst represents a level, but for each operator in the list, the next lists are the children of each operator. For example, if lst = [[+], [+, +], [1, 2], [3, 4]], then the Tree should look something like:

Tree 1

On a more nested example, if I were to run create_tree([[+], [3, +, +], [5, *], [b, c], [6, a]]), the Tree I should be getting is:

Tree 2

I know that a Queue would be very useful, but I do not know where to start. I don't think this code necessarily would need recursion, but it could work with it as well if implemented correctly.

I wish not to use any imports or create new classes, except List.

The doctest I have are something like this:

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

I have spent the past 12 hours trying to correctly implement this, and I have had no luck, and I think my brain is not working properly. Any help with the code is immensely appreciated. Please help this poor fellow so I can get out of this nightmare of a class and work on more enjoyable coding projects. Thanks in advance!

Answer 1

In the recursive function, the tree can be built by passing the formed levels to 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)

Output:

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