遍历嵌套的类字典结构，跟踪从根到叶的每条路径 (Python)

Question

我正在尝试遍历一个具有任意深度嵌套叶子的对象，获取每个根节点到叶子的路径。这方面的一个例子可能是：

class Field (object):
    def __init__(self, name, subfields=None):
        self.name = name
        self.subfields = subfields


f1 = Field("username")
f2 = Field("ip_address")
f3 = Field("song_id")
f11 = Field("song_length")
f10 = Field("misc_attrs", subfields=[f3, f11])

f4 = Field("event_time")
f5 = Field("song_name", subfields=[f1,f2])
f6 = Field("user_song_upload", subfields=[f10])

input_list = [f4,f5,f6]

我的目标是生成列表的列表 output，其中 output 中的每个列表代表从根节点到叶节点的路径。所以在上面的例子中，我们会有以下输出：

[["event_time"],["song_name","username"],["song_name","ip_address"],["user_song_upload","misc_attrs","song_id"],["user_song_upload","misc_attrs","song_length"]]

我有一个函数可以 return 所有叶节点，但我无法跟踪每个节点的完整路径。这是我目前所拥有的：

def get_leaf_paths(input_list, output = [], path=[]):
    for x in input_list:
        if not x.subfields:
            # we have a leaf
            path.append(x.name)
            output.append(path) 
            # next line clears the leaf from our last path
            path = path[:-1]

        else:
            # we don't have a leaf node, and need to iterate on the subfields
            path.append(x.name)
            get_leaf_paths(x.subfields, output, path)
    return output

然而，这会导致路径构建不正确（例如，两个相邻的顶级节点将在输出中出现在同一个内部列表中：

[['event_time'],
 ['song_name', 'username', 'user_song_upload', 'misc_attrs', 'song_id'],
 ['song_name', 'ip_address'],
 ['song_name', 'username', 'user_song_upload', 'misc_attrs', 'song_id'],
 ['song_name', 'username', 'user_song_upload', 'misc_attrs', 'song_length']]

Answer 1

您可以构造一个适当的基本案例来简化代码。尝试以下操作：

def get_leaf_paths(lst):
    if not lst: # empty list or None
        return [[]]
    return [[f.name, *path] for f in lst for path in get_leaf_paths(f.subfields)]

print(get_leaf_paths(input_list))

在代码中，基本情况是“空列表或 None”，即当 subfields 传递给函数但 subfields 实际上是 None.在叶节点调用函数时会出现这种情况。

输出：

[['event_time'], ['song_name', 'username'], ['song_name', 'ip_address'], ['user_song_upload', 'misc_attrs', 'song_id'], ['user_song_upload', 'misc_attrs', 'song_length']]

Answer 2

如果你需要将它应用到一个非常深的结构和递归（就像@j1-lee 在他们非常干净的实现中建议的那样）不是一个选项，这个工作：

def get_leaf_paths(lst):
    stack, l, i = [], lst, 0
    while l and len(l) > i:
        if l[i].subfields:
            stack.append((l, i))
            l, i = l[i].subfields, 0
        else:
            yield [x[n].name for x, n in stack] + [l[i].name]
            i += 1
        if i >= len(l):
            l, i = stack.pop()
            i += 1


print(list(get_leaf_paths(input_list)))

结果：

[['event_time'], ['song_name', 'username'], ['song_name', 'ip_address'], ['user_song_upload', 'misc_attrs', 'song_id'], ['user_song_upload', 'misc_attrs', 'song_length']]

遍历嵌套的类字典结构，跟踪从根到叶的每条路径 (Python)

Traversing a nested dict-like structure, keeping track of each path from root to leaf (Python)

python

object

recursion

path

traversal