如何在没有递归的情况下展平嵌套字典？

Question

我遇到了一个可以使字典变平的函数：

def flatten(dictionnary, container=None):
    if container is None:
        container = []
    for k, v in dictionnary.items():
        container.append(k)
        if v:
            flatten(v, container)
    return container

为了测试它，我创建了一个dictionnay，它嵌套了n次，如下所示：

^{pr2}$

函数在n小于999时工作，否则将达到递归限制：

RecursionError: maximum recursion depth exceeded while calling a Python object

因此，经过一点搜索，似乎any recursive function can rewritten to iteration但我不知道如何才能为函数实现，我必须产生相同的结果。在

我在玩这个游戏时遇到的另一个奇怪的问题是，如果我为n >= 998尝试下面的代码：

nesteddict = {}
for i in range(n, 0, -1):
    emptydict = {}
    emptydict[i] = nesteddict
    nesteddict = emptydict
print(nesteddict)

我得到递归错误：

RecursionError: maximum recursion depth exceeded while getting the repr of an object

这很奇怪，因为我没有看到任何递归。在

Answer 1

与其将dict保存在堆栈中，不如将项的迭代器保存在堆栈中。在

这样，您就可以恢复iterator on命令。在

另外，由于您要按顺序暂停和恢复迭代器的执行，因此结果将始终与dict的顺序一致

顺便说一下，@iBug，dict是根据Python 3.7的规范进行排序的

def flatten(dictionary, container=None):
    if container is None:
        container = []
    iterators = []
    iterator = iter(dictionary.items())
    while True:
        for k, v in iterator:
            container.append(k)
            if v:
                # Save the current iterator for later
                iterators.append(iterator)
                # Run on the new dict
                iterator = iter(v.items())
                break

        # Current iterator is done, fetch the next one
        else:
            try:
                iterator = iterators.pop()
            except IndexError:
                return container

print(flatten({1: None, 2: {3: None, 4: None}, 5: None}))
[1, 2, 3, 4, 5]