Full addresses from nested dictionaries

Question

We have data like this

input = {
    'a': 3,
    'b': {'g': {'l': 12}},
    'c': {
        'q': 3,
        'w': {'v': 3},
        'r': 8,
        'g': 4
    },
    'd': 4
}

It is not known in advance how many nesting levels there will be We need to get the full address to the final value, all points of which are separated by a dot, or another special character Like this:

a:3
b.g.l: 12
c.q: 3
c.w.v: 3
etc

I tried to solve this problem with a recursive function.

def recursive_parse(data: dict, cache: Optional[list]=None):
    if cache is None:
        cache = []
    for k in data:
        cache.append(k)
        if not isinstance(data[k], dict):
            print(f"{'.'.join(cache) } :{data[k]}")
            cache.clear()
        else:
            recursive_parse(data[k], cache)

But I have problems with "remembering" the previous key of the nested dictionary.

a :3
b.g.l :12
c.q :3
w.v :3
r :8
g :4
d :4

What is the correct algorithm to solve this?

Answer 1

It's probably better to use an explicit stack for this, rather than the Python call stack. Recursion is slow in Python, due to high function call overhead, and the recursion limit is fairly conservative.

def dotted(data):
    result = {}
    stack = list(data.items())
    while stack:
        k0, v0 = stack.pop()
        if isinstance(v0, dict):
            for k1, v1 in v0.items():
                item = ".".join([k0, k1]), v1
                stack.append(item)
        else:
            result[k0] = v0
    return result

Demo:

>>> data
{'a': 3,
 'b': {'g': {'l': 12}},
 'c': {'q': 3, 'w': {'v': 3}, 'r': 8, 'g': 4},
 'd': 4}
>>> for k, v in reversed(dotted(data).items()):
...     print(k, v)
... 
a 3
b.g.l 12
c.q 3
c.w.v 3
c.r 8
c.g 4
d 4

Answer 2

Try:

dct = {
    "a": 3,
    "b": {"g": {"l": 12}},
    "c": {"q": 3, "w": {"v": 3}, "r": 8, "g": 4},
    "d": 4,
}


def parse(d, path=None):
    if path is None:
        path = []

    if isinstance(d, dict):
        for k, v in d.items():
            yield from parse(v, path + [k])
    else:
        yield "{}: {}".format(".".join(path), d)


for p in parse(dct):
    print(p)

Prints:

a: 3
b.g.l: 12
c.q: 3
c.w.v: 3
c.r: 8
c.g: 4
d: 4