計數JSON葉節點

Question

我想計算JSON結構中的葉節點數（即只有沒有其他子元素的節點）節點數。

我找不到任何明顯的做法，所以一直在努力編寫一個函數，但我努力尋找一個可以工作的函數，而不使用全局變量。

這是我到目前爲止有：

def count_leafs(nested): 
    is isinstance(nested, Mapping): 
    for k, v in nested.items(): 
     if isinstance(v, Mapping): 
     for i_k, i_v in count_leafs(v): 
      yield i_k, i_v 
     elif isinstance(v, MutableSequence): 
     for i_k in v: 
      for i_i_k, i_i_v in i_k.items(): 
      count_leafs(i_i_v) 
     else: 
     yield k, v 
    elif isinstance(nested, MutableSequence): 
    for k in nested: 
     count_leafs(k) 


for k,v in count_leafs(json): 
leaf_count += 1 

這並未真正發揮一些非葉節點進行計數，並且它不是遞歸一路下跌到一些結構。

Answer 1

一般來說，我更喜歡非遞歸解決方案而不是遞歸解決方案。我的算法是這樣的：

1. 初始化隊列和JSON對象放到它
2. 循環而隊列不爲空
3. 獲取一個節點從隊列
   • 如果是映射，將所有值添加到隊列中供以後處理
   • 如果它是一個序列或一組（請注意：字符串也是序列，我們需要對它進行測試），我們將所有元素添加到隊列中用於後續處理
   • 如果它是以上皆非，指望它

下面是代碼：

from collections import Mapping, Sequence, Set, deque 

def count_leaves(nested): 
    queue = deque([nested]) 
    count = 0 
    while queue: 
     node = queue.popleft() 
     if isinstance(node, Mapping): 
      queue.extend(node.values()) 
     elif isinstance(node, (Sequence, Set)) and not isinstance(node, basestring): 
      queue.extend(node) 
     else: 
      count += 1 

    return count 

Answer 2

你的僞代碼是過於複雜和越野車。我還建議您編寫緊密跟在PEP 8 - Style Guide for Python Code之後的代碼，供您和其他人閱讀您編寫的代碼。

總之，作爲測試的情況下，假設你有一些像這樣的JSON數據：

json_data = { 
    "glossary": { 
     "title": "example glossary", 
     "answer": 42, 
     "boolean": True, 
     "nada": None, 
     "GlossDiv": { 
      "GlossList": { 
       "GlossEntry": { 
        "GlossDef": { 
         "GlossSeeAlso": [ 
          "GML", 
          "XML" 
         ], 
         "para": "A meta-markup language, used to create markup " 
           "languages such as DocBook." 
        }, 
        "GlossSee": "markup", 
        "Acronym": "SGML", 
        "GlossTerm": "Standard Generalized Markup Language", 
        "SortAs": "SGML", 
        "Abbrev": "ISO 8879:1986", 
        "ID": "SGML" 
       } 
      }, 
      "title": "S" 
     } 
    } 
} 

您可以遞歸數樹葉像這樣：

from collections import Mapping, MutableSequence 

def count_leaves(json_obj): 

    def leaf_iterator(json_obj): 
     if isinstance(json_obj, Mapping): 
      for v in json_obj.values(): 
       for obj in leaf_iterator(v): 
        yield obj 
     elif isinstance(json_obj, MutableSequence): 
      for v in json_obj: 
       for obj in leaf_iterator(v): 
        yield obj 
     else: 
      yield json_obj 

    return sum(1 for leaf in leaf_iterator(json_obj)) 

leaf_count = count_leaves(json_data) 
print('leaf count: {}'.format(leaf_count)) # -> leaf_count: 14 

我內部嵌套的leaf_iterator()發生器葉計數功能，但它也可以在外部定義，如果它應該在更大範圍內證明有用。 Python 3中的代碼可以通過使用在Python 3.3中引入的yield from<expression>進一步簡化。