蟒蛇 - 從棧跟蹤到樹

Question

我一直在爲我的腦子尋找一個簡單的遞歸方式來做這件事，現在有一段時間 - 說我有一個堆棧狀態序列看起來像這樣，作爲一個列出清單：

[ 
[a] 
[a,b] 
[a,b,c] 
[a,b] 
[a,b,d] 
[a,b] 
[a] 
[a,e] 
] 

我想借此和代表它基本上爲一棵樹，但使用嵌套列表的層，但沒有設定樹一個新的類。

以上的樹格式可能會是這個樣子

[a, [b, [c], 
     [d]], 
    [e] ] 

本質上，他說，因爲c和d B之後來到，他們是B的孩子，因爲他們在堆棧跟蹤沒有追隨者，他們之後什麼都沒有（或者是一個空的名單來代表沒有孩子）。因此，這也就夠了：

[a, [b, [c, []], 
     [d, []], 
    [e, []  ] 

基本上代表的樹是

a 
/\ 
e b 
    /\ 
    c d 

但完全沒有類。是的，我知道這是不潔的，一個班可能是乾淨的做法，但我對這個沒有班級的解決方案感興趣。

Answer 1

這在這裏你想要做什麼，而把每個節點在它自己的名單，這是更具可讀性和可恕我直言：

input = 
[['a'], 
['a', 'b'], 
['a', 'b', 'c'], 
['a', 'b'], 
['a', 'b', 'd'], 
['a', 'b'], 
['a'], 
['a', 'e']] 

output = [] 
item_node = {} 
for lst in input: 
    for i in range(len(lst)): 
     if lst[i] not in item_node: 
      item_node[lst[i]] = [lst[i], []] 
      if i == 0: 
       output.append(item_node[lst[i]]) 
      else: 
       item_node[lst[i-1]][1].append(item_node[lst[i]]) 

Out[47]: [['a', [['b', [['c', []], ['d', []]]], ['e', []]]]] 

爲了得到它在你想要第一格式，使用相同的設置：

for lst in input: 
    for i in range(len(lst)): 
     if lst[i] not in item_node: 
      item_node[lst[i]] = [lst[i]] 
      if i == 0: 
       output.append(item_node[lst[i]]) 
      else: 
       item_node[lst[i-1]].append(item_node[lst[i]]) 


Out[58]: [['a', ['b', ['c'], ['d']], ['e']]] 

要得到你的第二個選項：

for lst in input: 
    for i in range(len(lst)): 
     if lst[i] not in item_node: 
      item_node[lst[i]] = [] 
      if i == 0: 
       output.append(lst[i]) 
       output.append(item_node[lst[i]]) 
      else: 
       item_node[lst[i-1]].append(lst[i]) 
       item_node[lst[i-1]].append(item_node[lst[i]]) 
Out[54]: ['a', ['b', ['c', [], 'd', []], 'e', []]]