python - 递归寻找表达深度

Question

我正在尝试使用递归来查找“表达式”的深度，即嵌套元组的层数:例如，

depth(('+', ('expt', 'x', 2), ('expt', 'y', 2))) => 2

depth(('/', ('expt', 'x', 5), ('expt', ('-', ('expt', 'x', 2), 1), ('/', 5, 2)))) => 4

基本上，我认为我需要检查(从外到内)每个元素是否是元组的实例，然后如果是，则递归调用深度函数。但我需要找到一种方法来确定哪一组递归调用具有最大深度，这就是我遇到的问题。这是我到目前为止所拥有的:

def depth3(expr):
    if not isinstance(expr, tuple):
        return 0
    else:
        for x in range(0, len(expr)):
            # But this doesn't take into account a search for max depth
            count += 1 + depth(expr[x])
    return count

想过解决这个问题的好方法吗？

Answer 1

你在正确的轨道上，但不是用 count += 1 + depth(expr[x]) 找到“总”深度
，使用max求最大值:

def depth(expr):
    if not isinstance(expr, tuple):
        return 0
    # this says: return the maximum depth of any sub-expression + 1
    return max(map(depth, expr)) + 1

print depth(("a", "b"))
# 1
print depth(('+', ('expt', 'x', 2), ('expt', 'y', 2)))
# 2
print depth(('/', ('expt', 'x', 5), ('expt', ('-', ('expt', 'x', 2), 1), ('/', 5, 2)))) 
# 4