Python - 如何将二叉树转换为保留相同信息的 N 叉树

Question

我有一个二叉树，代表一个解析后的逻辑公式。例如，f = a & b & -c | d 由前缀表示法的列表列表表示，其中第一个元素是运算符(一元或二元)，接下来的元素是它们的参数:

f = [ |, [&, a, [&, b, [-, c]]], d]

但是如果你(通过递归)翻译成经典的中缀符号，结果是一样的。

f = (((-c & b) & a) | d) = a & b & -c | d

我想做的是把它转换成保留相同信息的N叉树，也就是说，如果你再把它转换成公式，结果一定是一样的。像这样:

f = {l: [{&: [a,b,{-:[c]}]}, d]}

以下是中缀符号。

f = ((a & b & -c) | d) = a & b & -c | d

我还没有找到任何库，所以我尝试自己递归地做。然而，我只实现了这段在某些情况下失败的代码，而且它不是很优雅......

    def explore_tree(self,tree, last_symbol, new_tree):
        if type(tree) != list: # This true means that root is an atom
            new_tree[last_symbol].append(tree)
            return
        root = tree[0]
        if is_operator(root):
            if root != last_symbol:
                branch = {root: []}
                new_tree[last_symbol].append(branch)
                #This line is to search the index of branch object and expand by them
                self.explore_branches(tree, root, new_tree[last_symbol]
                                     [new_tree[last_symbol].index(branch)]) 
            else:
                self.explore_branches(tree,root,new_tree)

函数 explore_branches() 递归调用以从左和右探索树(如果存在)，如果给定字符串是一个逻辑运算符，则 is_operator() 返回 true ，例如 & 或 |。

关于如何执行此操作的任何其他想法？

提前致谢。

Answer 1

唯一敏感的情况是否定。除此之外，您可以简单地编写您的算法或类似的算法，例如

from functools import reduce
def op(tree):
    return 0 if type(tree)!=list else tree[0]

def bin_to_n(tree):
    if op(tree)==0:
        return tree
    op_tree = tree[0]
    out = [op_tree]
    for node in tree[1:]:
        flat_node = bin_to_n(node)
        if op(node) != op_tree:
            out.append(flat_node)
        else:
            out += flat_node[1:]
    return out

现在关于否定。上述算法的失败案例是在展平 -(-(1)) 时给出 -1 而不是 1

• 因此，一个非常基本的修复是

< if op(node) != op_tree
---
> if op(node) != op_tree or op(node)=="-"

意思是如果找到“减号”，您永远不会“连接”它。因此，这让 -(-(1)) 保持原样。

现在我们可以进一步简化，但这些简化可以事先在输入列表上完成。所以它“语义上”改变了树(即使评估保持相同)。

• 只处理双重否定:

op_tree = tree[0]
> if op_tree == '-' and op(tree[1]) == '-':
>    return bin_to_n2(tree[1][1])
out = [op_tree]

• 或者去 monkas 并在发现否定时实际应用德摩根定律

#really invert according to demorgan's law
def bin_to_n3(tree, negate=False):
    if op(tree)==0:
        return tree

    op_tree = tree[0]

    if negate:
        if op_tree == '-':
            #double neg, skip the node
            return bin_to_n3(tree[1])

        #demorgan
        out = [ '+' if op_tree == '*' else '*' ]
        for node in tree[1:]:
            flat_node = bin_to_n3(node, True)
            #notice that since we modify the operators we have 
            #to take the operator of the resulting tree
            if op(flat_node) != op_tree:
                out.append(flat_node)
            else:
                out += flat_node[1:]
        return out

    if op_tree == '-' and op(op_tree)==0:
        #do not touch the leaf
        return tree

    #same code as above, not pun to factorize it
    out = [op_tree]
    for node in tree[1:]:
        flat_node = bin_to_n3(node)
        if op(flat_node) != op_tree:
            out.append(flat_node)
        else:
            out += flat_node[1:]
    return out

---

下面进行一些随机检查以确保转换保持树的值完好无损

from functools import reduce
def op(tree):
    return 0 if type(tree)!=list else tree[0]

def bin_to_n(tree):
    if op(tree)==0:
        return tree
    op_tree = tree[0]
    out = [op_tree]
    for node in tree[1:]:
        flat_node = bin_to_n(node)
        if op(node) != op_tree or op(node)=='-':
            out.append(flat_node)
        else:
            out += flat_node[1:]
    return out

def bin_to_n2(tree):
    if op(tree)==0:
        return tree

    op_tree = tree[0]
    if op_tree == '-' and op(tree[1]) == '-':
        return bin_to_n2(tree[1][1])
    out = [op_tree]
    for node in tree[1:]:
        flat_node = bin_to_n2(node)
        if op(node) != op_tree:
            out.append(flat_node)
        else:
            out += flat_node[1:]
    return out

#really invert according to demorgan's law
def bin_to_n3(tree, negate=False):
    if op(tree)==0:
        return tree

    op_tree = tree[0]

    if negate:
        if op_tree == '-':
            #double neg, skip the node
            return bin_to_n3(tree[1])

        #demorgan
        out = [ '+' if op_tree == '*' else '*' ]
        for node in tree[1:]:
            flat_node = bin_to_n3(node, True)
            #notice that since we modify the operators we have 
            #to take the operator of the resulting tree
            if op(flat_node) != op_tree:
                out.append(flat_node)
            else:
                out += flat_node[1:]
        return out

    if op_tree == '-' and op(op_tree)==0:
        #do not touch the leaf
        return tree

    #same code as above, not pun to factorize it
    out = [op_tree]
    for node in tree[1:]:
        flat_node = bin_to_n3(node)
        if op(flat_node) != op_tree:
            out.append(flat_node)
        else:
            out += flat_node[1:]
    return out

def calc(tree):
    if op(tree) == 0:
        return tree
    s = 0
    subtree = tree[1:]
    if op(tree)=='+':
        s = reduce(lambda x,y: x or calc(y), subtree, False)
    elif op(tree) == '-':
        s = not calc(subtree[0])
    else:
        s = reduce(lambda x,y: x and calc(y), subtree, True)
    return s

#adaptated from https://stackoverflow.com/questions/6881170/is-there-a-way-to-autogenerate-valid-arithmetic-expressions
def brute_check():
    import random
    random.seed(3)
    def make_L(n=3):
        def expr(depth):
            if depth==1 or random.random()<1.0/(2**depth-1): 
                return random.choice([0,1])
            if random.random()<0.25:
                return ['-', expr(depth-1)]
            return [random.choice(['+','*']), expr(depth-1), expr(depth-1)]
        return expr(n)

    for i in range(100):
        L = make_L(n=10)
        a = calc(L)
        b = calc(bin_to_n(L))
        c = calc(bin_to_n2(L))
        d = calc(bin_to_n3(L))
        if a != b:
            print('discrepancy', L,bin_to_n(L),  a, b)

        if a != c:
            print('discrepancy', L,bin_to_n2(L),  a, c)

        if a != d:
            print('discrepancy', L,bin_to_n3(L),  a, d)
brute_check()