Erstellen Sie einen Baum aus mehreren verschachtelten Wörterbüchern/Listen in Python

Question

Vorwort: Um zu erklären, warum Ich mache das, ich werde das Endziel erklären. Im Wesentlichen habe ich eine Liste von Konten, die in einer sehr spezifischen Syntax definiert sind. Hier sind einige Beispiele:

Wie oben zu sehen, kann ein Konto beliebig viele Eltern und Kinder haben. Das Endziel besteht darin, die obigen Konten in eine Baumstruktur in Python zu zerlegen, die für die automatische Vervollständigung von Konten im Editor für erhabenes Text verwendet wird (dh wenn ich Assets: eingab und dann für die automatische Vervollständigung abgefragt würde, würde ich mit einer Liste als solche präsentiert werden: Bank, Ersparnisse, reserviert)

das Ergebnis: die Kontoliste aus dem Vorwort Verwendung würde das gewünschte Ergebnis in Python aussieht etwas wie unten:

[ 
    { 
     "Assets":[ 
     { 
      "Bank":[ 
       "Car", 
       "House" 
      ] 
     }, 
     { 
      "Savings":[ 
       "Emergency", 
       { 
        "Goals":[ 
        "Roof" 
        ] 
       } 
      ] 
     }, 
     "Reserved" 
     ] 
    } 
] 

Halb-Lösung: Ich wa s sind in der Lage, zwei grundlegende Accounts zu erhalten, die durch Rekursion zusammengefügt werden. Dies funktioniert für das Hinzufügen dieser zwei: Assets:Bank:Car und Assets:Bank:House. Sobald sie sich jedoch voneinander zu unterscheiden beginnen, fällt sie auseinander und die Rekursion wird unordentlich, so dass ich mir nicht sicher bin, ob es der beste Weg ist.

import re 

def parse_account(account_str): 
    subs = account_str.split(":") 

    def separate(subs): 
     if len(subs) == 1: 
      return subs 
     elif len(subs): 
      return [{subs[0]: separate(subs[1:])}] 

    return separate(subs) 

def merge_dicts(a, b): 
    # a will be a list with dictionaries and text values and then nested lists/dictionaries/text values 
    # b will always be a list with ONE dictionary or text value 

    key = b[0].keys()[0] # this is the dictionary key of the only dictionary in the b list 

    for item in a: # item is a dictionary or a text value 
     if isinstance(item, dict): # if item is a dictionary 
      if key in item: 
       # Is the value a list with a dict or a list with a text value 
       if isinstance(b[0][key][0], str): 
        # Extend the current list with the new value 
        item[key].extend(b[0][key]) 
       else: 
        # Recurse to the next child 
        merge_dicts(item[key], b[0][key]) 
      else: 


    return a 

# Accounts have an "open [name]" syntax for defining them 
text = "open Assets:Bank:Car\nopen Assets:Bank:House\nopen Assets:Savings:Emergency\nopen Assets:Savings:Goals:Roof\nopen Assets:Reserved" 
EXP = re.compile("open (.*)") 
accounts = EXP.findall(text) # This grabs all accounts 

# Create a list of all the parsed accounts 
dicts = [] 
for account in accounts: 
    dicts.append(parse_account(account)) 

# Attempt to merge two accounts together 
final = merge_dicts(dicts[0], dicts[1]) 
print final 

# In the future we would call: reduce(merge_dicts, dicts) to merge all accounts 

Ich könnte das völlig falsch machen und würde mich für unterschiedliche Meinungen interessieren. Hat jemand sonst einen Einblick, wie dies mit den verbleibenden Konten in der Beispielzeichenfolge funktioniert?

Answer 1

Das dauerte mich ewig in meinem Kopf zu sortieren. Die Wörterbücher sind einfach, ein Schlüssel, der immer eine Liste als Wert hat - sie haben eine benannte Liste.

Innerhalb der Listen wird eine Zeichenfolge oder ein anderes Wörterbuch (mit einem Schlüssel mit einer Liste) sein.

Das bedeutet, wir können 'Assets: Bank: Car' aufspalten und in der Root-Liste nach einem Wörterbuch suchen, das {"Assets":[<whatever>]} entspricht, oder eins hinzufügen - und dann zur [<whatever>] Liste zwei Ebenen tiefer springen. Nächste Schleife, suche nach einem Wörterbuch, das {"Bank":[<whatever>]} entspricht, oder füge eins hinzu, springe zur [<whatever>] Liste zwei Ebenen tiefer. Machen Sie das so lange, bis wir den letzten Knoten Car erreicht haben. Wir müssen auf eine Liste sein, da wir immer zu einer bestehenden Liste gesprungen oder eine neue gemacht haben, also setzen Sie Car in die aktuelle Liste.

NB. Dieser Ansatz würde brechen, wenn Sie

Assets:Reserved 
Assets:Reserved:Painting 

haben aber das wäre ein Unsinn widerstreitender Eingang, zu fragen: „Reserviert“ zu sein, sowohl Blattknoten und Behälter, und in dieser Situation würde man nur haben:

Assets:Reserved:Painting 

richtig?

data = """ 
Assets:Bank:Car 
Assets:Bank:House 
Assets:Savings:Emergency 
Assets:Savings:Goals:Roof 
Assets:Reserved 
""" 
J = [] 

for line in data.split('\n'): 
    if not line: continue 

    # split the line into parts, start at the root list 
    # is there a dict here for this part? 
    # yes? cool, dive into it for the next loop iteration 
    # no? add one, with a list, ready for the next loop iteration 
    # (unless we're at the final part, then stick it in the list 
    #  we made/found in the previous loop iteration) 

    parts = line.split(':') 
    parent_list, current_list = J, J 

    for index, part in enumerate(parts): 
     for item in current_list: 
      if part in item: 
       parent_list, current_list = current_list, item[part] 
       break 
     else: 
      if index == len(parts) - 1: 
       # leaf node, add part as string 
       current_list.append(part) 
      else: 
       new_list = [] 
       current_list.append({part:new_list}) 
       parent_list, current_list = current_list, new_list  

print J 

->

[{'Assets': [{'Bank': ['Car', 'House']}, {'Savings': ['Emergency', {'Goals': ['Roof']}]}, 'Reserved']}] 

Online ausprobieren: https://repl.it/Ci5L