Python 递归 : nested list from flat list

Question

我需要弄清楚如何创建(我认为需要的)递归函数。我的大脑从来没有很好地处理递归。

我有一个项目的平面集合，需要根据每个项目中的值将其转换为嵌套集合。除了其他属性外，每个项目都有一个类型。一种可能的 item.type 是“group header”。每个“组页眉”将由“组页脚”关闭。我需要根据这两种类型嵌套集合。

集合可能看起来像这样:

• 项目 1:type = blurb
• 第 2 项:type = group header
• 第 3 项:类型 = 问题
• 第 4 项:类型 = 问题
• 第 5 项:type = group header
• 第 6 项:类型 = 问题
• 第 7 项:类型 = 问题
• 第 8 项:类型 = 组页脚
• 第 9 项:类型 = 问题
• 第 10 项:类型 = 组页脚

我想让那个集合看起来更像这样:

• 项目 1:简介
• 第 2 项:页眉，第 10 项:页脚
• • 第 3 项:问题
• • 第 4 项:问题
• • 第 5 项:组页眉，第 8 项:页脚
• • • 第 6 项:问题
• • • 第 7 项:问题
• • 第 9 项:问题

可以有任何深度的嵌套，因此(我认为)需要递归。

非常感谢有关如何操作的任何指示。我根本无法理解它，也找不到在线示例，其中标签(在我的例子中是“组页脚”)用于跳回嵌套级别。

以下是可以使用的 python fiddle 的开头部分: http://pythonfiddle.com/recursion-fiddle-ninety-nine

来自链接的示例数据:

test_data = [{"id":1, "type":"blurb", "info":"This is the blurb"},
            {"id":2, "type":"header", "info":"This is the first group header"},
            {"id":3, "type":"question", "info":"This is the first question"},
            {"id":4, "type":"question", "info":"This is the second question"},
            {"id":5, "type":"header", "info":"This is the second group header"},
            {"id":6, "type":"question", "info":"This is the third question"},
            {"id":7, "type":"question", "info":"This is the fourth question"},
            {"id":8, "type":"footer", "info":"This is the footer for the second header"},
            {"id":9, "type":"question", "info":"This is the fifth question"},
            {"id":10, "type":"footer", "info":"This is the footer for the first header"}]

提前致谢

周杰伦

Answer 1

我不知道您希望结果列表的格式究竟如何，但是您可以:

nested_data = []
stack= []
for item in test_data:
    if item['type']=='header': # if it's a header
        # add [item] to the list (the footer will be appended to this later)
        header= [[item]]
        nested_data.append(header)
        # push this list onto the stack so we can continue appending to it
        # after we've found the footer
        stack.append(nested_data)
        nested_data= header
    elif item['type']=='footer':
        # if it's a footer, pop the last list off the stack
        nested_data= stack.pop(-1)
        # and append the footer after the header so that
        # [header, footer] is the first item
        nested_data[-1][0].append(item)
    else:
        # if it's just a boring ol' item, all we need do is append it
        nested_data.append(item)

这会产生(nested_data 变量保存结果):

[
  {
    "info": "This is the blurb", 
    "type": "blurb", 
    "id": 1
  }, 
  [
    [
      {
        "info": "This is the first group header", 
        "type": "header", 
        "id": 2
      }, 
      {
        "info": "This is the footer for the first header", 
        "type": "footer", 
        "id": 10
      }
    ], 
    {
      "info": "This is the first question", 
      "type": "question", 
      "id": 3
    }, 
    {
      "info": "This is the second question", 
      "type": "question", 
      "id": 4
    }, 
    [
      [
        {
          "info": "This is the second group header", 
          "type": "header", 
          "id": 5
        }, 
        {
          "info": "This is the footer for the second header", 
          "type": "footer", 
          "id": 8
        }
      ], 
      {
        "info": "This is the third question", 
        "type": "question", 
        "id": 6
      }, 
      {
        "info": "This is the fourth question", 
        "type": "question", 
        "id": 7
      }
    ], 
    {
      "info": "This is the fifth question", 
      "type": "question", 
      "id": 9
    }
  ]
]