我有一个二叉树，它表示一个已解析的逻辑公式。例如，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 ，例如 & 或 |。
关于如何做到这一点还有其他想法吗？
提前谢谢您。
最佳答案
唯一敏感的情况是否定。 除此之外，您可以简单地编写您的算法或类似的代码，例如
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]
- 或者去僧侣并在发现否定时实际应用德摩根定律
#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()
关于Python - 如何将二叉树转换为 N 叉树并保持相同的信息，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/58883506/