python - Python中的元组树结构深度

Question

我想做一个递归函数，用来测量a的深度 Python 2 中的元组树结构。这是麻省理工学院 AI 类(class)中的练习，我不参加该类(class)。

我从左边开始，向树的叶子添加一个零。如果不是一片叶子，我就顺着树往下走，直到找到一片叶子。我最大化 child 并将结果返回给 parent 。递归会给我最终结果。

#input
ls0 = 'x'
ls1 = ('expt', 'x', 2)
ls2 = ('+', ('expt', 'x', 2), ('expt', 'y', 2))
ls4 = ('/', ('expt', 'x', 5), ('expt', ('-', ('expt', 'x', 2),1), ('/', 5, 2)))

#expected output
print(depth(ls4)) #expected output 4
print(depth(ls2)) #expected output 2
print(depth(ls1)) #expected output 1

#function definition
def depth(expr):
    a = []
    for j in range(len(expr)):
        if isinstance(expr,(list,tuple)) == 0:
            a.append(0)
            if len(a) == len(expr):
                return max(a)
        else:
            a.append(1 + depth(expr[j]))

Answer 1

在递归函数中，使用计数器来跟踪当前深度:

ls0 = 'x'
ls1 = ('expt', 'x', 2)
ls2 = ('+', ('expt', 'x', 2), ('expt', 'y', 2))
ls4 = ('/', ('expt', 'x', 5), ('expt', ('-', ('expt', 'x', 2),1), ('/', 5, 2)))
tree = [ls1, ls2, ls4]
def depth(b, count=0):
   if isinstance(b, str) or isinstance(b, int) or all(not isinstance(i, tuple) for i in b):
     yield count+1
   else:
     for i in b:
       for c in depth(i, count+1):
         yield c

final_results = [max(i) for i in list(map(list, list(map(depth, tree))))]

输出:

[1, 2, 4]