python - 如何将字符串处理成子列表层

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上看到过将列表分成大小相等的列表，但没有一个使用一组标准进入子列表。

我对python相当陌生，所以我对数据结构和迭代器工具不太熟悉。

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)))

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分隔符平衡，上述方法就可以工作；特别是，如果你有多余的cs，你将有一个堆栈下溢。

虽然我经常喜欢递归解决方案，但这具有使堆栈显式的优点，在这种情况下，在我看来，这会导致更容易 grok 代码。

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's 比 'b's 多，这将中断

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']

需要注意的一些细节：

• 我不使用局部变量或全局变量，只使用函数参数来跟踪状态
• 我不使用赋值运算符
• 没有迭代器或循环用于遍历输入列表，只有递归
• It's a tail-recursive solution, although that's irrelevant in Python
• Only expressions are used; operations like append or extend (which return None) are avoided
• No lists are ever modified (including the input list), instead new lists are created as needed (using array slices for that)
• It's a rather short and elegant solution, but that might be a subjective opinion :)

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. 通过复制来改变它是微不足道的。

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()

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

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']