如何将字符串处理成子列表层级？

Question

这是一个示例表单，稍后我会用文字解释它。我有一个由分割字符串得到的列表...

说

[a, a, a, b, a, a, b, a, c, a, b, a, a, c, a, c, a]

其中，b是标准1，c是标准2

我想将它分成如下列表：

[a, a, a, [b, a, a, [b, a, c], a, [b, a, a, c], a, c], a]

所以我想处理这个字符串，如果遇到符合条件1的项，就打开一个新列表，如果遇到符合条件2的项，就关闭列表并返回上一级。

我试过类似这样的方法，但效果不是很好。

def sublist(self, l):
  for line in list:
    if not b:
    self.data.append(line)
  else:
    sublist(l[line:])       #<-----  not sure how to recurse it.

我之前在stackoverflow上看到过将列表分成相等大小的子列表，但没有看到使用一组条件来将其分成子列表。

- chemelnucfin

Answer 1

这里是你需要的:

lst = "aaabaabacabaacaca"

def go(it):
    for x in it:
        if x == 'b':
            yield [x] + list(go(it))
        else:
            yield x
            if x == 'c':
                break 


print list(go(iter(lst)))

- georg

---

很好。生成器确实简化了递归结构。 - Marcin

请注意，这个程序通过终止输出来处理“下溢”。这可能不是想要的结果。 - Marcin

完全符合我的要求。谢谢。 - chemelnucfin

Answer 2

addlist = []
alllists = []
for item in mylist:
    if item == b:
       newlist = [item]
       addlist.append(newlist)
       alllists.append(addlist)
       addlist = newlist
    elif item == c:
       addlist.append(item)
       addlist = alllists.pop()
    else:
       addlist.append(item)

只要你的b和c分隔符是平衡的，上述方法就能正常工作；特别地，如果你有过多的c，就会出现堆栈下溢。

虽然我经常喜欢使用递归解决方案，但这种方法的优点在于使堆栈显式化，在我看来，这导致了更易于理解的代码。

- Marcin

Answer 3

使用堆栈：

def parseList(inList):
    stack = [[]]
    for element in inList:
        if element == 'b':
            stack.append([element])
            stack[-2].append(stack[-1])
        elif element == 'c':
            stack.pop().append(element)
        else:
            stack[-1].append(element)
    return stack[0]

如果有更多的“c”而不是“b”，这将会出错。

- sobel

---

这个解决方案不起作用，在OP问题的示例中，它会产生“IndexError: list index out of range”的错误。 - Óscar López

Answer 4

这个问题有非常好的答案，我特别喜欢thg435使用生成器的递归解决方案和Marcin的迭代解决方案，后者将元素添加到引用列表中。

我还发现一些解决方案修改了输入列表或使用全局状态，这在我看来违背了递归解决方案的真正精神。以下是我在Python中尝试的纯函数式递归解决方案 - 当然，有更具惯用性和高效的方法来解决这个问题，但我想写一个答案，就像我在一个纯函数式编程语言中写的那样：

# lst: the list to be processed
# acc: accumulated result
# stk: temporary stack
def process(lst, acc, stk):
    if not lst:
        return acc
    elif lst[0] == 'b':
        return process(lst[1:], [lst[0]], [acc] + stk)
    elif lst[0] == 'c':
        return process(lst[1:], stk[0] + [acc + [lst[0]]], stk[1:])
    else:
        return process(lst[1:], acc + [lst[0]], stk)

lst = ['a', 'a', 'a', 'b', 'a', 'a', 'b', 'a', 'c', 'a', 'b', 'a', 'a', 'c', 'a', 'c', 'a']
process(lst, [], [])
> ['a', 'a', 'a', ['b', 'a', 'a', ['b', 'a', 'c'], 'a', ['b', 'a', 'a', 'c'], 'a', 'c'], 'a']

需要注意的一些细节：

• 我不使用局部变量或全局变量，只使用函数参数来跟踪状态
• 我不使用赋值运算符
• 没有使用迭代器或循环来遍历输入列表，只使用递归
• 这是一个尾递归解决方案，虽然在Python中这并不重要
• 只使用表达式；避免使用像append或extend（返回None）这样的操作
• 从不修改任何列表（包括输入列表），而是根据需要创建新列表（使用数组切片）
• 这是一个相当简短和优雅的解决方案，但这可能是主观的意见 :)

- Óscar López

Answer 5

以下代码可以实现此功能：

a, b, c = 1, 2, 3

def sublist(l):
  ret = []
  while l:
    val = l.pop(0)
    if val == b:
      ret.append([val] + sublist(l))
    else:
      ret.append(val)
      if val == c: break
  return ret

l = [a, a, a, b, a, a, b, a, c, a, b, a, a, c, a, c, a]
print l
print sublist(l)

请注意，这会修改l的副作用。通过制作副本可以轻松更改此内容。

- NPE

Answer 6

在真正的递归风格中，你可以这样做：

x = yourlist
i = 0
def lets_parse():
    global i
    fnlist = []
    while i < len(x)
        if x[i] == 'c':
            fnlist.append(x[i])
            i += 1
        return fnlist
        elif x[i] == 'b':
            i += 1
            f = lets_parse()
            f.insert(0, 'b')
            fnlist.append(f)
        else:
            fnlist.append(x[i])
            i += 1
return fnlist

print lets_parse()

请注意全局变量的使用。许多批评者可能会反对它，认为这是糟糕的编码风格。

- cobie

---

的确，这是糟糕的编程风格。在“真正的递归”中，你不需要使用全局变量，结果通过递归函数的参数和返回值传递。 - Óscar López

Answer 7

import ast    
mylist = '[a, a, a, b, a, a, b, a, c, a, b, a, a, c, a, c, a]'
mylist = mylist.replace('a','"a"')
mylist = mylist.replace('b','["b"')
mylist = mylist.replace('c','"c"]')
print ast.literal_eval(mylist)
#Output:
['a', 'a', 'a', ['b', 'a', 'a', ['b', 'a', 'c'], 'a', ['b', 'a', 'a', 'c'], 'a', 'c'], 'a']

- fraxel