计算python字典/数组数据结构的非空尾叶 - 递归算法? [英] Count non-empty end-leafs of a python dicitonary/array data structure - recursive algorithm?

问题描述

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

I'm looking for a function to find all the non-empty end-points of a kind of complex dictionary/array structure. I think that because I don't know the number of nested arrays or their locations, it would have to be recursive, and I just don't entirely get that way of thinking yet.

所以对于嵌套的字典:

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"表示有一个数组(variable.js的风格):

and variable "paths" named as follows, where ".XX" designates there is an array (in the style of variety.js):

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

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

I'd like a function f(x,y) that can return...

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

对我来说，问题似乎是在你去的时候试图构造树，以及将计数器放在哪里以获取空值.所以，我不太明白如何正确记录计数器或进行递归.

The problem for me seems to be trying to construct the tree as you go and where to put the counter for nulls. So, I don't quite understand how to record the counters or do recursion correctly.

推荐答案

也许这可以引导您朝着正确的方向前进.byPath 收集嵌套的字典项.一旦调用，您基本上可以展平结果列表并检查您的条件是否满足(例如 elem !='' 或 not elem 或其他):

Maybe this can guide you in the right direction. byPath collects the nested dictionary items. Once called, you can basically flatten out the resulting list and check if your condition is met (like elem != '' or not elem or whatever):

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') )

编辑:这里是实际计算那些不是空字符串的元素的部分:

EDIT: Here the part for actually counting those elements that are not an empty string:

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字典/数组数据结构的非空尾叶 - 递归算法?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！