如何完全遍历一个未知深度的复杂字典？

Question

从 JSON 导入可能会涉及到非常复杂和嵌套的结构。例如：

{u'body': [{u'declarations': [{u'id': {u'name': u'i',
                                       u'type': u'Identifier'},
                               u'init': {u'type': u'Literal', u'value': 2},
                               u'type': u'VariableDeclarator'}],
            u'kind': u'var',
            u'type': u'VariableDeclaration'},
           {u'declarations': [{u'id': {u'name': u'j',
                                       u'type': u'Identifier'},
                               u'init': {u'type': u'Literal', u'value': 4},
                               u'type': u'VariableDeclarator'}],
            u'kind': u'var',
            u'type': u'VariableDeclaration'},
           {u'declarations': [{u'id': {u'name': u'answer',
                                       u'type': u'Identifier'},
                               u'init': {u'left': {u'name': u'i',
                                                   u'type': u'Identifier'},
                                         u'operator': u'*',
                                         u'right': {u'name': u'j',
                                                    u'type': u'Identifier'},
                                         u'type': u'BinaryExpression'},
                               u'type': u'VariableDeclarator'}],
            u'kind': u'var',
            u'type': u'VariableDeclaration'}],
 u'type': u'Program'}

如何推荐遍历像上面这样的复杂结构？

除了一些列表外，大多数都是字典，结构甚至可以变得更加复杂，因此我需要一个通用的解决方案。

- Eduard Florinescu

Answer 1

您可以使用递归生成器将您的字典转换为平面列表。

def dict_generator(indict, pre=None):
    pre = pre[:] if pre else []
    if isinstance(indict, dict):
        for key, value in indict.items():
            if isinstance(value, dict):
                for d in dict_generator(value, pre + [key]):
                    yield d
            elif isinstance(value, list) or isinstance(value, tuple):
                for v in value:
                    for d in dict_generator(v, pre + [key]):
                        yield d
            else:
                yield pre + [key, value]
    else:
        yield pre + [indict]

它返回

[u'body', u'kind', u'var']
[u'init', u'declarations', u'body', u'type', u'Literal']
[u'init', u'declarations', u'body', u'value', 2]
[u'declarations', u'body', u'type', u'VariableDeclarator']
[u'id', u'declarations', u'body', u'type', u'Identifier']
[u'id', u'declarations', u'body', u'name', u'i']
[u'body', u'type', u'VariableDeclaration']
[u'body', u'kind', u'var']
[u'init', u'declarations', u'body', u'type', u'Literal']
[u'init', u'declarations', u'body', u'value', 4]
[u'declarations', u'body', u'type', u'VariableDeclarator']
[u'id', u'declarations', u'body', u'type', u'Identifier']
[u'id', u'declarations', u'body', u'name', u'j']
[u'body', u'type', u'VariableDeclaration']
[u'body', u'kind', u'var']
[u'init', u'declarations', u'body', u'operator', u'*']
[u'right', u'init', u'declarations', u'body', u'type', u'Identifier']
[u'right', u'init', u'declarations', u'body', u'name', u'j']
[u'init', u'declarations', u'body', u'type', u'BinaryExpression']
[u'left', u'init', u'declarations', u'body', u'type', u'Identifier']
[u'left', u'init', u'declarations', u'body', u'name', u'i']
[u'declarations', u'body', u'type', u'VariableDeclarator']
[u'id', u'declarations', u'body', u'type', u'Identifier']
[u'id', u'declarations', u'body', u'name', u'answer']
[u'body', u'type', u'VariableDeclaration']
[u'type', u'Program']

- Valentin Briukhanov

---

在我阅读的所有解决方案中，这是最简单且运行良好的 :-) 谢谢Bryukhanov Valentin。 - Md. Mohsin

我还想在列表/元组子项的情况下获得索引。我通过添加enumerate并执行以下操作来实现：for i, v in enumerate(value): for d in dict_generator(v, pre + [key + f'[{i}]']): - Thomas Fauskanger

完整的代码可以在此链接中找到：https://hastebin.com/agiguhovuj.cs（这是Python代码，不是C#）。 - Thomas Fauskanger

它运行得很好。它生成了树中所有路径的完整列表，每个路径都在一个列表中。mypaths = [*dict_generator(myjson)]对于mypaths中的每个路径： print(path) - Golden Lion

如果我想在删除键或项目后重新组合它们，该怎么办？ - Nathanael Steinhauer

Answer 2

如果你只需要遍历字典，我建议使用一个递归的 walk 函数，该函数接受一个字典作为参数，并通过其元素进行递归遍历。类似于这样：

def walk(node):
    for key, item in node.items():
        if item is a collection:
            walk(item)
        else:
            It is a leaf, do your thing

如果您还想搜索元素，或查询通过特定条件的多个元素，请查看jsonpath模块。

- Hans Then

---

这仅适用于直接嵌套的字典。在示例数据结构中，有几个字典值是其他字典的列表。需要一些额外的逻辑来处理这些情况（例如在列表理解或生成器表达式中进行递归）。为了使事情正常工作，您可能需要利用对数据含义的了解，例如所有字典都具有“type”键。 - Blckknght

你还应该小心检查循环。例如：foo = {}; foo['bar'] = foo 会让你的程序崩溃。你的遍历函数应该保持一个已经遍历过的对象列表，并且不要重复遍历。你可以将这个列表传递给每个后续调用。 - Cory

如果该项是一个集合，则会抛出错误。你的导入语句是什么？ - Golden Lion

Answer 3

与其编写自己的解析器，根据任务的不同，你可以扩展标准库 json 模块中的编码器和解码器。

我特别建议如果您需要将属于自定义类的对象编码为json，则使用此方法。如果您必须执行一些也可以在json的字符串表示形式上完成的操作，请考虑迭代 JSONEncoder().iterencode

对于两者，参考文献是http://docs.python.org/2/library/json.html#encoders-and-decoders

- danza

Answer 4

如果你了解数据的含义，你可能想创建一个parse函数，将嵌套的容器转换为自定义类型的对象树。然后，您可以使用这些自定义对象的方法来处理数据。

对于您的示例数据结构，您可以创建Program、VariableDeclaration、VariableDeclarator、Identifier、Literal和BinaryExpression类，然后使用类似以下的解析器：

def parse(d):
    t = d[u"type"]

    if t == u"Program":
        body = [parse(block) for block in d[u"body"]]
        return Program(body)

    else if t == u"VariableDeclaration":
        kind = d[u"kind"]
        declarations = [parse(declaration) for declaration in d[u"declarations"]]
        return VariableDeclaration(kind, declarations)

    else if t == u"VariableDeclarator":
        id = parse(d[u"id"])
        init = parse(d[u"init"])
        return VariableDeclarator(id, init)

    else if t == u"Identifier":
        return Identifier(d[u"name"])

    else if t == u"Literal":
        return Literal(d[u"value"])

    else if t == u"BinaryExpression":
        operator = d[u"operator"]
        left = parse(d[u"left"])
        right = parse(d[u"right"])
        return BinaryExpression(operator, left, right)

    else:
        raise ValueError("Invalid data structure.")

- Blckknght

Answer 5

也许可以帮助您：

def walk(d):
    global path
      for k,v in d.items():
          if isinstance(v, str) or isinstance(v, int) or isinstance(v, float):
            path.append(k)
            print "{}={}".format(".".join(path), v)
            path.pop()
          elif v is None:
            path.append(k)
            ## do something special
            path.pop()
          elif isinstance(v, dict):
            path.append(k)
            walk(v)
            path.pop()
          else:
            print "###Type {} not recognized: {}.{}={}".format(type(v), ".".join(path),k, v)

mydict = {'Other': {'Stuff': {'Here': {'Key': 'Value'}}}, 'root1': {'address': {'country': 'Brazil', 'city': 'Sao', 'x': 'Pinheiros'}, 'surname': 'Fabiano', 'name': 'Silos', 'height': 1.9}, 'root2': {'address': {'country': 'Brazil', 'detail': {'neighbourhood': 'Central'}, 'city': 'Recife'}, 'surname': 'My', 'name': 'Friend', 'height': 1.78}}

path = []
walk(mydict)

会产生如下输出：

Other.Stuff.Here.Key=Value 
root1.height=1.9 
root1.surname=Fabiano 
root1.name=Silos 
root1.address.country=Brazil 
root1.address.x=Pinheiros 
root1.address.city=Sao 
root2.height=1.78 
root2.surname=My 
root2.name=Friend 
root2.address.country=Brazil 
root2.address.detail.neighbourhood=Central 
root2.address.city=Recife 

- Fabiano Silos

Answer 6

要遍历/映射整个JSON结构，您可以使用以下代码：

def walk(node, key):
    if type(node) is dict:
        return {k: walk(v, k) for k, v in node.items()}
    elif type(node) is list:
        return [walk(x, key) for x in node]
    else:
        return YourFunction(node, key)

def YourFunction(node, key):
    if key == "yourTargetField":   # for example, you want to modify yourTargetField
        return "Modified Value"
    return node # return existing value

这将通过整个JSON结构，并运行每个叶子节点（端点键值对）通过您的函数。Yourfunction返回修改后的值。 整个walk函数将给您一个新的，处理过的对象，按顺序。

- Marcel Bostelaar

Answer 7

如果被接受的答案对您有效，但您还想要完整有序路径，并包括嵌套数组的数字索引，则此轻微变化将起作用：

def dict_generator(indict, pre=None):
    pre = pre[:] if pre else []
    if isinstance(indict, dict):
        for key, value in indict.items():
            if isinstance(value, dict):
                for d in dict_generator(value,  pre + [key]):
                    yield d
            elif isinstance(value, list) or isinstance(value, tuple):
                for k,v in enumerate(value):
                    for d in dict_generator(v, pre + [key] + [k]):
                        yield d
            else:
                yield pre + [key, value]
    else:
        yield indict

- Brideau

Answer 8

我更灵活的版本如下：

def walktree(tree, at=lambda node: not isinstance(node, dict), prefix=(), 
                flattennode=lambda node:isinstance(node, (list, tuple, set))):
    """
    Traverse a tree, and return a iterator of the paths from the root nodes to the leaf nodes.
    tree: like '{'a':{'b':1,'c':2}}'
    at: a bool function or a int indicates levels num to go down. walktree(tree, at=1) equivalent to tree.items()
    flattennode: a bool function to decide whether to iterate at node value
    """
    if isinstance(at, int):
        isleaf_ = at == 0
        isleaf = lambda v: isleaf_
        at = at - 1
    else:
        isleaf = at
    if isleaf(tree):
        if not flattennode(tree):
            yield (*prefix, tree)
        else:
            for v in tree:
                yield from walktree(v, at, prefix, flattennode=flattennode)
    else:
        for k,v in tree.items():
            yield from walktree(v, at, (*prefix, k), flattennode=flattennode)

用法：

> list(walktree({'a':{'b':[0,1],'c':2}, 'd':3}))
[('a', 'b', 0), ('a', 'b', 1), ('a', 'c', 2), ('d', 3)]
> list(walktree({'a':{'b':[0,1],'c':2}, 'd':3}, flattennode=lambda e:False))
[('a', 'b', [0, 1]), ('a', 'c', 2), ('d', 3)]
> list(walktree({'a':{'b':[0,1],'c':2}, 'd':3}, at=1))
[('a', {'b': [0, 1], 'c': 2}), ('d', 3)]
> list(walktree({'a':{'b':[0,{1:9,9:1}],'c':2}, 'd':3}))
[('a', 'b', 0), ('a', 'b', 1, 9), ('a', 'b', 9, 1), ('a', 'c', 2), ('d', 3)]
> list(walktree([1,2,3,[4,5]]))
[(1,), (2,), (3,), (4,), (5,)]

- guoyongzhi

---

请考虑避免发布包含大量代码的长回答。 - Khaled

@Khaled 代码大小，就我而言，代码对所需的功能来说看起来是最小化的。 - Eduard Florinescu

这需要一篇博客文章来完整地解释。我实际上很喜欢这个。 - Christopher Rucinski

Answer 9

这是一个稍微改进的已接受解决方案。如果你正在使用Python3（我希望你是），你可以使用在Python 3.3中引入的yield from语法。此外，isinstance作为第二个参数可以接受元组：

def dict_generator(adict, pre=None):
    pre = pre[:] if pre else []
    if isinstance(adict, dict):
        for key, value in adict.items():
            if isinstance(value, dict):
                yield from dict_generator(value, pre + [key])
            elif isinstance(value, (list, tuple)):
                for v in value:
                    yield from dict_generator(v, pre + [key])
            else:
                yield pre + [key, value]
    else:
        yield pre + [adict]

迭代版本（如果您使用生成器，非常相似）：

def flatten(adict):
    stack = [[adict, []]]
    while stack:
        d, pre = stack.pop()
        if isinstance(d, dict):
            for key, value in d.items():
                if isinstance(value, dict):
                    stack.append([value, pre + [key]])
                elif isinstance(value, (list, tuple)):
                    for v in value:
                        stack.append([v, pre + [key]])
                else:
                    print(pre + [key, value])
        else:
            print(pre + [d])

- funnydman

Answer 10

对于上面的解决方案（处理包含列表的json），有一些补充。

#!/usr/bin/env python

import json

def walk(d):
   global path
   for k,v in d.items():
      if isinstance(v, str) or isinstance(v, int) or isinstance(v, float):
         path.append(k)
         print("{}={}".format(".".join(path), v)) 
         path.pop()
      elif v is None:
         path.append(k)
         # do something special
         path.pop()
      elif isinstance(v, list):
         path.append(k)
         for v_int in v:
            walk(v_int)
         path.pop()
      elif isinstance(v, dict):
         path.append(k)
         walk(v)
         path.pop()
      else:
         print("###Type {} not recognized: {}.{}={}".format(type(v), ".".join(path),k, v))

with open('abc.json') as f:
   myjson = json.load(f)

path = []
walk(myjson)

- BurAk