python - 将字典列表转换为层次结构

Question

我发现自己需要一些帮助，我正在尝试将字典列表(你会看到)转换为某种树/等级结构。我所要做的就是列表的当前顺序的深度参数(这是正确的)。

functions = [
  {'depth': 0, 'line': 3, 'type': 'class', 'name': 'General(object)'},
  {'depth': 1, 'line': 4, 'type': 'def', 'name': '__init__(self, someargs)'},
  {'depth': 2, 'line': 5, 'type': 'def', 'name': 'whenCall(self)'},
  {'depth': 1, 'line': 9, 'type': 'def', 'name': 'findthis(self)'},
  {'depth': 1, 'line': 12,  'type': 'def', 'name': 'find_multi(self)'},
  {'depth': 0, 'line': 15, 'type': 'def', 'name': 'this()'},
  {'depth': 0, 'line': 19, 'type': 'def', 'name': 'that(a,b,c)'},
  {'depth': 1, 'line': 20, 'type': 'def', 'name': 'private()'}
]

我正在考虑让结果看起来像以下层次结构:

functions_hir = [{
    'value': {'depth': 0, 'line': 3, 'type': 'class', 'name': 'General(object)'}, 
    'children': [{

        'value': {'depth': 1, 'line': 4, 'type': 'def', 'name': '__init__(self, someargs)'},
        'children': [{

            'value': {'depth': 2, 'line': 5, 'type': 'def', 'name': 'whenCall(self)'},
            'children': []
        }]
    },{
        'value': {'depth': 1, 'line': 9, 'type': 'def', 'name': 'findthis(self)'},
        'children': []
    },{
        'value': {'depth': 1, 'line': 12,  'type': 'def', 'name': 'find_multi(self)'},
        'children': [] 
    }]
},{
    'value': {'depth': 0, 'line': 15, 'type': 'def', 'name': 'this()'},
    'children': []
},{
    'value': {'depth': 0, 'line': 19, 'type': 'def', 'name': 'that(a,b,c)'},
    'children': [{

        'value': {'depth': 1, 'line': 20, 'type': 'def', 'name': 'private()'},
        'children': []
    }]
}]

现在我可以很简单地对其进行迭代/递归。但我没有任何运气从我的列表中生成这样的层次结构(我猜我什至还没有接近)..而且我实际上不知道从哪里开始..希望任何人都可以设法帮助我!

Answer 1

你可以使用递归方法，这个函数将在线性时间内创建你想要的字典:

functions = [
  {'depth': 0, 'line': 3, 'type': 'class', 'name': 'General(object)'},
  {'depth': 1, 'line': 4, 'type': 'def', 'name': '__init__(self, someargs)'},
  {'depth': 2, 'line': 5, 'type': 'def', 'name': 'whenCall(self)'},
  {'depth': 1, 'line': 9, 'type': 'def', 'name': 'findthis(self)'},
  {'depth': 1, 'line': 12,  'type': 'def', 'name': 'find_multi(self)'},
  {'depth': 0, 'line': 15, 'type': 'def', 'name': 'this()'},
  {'depth': 0, 'line': 19, 'type': 'def', 'name': 'that(a,b,c)'},
  {'depth': 1, 'line': 20, 'type': 'def', 'name': 'private()'}
]

i = 0
def gather(d):
    global i
    res = []
    while i < len(functions):
        if functions[i]["depth"] < d:
            return res
        elif functions[i]["depth"] == d:
            value, i = functions[i], i + 1
            children = gather(d + 1)
            res.append({"value": value, "children": children})
    return res

result = gather(0)

或者你可以在没有全局变量的情况下做到这一点:

def gather(d, i):
    res = []
    while i < len(functions):
        if functions[i]["depth"] < d:
            return i, res
        elif functions[i]["depth"] == d:
            value = functions[i]
            i, children = gather(d + 1, i + 1)
            res.append({"value": value, "children": children})
    return i, res

result = gather(0, 0)[1]