获取递归循环中嵌套数组的父元素

Question

我正在尝试遍历PDF书签并将它们保存在一个对象中，包括它们的父书签。

多亏了PyPDF4，我可以把书签作为数组中的数组。

例如:

[]
0: Root 1
1: []
0: Child layer 1.1
1: Child layer 1.2
2: []
0: Child layer 1.2.1
1: Child layer 1.2.2
1: Child layer 1.2.3
2: Root 2

由于这些数组因文件而异，我不知道这个数组是如何结构的。所以我最后选择了一个递归函数来保存它们。

def __iterate_through_bookmarks(outlines, bookmarks, layer = 0, parent = None):
layer += 1
print(layer)
if isinstance(outlines, list): 
for item in outlines:
__iterate_through_bookmarks(item, bookmarks, layer, parent)
return bookmarks

print(outlines.title)
bookmarks.append(bookmark(outlines, parent))

我做了一些实验，但我不能得到正确的。但是，看到函数中的层计数器如何正确地处理层给了我希望，这是可能的。

层输出:

1
2
Root 1
2
3
Child layer 1.1
3
Child layer 1.2
3
4
Child layer 1.2.1
4
Child layer 1.2.2
4
Child layer 1.2.3
2
Root 2

子层由于递归函数的工作方式，X有相同的层计数器。然而，我不能找到一个解决方案，如何保存他们的(相同的)父对象在一个对象。

最终目标是返回一个带有书签对象的数组。一个类，用于存储大纲的标题、位置和父类。

有人有什么建议吗?

Answer 1

带有显式'children'字段

递归浏览一个嵌套的字典列表，其中每个字典都有一个"名称";还有一个"孩子们"场。

nested_list = [
{'name': 'act IV',
'children': [{'name': 'scene 4',
'children': [{'name': 'dual seduction',
'children': []},
]}
]},
{'name': 'act I',
'children': [{'name': 'scene 2',
'children': [{'name': 'inconstancy praise',
'children': []},
{'name': 'sganarelle monologue',
'children': []}
]}
]},
]
def get_list_of_bookmarks(nested_list, parent_name=None):
bookmark_list = []
for bookmark in nested_list:
bookmark_list.append({'name': bookmark['name'], 'parent': parent_name})
bookmark_list.extend(get_list_of_bookmarks(bookmark['children'], parent_name=bookmark['name']))
return bookmark_list
print(get_list_of_bookmarks(nested_list))
# [{'name': 'act IV', 'parent': None},
#  {'name': 'scene 4', 'parent': 'act IV'},
#  {'name': 'dual seduction', 'parent': 'scene 4'},
#  {'name': 'act I', 'parent': None},
#  {'name': 'scene 2', 'parent': 'act I'},
#  {'name': 'inconstancy praise', 'parent': 'scene 2'},
#  {'name': 'sganarelle monologue', 'parent': 'scene 2'}]

或者，如果您想存储对父对象的引用，而不仅仅是父对象的名称:

def get_list_of_bookmarks(nested_list, parent=None):
bookmark_list = []
for bookmark_with_children in nested_list:
bookmark_with_parent = {'name': bookmark_with_children['name'], 'parent': parent}
bookmark_list.append(bookmark_with_parent)
bookmark_list.extend(get_list_of_bookmarks(bookmark_with_children['children'], parent=bookmark_with_parent))
return bookmark_list
print(get_list_of_bookmarks(nested_list))
# [{'name': 'act IV', 'parent': None},
# {'name': 'scene 4', 'parent': {'name': 'act IV', 'parent': None}},
# {'name': 'dual seduction', 'parent': {'name': 'scene 4', 'parent': {'name': 'act IV', 'parent': None}}},
# {'name': 'act I', 'parent': None},
# {'name': 'scene 2', 'parent': {'name': 'act I', 'parent': None}},
# {'name': 'inconstancy praise', 'parent': {'name': 'scene 2', 'parent': {'name': 'act I', 'parent': None}}},
# {'name': 'sganarelle monologue', 'parent': {'name': 'scene 2', 'parent': {'name': 'act I', 'parent': None}}}]

注意，print的输出看起来非常冗余并且充满副本，但事实并非如此。每个书签都包含对其父书签的引用;它不包含父节点的副本。

没有明确的'children'字段:顺序是相关的

现在假设你没有一个显式的'children'字段，你的嵌套列表只是一个列表的列表;子列表被认为是前一个元素的子列表。

nested_list = [
'act IV',
['scene 4', ['dual seduction']],
'act I',
['scene 2', ['inconstancy praise', 'sganarelle monologue']],
]

我们可以从相关问题中得到启发:将不规则的列表的列表拉平。

from collections.abc import Iterable
def flatten_with_depth(l, depth=0):
for el in l:
if isinstance(el, Iterable) and not isinstance(el, (str, bytes)):
yield from flatten_with_depth(el, depth=depth+1)
else:
yield (el, depth)
# flatten_with_depth() adapted from flatten() at https://stackoverflow.com/a/2158532/3080723
print(list(flatten_with_depth(nested_list)))
# [('act IV', 0), ('scene 4', 1), ('dual seduction', 2), ('act I', 0), ('scene 2', 1), ('inconstancy praise', 2), ('sganarelle monologue', 2)]

现在书签列表是扁平的，每个书签都有它的深度。深度depth的给定书签的父书签是深度depth-1的最近的前书签。一种容易找到父节点的有效方法是在当前分支中维护一个祖先节点的堆栈。

def get_parents_knowing_depths(list_with_depths):
ancestor_stack = []
result = []
for (bookmark_name, depth) in list_with_depths:
if depth == 0:
bookmark = {'name': bookmark_name, 'parent': None}
ancestor_stack = [bookmark]
else:
while len(ancestor_stack) > depth:
ancestor_stack.pop()
bookmark = {'name': bookmark_name, 'parent': ancestor_stack[-1]}
ancestor_stack.append(bookmark)
result.append(bookmark)
return result
print(get_parents_knowing_depths(flatten_with_depth(nested_list)))
# [{'name': 'act IV', 'parent': None},
#  {'name': 'scene 4', 'parent': {'name': 'act IV', 'parent': None}},
#  {'name': 'dual seduction', 'parent': {'name': 'scene 4', 'parent': {'name': 'act IV', 'parent': None}}},
#  {'name': 'act I', 'parent': None},
#  {'name': 'scene 2', 'parent': {'name': 'act I', 'parent': None}},
#  {'name': 'inconstancy praise', 'parent': {'name': 'scene 2', 'parent': {'name': 'act I', 'parent': None}}},
#  {'name': 'sganarelle monologue', 'parent': {'name': 'scene 2', 'parent': {'name': 'act I', 'parent': None}}}]