1

新程序员在这里。原谅任何偶尔的白痴。

我正在尝试编写一个小函数来返回（任意大）嵌套列表中最深的列表。子列表包含元组和字符串。

例子：

L = ['o', ([], [(1, 'V'), (-1, 'C')]), ['o', ['o', (['prefers'], [(1, 'D'), (1, 'D'), (-1, 'V')]), ['o', (['the'], [(1, 'N'), (-1, 'D')]), (['beer'], [(-1, 'N')])]], ['o', (['the'], [(1, 'N'), (-1, 'D')]), (['king'], [(-1, 'N')])]]]

我意识到这非常难以解析。这就是嗯，为什么我要机器来做。

（如果你想知道，我是一名语言学家，这个列表定义了一个极简语法中句子的派生树。）我想要的是返回嵌入最深的列表，在这种情况下是 ['o', (['the'], [(1, 'N'), (-1, 'D')]), (['beer'], [(-1, 'N')])]]。这是我尝试过的（除其他外）：

def get_deepest(L):
    is_list = True
    while is_list == True:
        for e in L:
            is_list = any(isinstance(e,list) for e in L)
            get_deepest(e)
        return e

这达到了递归限制。任何指针？这几天我一直在为此苦苦挣扎。

谢谢。

4

3 回答 3

1

通过自己使用堆栈来模仿递归堆栈。

tovisit = [ L ]
current_deepest = None
while tovisit != []:
     v = tovisit.pop()
     for e in v:
         tovisit.append(e)

您需要在此处添加自己的逻辑（您当前的函数是错误的，您在退出 for 循环时返回 e）。

于 2013-06-14T19:34:29.900 回答
0

这是我的解决方案。你的get_deepest()电话没有返回任何东西，所以有一个逻辑错误，而且它继续深入。

Lst = ['o', ([], [(1, 'V'), (-1, 'C')]), ['o', ['o', (['prefers'], [(1, 'D'), (1, 'D'), (-1, 'V')]), ['o', (['the'], [(1, 'N'), (-1, 'D')]), (['beer'], [(-1, 'N')])]], ['o', (['the'], [(1, 'N'), (-1, 'D')]), (['king'], [(-1, 'N')])]]]

def get_dpst(L, maxdepth):
    deepest_tup = (L, maxdepth)
    for e in L:
        is_list = any(isinstance(e,list) for e in L)
        if is_list:
            tup = get_dpst(e, maxdepth+1)
            if tup[1] > deepest_tup[1]:
                deepest_tup = tup
    return deepest_tup

def get_deepest(L):
    tup = get_dpst(L, 0)
    return tup[0]

def printlist(lst):
    print '[%s]' % ', '.join(map(str, lst))

printlist(get_deepest(Lst))

或者在函数中定义一个函数。

Lst = ['o', ([], [(1, 'V'), (-1, 'C')]), ['o', ['o', (['prefers'], [(1, 'D'), (1, 'D'), (-1, 'V')]), ['o', (['the'], [(1, 'N'), (-1, 'D')]), (['beer'], [(-1, 'N')])]], ['o', (['the'], [(1, 'N'), (-1, 'D')]), (['king'], [(-1, 'N')])]]]

def get_deepest(L):
    def get_dpst(L, maxdepth):
        deepest_tup = (L, maxdepth)
        for e in L:
            is_list = any(isinstance(e,list) for e in L)
            if is_list:
                tup = get_dpst(e, maxdepth+1)
                if tup[1] > deepest_tup[1]:
                    deepest_tup = tup
        return deepest_tup
    tup = get_dpst(L, 0)
    return tup[0]

def printlist(lst):
    print '[%s]' % ', '.join(map(str, lst))

printlist(get_deepest(Lst))
于 2013-06-14T19:33:36.910 回答
0 
L = ['o', ([], [(1, 'V'), (-1, 'C')]), ['o', ['o', (['prefers'], [(1, 'D'), (1, 'D'), (-1, 'V')]), ['o', (['the'], [(1, 'N'), (-1, 'D')]), (['beer'], [(-1, 'N')])]], ['o', (['the'], [(1, 'N'), (-1, 'D')]), (['king'], [(-1, 'N')])]]] 
max_depth = -1
deepest_list = None
def get_deepest(L,depth=0):
    global max_depth, deepest_list
    if depth > max_depth:
        max_depth = depth
        deepest_list = L
    for x in L:
        if isinstance(x,list):
            get_deepest(x,depth+1)
get_deepest(L)
print deepest_list

这段代码是一起破解的，肯定有一种方法可以在没有全局变量的情况下完成。顺便说一句，我认为对于中等规模的问题，递归是可以的。

于 2013-06-15T03:21:30.593 回答