在 Python 中确定嵌套元组的嵌套级别的简单方法

Question

有没有一种简单的方法来确定t（表示重组二叉树）的嵌套级别（不依赖于Python的递归限制）？

t = (4, (3, 5, (2, 4, 6, (1, 3, 5, 7))))

请注意，如果没有 t 深度的先验知识，例程可能会面临递归限制，该限制由 sys.setrecursionlimit(n) 设置并由 sys.getrecursionlimit() 查看。尽管如此，事先将递归限制设置得非常高可能还不够，从而产生错误

`RecursionError: maximum recursion depth exceeded while calling a Python object`.

以下生成更大（更深）的t：

t = tuple(tuple(range(k)) for k in range(1,200))`

我猜这些可能有用（还没有弄清楚细节）：

可以将 t 转换为字符串并计算左括号的数量
如果展平元组的大小为$N$，则深度为$n(n+1)/2=N$的正二次根的大小，即$n=(-1+\sqrt( 1+8N))/2$
反复剥离（并计数）外容器直到最深的嵌套
还有其他的吗？

P.S。任何想法为什么在线 TeX 没有在我的问题中呈现？测试：$N$

Answer 1

您可以将递归函数转换为您自己管理的堆栈，例如

t = (4, (3, 5, (2, 4, 6, (1, 3, 5, 7))))

def depth(t):
    max_depth = 0
    A = [(t,max_depth)]
    while A:
        x,depth = A.pop()
        if isinstance(x, (list, tuple)):
            for a in x:
                A.append((a,depth+1))
        else:
            max_depth = max(max_depth,depth)
    return max_depth

print depth(1)  # Prints 0
print depth((1,1)) # Prints 1
print depth(t) # Prints 4

这不是递归函数，因此不会达到递归限制。

Answer 2

您最初的问题谈到递归限制是一个问题，但您的示例与此相去甚远。我建议您采用最 Pythonic 的方法，并且只在递归限制开始成为问题时才担心它们。该问题的递归方法是找到每个元素的深度，并取最大值。

def depth(t):
    try:
        return 1+max(map(depth,t))
    except:
        return 0

t = (4, (3, 5, (2, 4, 6, (1, 3, 5, 7))))
print(depth(t)) # 4
t = tuple(tuple(range(k)) for k in range(1,200))
print(depth(t)) # 2

这会将字符串视为另一个嵌套级别，这可能不是您想要的，但可能无关紧要。

在 Python 中确定嵌套元组的嵌套级别的简单方法

Easy way to determine a nesting level of nested tuples, in Python

python

algorithm

recursion

nested

python-3.x