访问n叉树的x层来操作节点并通过递归添加子节点

Question

我有一个问题正在尝试解决，我可以接受各种不同长度和复杂度的表达式，并将它们作为节点插入到 n 元（或非二元）树中。

我需要确定要查找的位置或要查找的内容以开始递归。

表达式可以变化为：

invalid_expr = ["(", "SOME", "&", "THING", ")", "|", "INVALID", "&", "(", "GOES", "|", "IN", "|", "HERE", ")"]
simple_expr = ["VERY", "&", "SIMPLE", "&", "EXPRESSION", "&", "(", "NO", "|", "BIG", "|", "DEAL", ")"]
complicated_expr = ["(", "MORE", "&", "(", "COMPLICATED", "|","(","EXPRESSION","&","PRESENTING",")","|", "MANY", ")", ")", "|", "(", "DEEPER", "&", "(", "LEVELS", "|", "FOR", "|", "TREE", ")",")"]

树类比较简单：

class NonBinTree:

    def __init__(self, val):
        self.val = val
        self.nodes = []

    def add_node(self, val):
        self.nodes.append(NonBinTree(val))
    
    def add_child_node(self, parent, val):
        self.nodes[parent].add_node(val)

    def make_parent_node(self, parent, val):
        self.nodes[parent] = NonBinTree(val)

    
    def __repr__(self):
        return f"NonBinTree({self.val}): {self.nodes}"

代码的功能是首先获取一个表达式，将括号内的项目计数为整个列表，该列表进入节点，而括号外的项目作为单个字符串节点。作为公共运算符的运算符将是父节点，非运算符字符串或列表将是子节点。该逻辑必须更深地遍历每一层以访问每个子项、评估字符串、用公共运算符替换字符串父项并添加字符串子项和列出子项。 执行此操作的算法是：

pre_inserted_nodes, operator = create_nodes(an_expr)
a = NonBinTree(list(operator)[0])
for i in pre_inserted_nodes:
    if i != list(operator)[0]:
        a.add_node(i)
i=0
while i < len(pre_inserted_nodes):
    if isinstance(pre_inserted_nodes[i], list):
        pre_inserted_nodes[i].pop(0)
        pre_inserted_nodes[i].pop()
        new_pre_inserted_nodes, new_operator = create_nodes(pre_inserted_nodes[i])
        temp_new_pre_inserted_nodes = copy.deepcopy(new_pre_inserted_nodes)
        for node_index in range(len(temp_new_pre_inserted_nodes)):
            if not isinstance(temp_new_pre_inserted_nodes[node_index], list):
                if temp_new_pre_inserted_nodes[node_index] == list(new_operator)[0]:
                    new_pre_inserted_nodes.pop(node_index)
        a.make_parent_node(i, list(new_operator)[0])
        for node in new_pre_inserted_nodes:
            a.add_child_node(i, node)
    i += 1

树可能变得非常复杂，在某些情况下（例如在complexed_expr中）它可能有5个需要访问的级别。 例如。：

NonBinTree(|): [(&): [(More): [], (|): [(Complicated): [], (&): [(Expressions): [], (Presenting): []], (More): []]], (&): [(Deeper): [], (|): [(Levels): [], (For): [], (Tree): []]]]

所以它可以从

a.node[0]

到

a.node[0].node[0].node[1].node[1].add_node(element)

变化。

我正在努力如何处理从单个节点级别到 4 个节点级别的表达式。

我想 TLDR 是，如何在现有的

.node[x]

 字符串中添加额外的 

.node[0].node[y].node[z]

Answer 1

您可以为此使用递归函数。当遇到左括号时，进行递归调用，当遇到右括号（或输入结束）时，从调用中返回。

我会将您的课程简化为仅最基本的内容。

这是一个可能的实现：

class Node:
    def __init__(self, val, nodes=None):
        self.val = val
        self.nodes = nodes or []

    def __repr__(self):
        return f"Node({self.val}): {self.nodes}"

def expr_to_tree(expr):
    it = iter(expr)

    def q(s):
        return "end-of-input" if s is None else f"'{s}'"
    
    def get_operand():
        operand = next(it, None)
        if operand == "(":
            return get_expr(")")
        if operand in (")", "&", "|", None):
            raise ValueError(f"Expected an operand, but got {q(operand)}")
        return Node(operand)

    def get_expr(terminal):
        node = get_operand()
        operator = next(it, None)
        if operator in ("&", "|"):
            node = Node(operator, [node])
            while operator == node.val:
                node.nodes.append(get_operand())
                operator = next(it, None)
        if operator != terminal:
            raise ValueError(f"Expected {q(node.val)}, or {q(terminal)}, but got {q(operator)}")
        return node

    return get_expr(None)

调用示例：

print(expr_to_tree(complicated_expr))

这将输出：

Node(|): [Node(&): [Node(MORE): [], Node(|): [Node(COMPLICATED): [], Node(&): [Node(EXPRESSION): [], Node(PRESENTING): []], Node(MANY): []]], Node(&): [Node(DEEPER): [], Node(|): [Node(LEVELS): [], Node(FOR): [], Node(TREE): []]]]