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

ここで、これを試してみてください。これは、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

疑似コードのみ (コンパイルは保証されておらず、実行されることはほとんどありません):

dep の深さ (expr):
  isinstance(expr, tuple) でない場合:
    0 を返す
  そうしないと：
    深さ = 0
    範囲内の x の場合 (0, len(expr)):
      d = 深さ (expr[x])
      d > mdepth の場合:
        深さ = d
    mdepth+1 を返す
于 2012-09-11T16:42:37.857 に答える