在递归循环中获取嵌套数组的父级

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

由于递归函数的工作方式，子层1.x具有相同的层计数器。但是，我找不到一个解决方案来解决如何在对象中保存它们的（相同的）父对象

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

有人有什么建议吗

Answer 1

带有显式的“children”字段

递归浏览嵌套的dict列表，其中每个dict都有一个“name”和一个“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']],
]

我们可以从相关问题中得到启发：Flatten an irregular list of lists

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}}}]