6

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

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

对解决此问题的好方法的想法？

4

5 回答 5

13

您在正确的轨道上，但不是使用 找到“总”深度，而是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
于 2012-09-11T16:39:07.063 回答
0

仅伪代码（不保证编译，更不用说运行）：

深度（expr）：
  如果不是 isinstance(expr, tuple)：
    返回 0
  别的：
    米深度 = 0
    对于范围内的 x (0, len(expr))：
      d = 深度（expr[x]）
      如果 d > mdepth：
        mdepth = d
    返回 mdepth+1
于 2012-09-11T16:42:37.857 回答
0

在这里，试试这个——它是一个函数式编程解决方案，采用 Lisp、Haskell 等语言编程时使用的风格。

def depth(exp):
    if not exp:                         # the tuple is empty
        return 0                        #return 0
    elif not isinstance(exp[0], tuple): # first element is not a tuple
        return depth(exp[1:])           # traverse the rest of elements
    else:  # depth is 1 + depth of first tuple + depth of rest of elements
        return 1 + max(depth(exp[0]), depth(exp[1:]))
于 2012-09-11T17:00:26.893 回答
0

你可以试试这个

def depth(expr):
count = 0
if not isinstance(expr,tuple):
    return 0 
else:
    count = 1
    count1 = 0
    for e in expr:
        count1 = 1 + depth(e)
        count = max(count1,count)
return count
于 2014-07-20T13:19:15.197 回答
0

在遍历子表达式时，您可以简单地跟踪最后的最大深度。

def depth(expr):
    # base case
    if not isinstance(expr, tuple):
        return 0
    # if it is a tuple, we've at least depth of 1
    max_depth = 1
    # If any sub-expression is deeper, update max_depth
    for elem in expr:
        elem_depth = 1 + depth(elem)
        if elem_depth > max_depth:
            max_depth = elem_depth
    return max_depth
于 2016-07-24T23:17:35.560 回答