计算python dicitonary / array数据结构的非空末页-递归算法？

问题内容：

我正在寻找一种函数来查找一种复杂的字典/数组结构的所有非空端点。我认为这是因为我不知道嵌套数组的数目或它们的位置，所以它必须是递归的，而且我还没有完全想到这种方式。

因此，对于嵌套字典：

x = {"top": {"middle" : [
                         {"nested": "value"},
                         {"nested":"val2"},
                         {"nested":""}
                        ],
            "last" : [
                         {"nested": [
                            {"first":1,"second":1},
                            {"first":0,"second":""}
                            ]
                            },
                         {"nested": [
                            {"first":1,"second":1},
                            {"first":1,"second":2}
                            ]
                            },
                         {"nested": [
                            {"first":1,"second":1},
                            {"first":"","second":""}
                            ]
                            }
                        ]
            },
      "other":1}

变量“ paths”的名称如下，其中“ .XX”表示存在一个数组（采用variant.js的样式）：

vars = ["top.middle.XX.nested",
        "top.last.XX.nested.XX.first",
        "top.last.XX.nested.XX.second",
        "other"]

我想要一个f(x,y)可以返回的函数…

f(x,"top.middle.XX.nested") = 2/3
f(x,"top.last.XX.nested.XX.first") = 5/6
f(x,"top.last.XX.nested.XX.second") = 4/6
f(x,"other") = 1

对我而言，问题似乎是在尝试构建树时以及将计数器放置为null的位置。因此，我不太了解如何记录计数器或正确进行递归。

问题答案：

也许这可以指导您正确的方向。byPath收集嵌套的字典项。调用之后，您基本上可以将结果列表弄平，并检查是否满足您的条件（例如elem != ''或类似条件not elem）：

x = #your x as posted

def byPath (tree, path):
    try: head, tail = path.split ('.', 1)
    except: return tree [path]

    if head == 'XX': return [byPath (node, tail) for node in tree]
    else: return byPath (tree [head], tail)


print (byPath (x, 'top.middle.XX.nested') )
print (byPath (x, 'top.last.XX.nested.XX.first') )
print (byPath (x, 'top.last.XX.nested.XX.second') )
print (byPath (x, 'other') )

编辑：这部分实际计数那些不是空字符串的元素：

def count (result):
    if isinstance (result, list):
        total = 0
        positive = 0
        for e in result:
            r = count (e)
            total += r [1]
            positive += r [0]
        return (positive, total)
    else: return (0 if result == '' else 1, 1)

a = byPath (x, 'top.middle.XX.nested')
b = byPath (x, 'top.last.XX.nested.XX.first')
c = byPath (x, 'top.last.XX.nested.XX.second')
d = byPath (x, 'other')

for x in [a, b, c, d]: print (count (x) )

将所有内容放在一起：

def f (tree, path):
    return count (byPath (tree, path) )

for path in ['top.middle.XX.nested', 'top.last.XX.nested.XX.first', 'top.last.XX.nested.XX.second', 'other']:
    print (path, f (x, path) )

计算python dicitonary / array数据结构的非空末页-递归算法？

微信关注