Рекурсивно проверьте наличие ключа и добавьте его в массив dict

У меня есть дикт следующим образом

{
   "key1" : "value1",
   "key2" : "value2",
   "key3" : "value3",
   "key4" : {
       "key5" : "value5"
   }
}

Если в dict есть key1 == value1, я добавлю dict в список.

Предположим, что ключ1==значение1 отсутствует в первой паре ключ-значение, тогда как он находится внутри вложенного словаря следующим образом:

{
   "key2" : "value2",
   "key3" : "value3",
   "key4" : {
       "key5" : "value5",
       "key1" : "value1",
       "key6" : { 
          "key7" : "value7",
          "key1" : "value1"
       }
   },
   "key8" : { 
       "key9" : "value9",
       "key10" : {
            "key11" : "value11",
            "key12" : "value12",
            "key1" : "value1"
       }
   }
}

В приведенном выше словаре я должен сначала проверить, есть ли key1 = value1. Если нет, я должен просмотреть вложенный словарь, и если он найден во вложенном словаре, я должен добавить этот словарь в список. Если вложенный словарь также является вложенным словарем, но ключ1=значение1 находится в первой паре значений ключа, то нет необходимости проверять внутренний словарь (например, ключ4 имеет ключ1=значение1 в первой паре значений ключа. Следовательно, нет необходимости проверьте внутренний, хотя key6 имеет key1 = value1).

Итак, наконец, у меня будет следующий список.

[
   {
       "key5" : "value5",
       "key1" : "value1",
       "key6" : { 
          "key7" : "value7",
          "key1" : "value1"
       }
   },
   {
            "key11" : "value11",
            "key12" : "value12",
            "key1" : "value1"
   }
]

Как этого добиться? Примечание. Глубина словаря может варьироваться.


python dictionary
person NagaLakshmi    schedule 27.03.2015    source источник
comment
У вас есть произвольные глубокие диктовки или только до управляемого предела?   -  person syntonym    schedule 27.03.2015
comment
@syntonym Предполагая, что это произвольно глубоко ..   -  person NagaLakshmi    schedule 27.03.2015

Ответы (1)


arrow_upward
3
arrow_downward

если словарь содержит key1 и value1, мы добавим его в список и закончим. если нет, мы получим все значения в словаре, которые равны dict, и проделаем ту же логику.

l = []
def append_dict(d):
    if d.get("key1") == "value1":
        l.append(d)
        return

    for k,v in d.items():
        if isinstance(v, dict):
            append_dict(v) 


append_dict(d)
print l

итеративное решение будет добавлять в очередь диктофон, который мы хотели бы проверить:

from Queue import Queue
q = Queue() 
l = []
q.put(d)
while not q.empty():
    d = q.get()
    if d.get("key1") == "value1":
        l.append(d)
        continue
    for k,v in d.items():
        if isinstance(v, dict):
            q.put(v) 

print l

Как отметил @shashank, использование stack вместо queue также будет работать, это BFS против DFS для поиска в словаре

person Udy    schedule 27.03.2015
comment
Разве if d[k] == v будет недостаточно? Кроме того, это рекурсия, которая может не работать для произвольных глубоких диктовок (потому что максимальная глубина рекурсии python), но может быть достаточно. - person syntonym; 27.03.2015
comment
при написании объяснения тоже это заметил. правда о рекурсии, будет делать это также итеративно - person Udy; 27.03.2015
comment
ОП запросил рекурсию - person Moshe Carmeli; 27.03.2015
comment
Правда, Stack против Queue будет DFS против BFS - person Udy; 27.03.2015
comment
Хороший ответ. Примечание. Если вы хотите имитировать порядок поиска в глубину LIFO, вместо очереди следует использовать стек. Или используйте Deque, чтобы имитировать точный порядок рекурсивной функции. Очередь будет выполнять поиск в ширину. - person Shashank; 27.03.2015
comment
@MosheCarmeli Он использовал термин в заголовке, чтобы указать, что он хочет пройти по всем подразделам, но рекурсивная обработка несовместима с произвольными глубокими словарями в python, тогда как итеративное решение будет работать. Я не думаю, что он использовал термин recursive технический, но для описания своей проблемы. - person syntonym; 27.03.2015