在Python中扁平化嵌套结构

Question

我该怎么做才能把这个在Python中变得扁平化，让每个“widget”都变成列表中的一个元素呢？

{  "widgets" :[{"num": "1", "letter": "a",
              "widgets" :[{"num": "2", "letter": "b",
                           "widgets" :[{"num": "3","letter": "c"},
                                       {"num": "4", "letter": "d"}]
                         }]
            }]
}

最终结果应该是这样的

[{"num":"1", "letter","a"},
 {"num": "2", "letter":"b"},
 {"num": "3", "letter":"c"},
 {"num": "4", "letter":"d"}] 

Answer 1

这是我匆忙写的回复；写完后我意识到它的列表项并没有按照你指定的顺序排列；不过我觉得这可能会在递归方面给你一些启示，就像这里其他的回答一样。

注意：没有导入Python模块“elegance”。；)

def getflattenedwidgetlist(thislist):
    thislevellist = list()
    for dictionary in thislist:
        thisdict = dict()
        thislevellist.append(thisdict)
        for key in dictionary:
            if key != "widgets":
                thisdict[key] = dictionary[key]

        if "widgets" in dictionary:
            return getflattenedwidgetlist(dictionary["widgets"]) + [thisdict]

    return thislevellist


stuff = {
   "widgets" :[{
       "num": "1",
       "letter": "a",
       "widgets" :[{
         "num": "2",
         "letter": "b",
         "widgets" :[{
             "num": "3",
             "letter": "c"
           },
           { 
            "num": "4",
            "letter": "d"
           }]
        }]
    }] 
}

print getflattenedwidgetlist([stuff])

Answer 2

这里有一个递归的解决方案：

def flatten_widget(widget):
    assert isinstance(widget, dict)

    # Remove any sub-level widgets for processing
    widgets = widget.pop('widgets', None)

    # The first object is itself, unless it contains nothing
    flat_list = [widget] if widget else []

    # If there are sub-level widgets, flatten them
    if widgets:
        assert isinstance(widgets, list)
        # Recursively flatten each widget and add it return list
        for w in widgets:
            flat_list += flatten_widget(w)

    # Return all widgets in a list
    return flat_list

print flatten_widget(widget)
# [{'num': '1', 'letter': 'a'}, {'num': '2', 'letter': 'b'}, {'num': '3', 'letter': 'c'}, {'num': '4', 'letter': 'd'}]

请注意，这个方法无法检测循环引用。此外，它假设你不介意原始数据结构会被修改。我没有进行性能测试，但我猜不需要复制每个字典项会稍微快一些。

Answer 3

在你处理完那些给你数据的人之后，可能会用到类似这样的代码：

def flatten_widgets(widget):
    stack = [widget['widgets']]
    while stack:
        for widget in stack.pop():
            yield {k: v for k, v in widget.items() if k != 'widgets'}
            if 'widgets' in widget:
                stack.append(widget['widgets'])

>>> list(flatten_widgets(a))

[{'letter': 'a', 'num': '1'},
 {'letter': 'b', 'num': '2'},
 {'letter': 'c', 'num': '3'},
 {'letter': 'd', 'num': '4'}]