Создан вложенный / рекурсивный список

Question

Как я могу создать список рекурсивно?

У меня есть этот список:

l = ['a', 'b', 'new', 'c', 'd', 'new', 'z', 'x', 'c', 'fin', 'f', 'fin', 
     'g', 'l', 'new', 'z', 'x', 'c', 'fin', 'j']

Ожидаемый результат:

r = ['a', 'b', ['c', 'd', ['z', 'x', 'c'] 'f'], 'g', 'l', ['z', 'x', 'c'] 'j']

ЧтоЯ пробовал до сих пор:

def asd(l, index=0):
    r = []
    for i in l[index:]:
        index += 1
        if i == 'new':
            i, index = asd(l, index)
        r.append(i)
        if i == 'fin':
            return r
    return r, index

r, index = asd(l)

Я не могу понять, как заставить это работать.Кто-нибудь может мне помочь?

Answer 1

Вот прямое рекурсивное решение, использующее deque в качестве структуры стековых данных, из которой вы можете popleft крайний левый элемент в O (1).

Алгоритм

from collections import deque

def nest(lst):
    return _nest(deque(lst))

def _nest(deq):
    result = []

    while deq:
        x = deq.popleft()
        if x == 'fin':
            break
        elif x == 'new':
            result.append(_nest(deq))
        else:
            result.append(x)

    return result

Тесты

tests = [
    [],
    [1, 2, 3],
    [1, 2, 'new', 3, 4, 'fin', 5],
    [1, 2, 'new', 3, 4, 'fin', 5, 6, 'new', 7, 'fin'],
    ['new', 'fin', 'new', 'fin', 'new', 'new', 'fin', 'fin'],
    ['new', 1, 2, 'fin'],
    [1, 2, 3, 'new', 4, 'new', 5, 6, 'fin', 7, 8, 'fin', 9, 10, 'new', 11, 'fin', 12, 13]
]

for test in tests:
    print(nest(test))

Выход

[]
[1, 2, 3]
[1, 2, [3, 4], 5]
[1, 2, [3, 4], 5, 6, [7]]
[[], [], [[]]]
[[1, 2]]
[1, 2, 3, [4, [5, 6], 7, 8], 9, 10, [11], 12, 13]

Answer 2

Вместо этого вы можете использовать стек и просматривать список и использовать его:

def parse(l):
    stack = [[]]

    for i in l:
        if i == "new":
            stack.append([])
        elif i == "fin":
            pop = stack.pop()
            stack[-1].append(pop)
        else:
            stack[-1].append(i)

    return stack[0]

Answer 3

Рекурсивная альтернатива:

def asd(l):
    if 'new' in l:
        index_new = l.index('new')
        keyword = 1
        for index_fin,e in enumerate(l[index_new+1:], index_new+1):
            if e == 'new':
                keyword += 1
            elif e == 'fin':
                keyword -=1
            if not keyword:
                break
        return l[:index_new] + [asd(l[index_new+1:index_fin])] + asd(l[index_fin+1:])
    else:
        return l

Ввод:

['a', 'b', 'new', 'c', 'd', 'new', 'z', 'x', 'c', 'fin', 'f', 'fin', 
     'g', 'l', 'new', 'z', 'x', 'c', 'fin', 'j']

Выход:

['a', 'b', ['c', 'd', ['z', 'x', 'c'], 'f'], 'g', 'l', ['z', 'x', 'c'], 'j']

Answer 4

Это нерекурсивное решение, которое может создать ваш список, анализируя его за один проход без необходимости выполнения дорогостоящих операций index():

l = ['a', 'b', 'new', 'c', 'd', 'new', 'f', 'fin', 'g', 'fin', 'j']

rv = []

curr = [rv]  # things are always added to the last element if not 'fin' or 'new'

for elem in l:
    if elem == "new":
        # create a new list, put it at end of curr 
        curr.append([])
        # add that list to the one before
        curr[-2].append(curr[-1])
    elif elem == "fin":
        # done, remove from curr
        curr.pop() 
    else:
        curr[-1].append(elem)

print(rv)

Вывод:

['a', 'b', ['c', 'd', ['f'], 'g'], 'j']

---

l = ['a', 'b', 'new', '1', '2', '3', 'fin', 'c', 'new', 'x', 'y', 'z', 'fin',]  

приводит к

['a', 'b', ['1', '2', '3'], 'c', ['x', 'y', 'z']]

Вам необходимо защитить его от несбалансированного / неправильного new / fin

---

Отредактировано, чтобы сделать его более краткимпосле комментария Матье.