Generate a nested list from flatten data in Python

To generate a Table of Content, I have these data available in a Python list:

data = [
    {title: 'Section 1', level: 1, page_number: 1},
    {title: 'Section 1.1', level: 2, page_number: 2},
    {title: 'Section 1.2', level: 2, page_number: 3},
    {title: 'Section 2', level: 1, page_number: 4},
    {title: 'Section 2.1', level: 2, page_number: 5},
    {title: 'Section 开发者_如何学运维3', level: 1, page_number: 6},
]

From this, I'd like to obtain this kind of nested structure, much more compatible with the use of a template engine:

toc = [
    {title: 'Section 1', page_number: 1, sub: [
        {title: 'Section 1.1', page_number: 2, sub: []},
        {title: 'Section 1.2', page_number: 3, sub: []},
    ]},
    {title: 'Section 2', page_number: 4, sub: [
        {title: 'Section 2.1', page_number: 5, sub: []},    
    ]},
    {title: 'Section 3', page_number: 6, sub: []},
]

Hints on how to achieve this? I tried with a recursive function but it's getting much tricky for my limited brain.

Any help much appreciated.

EDIT: Added fact that a section entry can have eventually no child. Sorry for the miss.

Assuming chapters come in order, meaning child chapter is always after the parent, and there are no missing parent (skipped levels):

import pprint

data = [
    {'title': 'Section 1', 'level': 1, 'page_number': 1},
    {'title': 'Section 1.1', 'level': 2, 'page_number': 2},
    {'title': 'Section 1.2', 'level': 2, 'page_number': 3},
    {'title': 'Section 2', 'level': 1, 'page_number': 4},
    {'title': 'Section 2.1', 'level': 2, 'page_number': 42},
    {'title': 'Section 2.1.1', 'level': 3, 'page_number': 42},
    {'title': 'Section 3', 'level': 1, 'page_number': 42},
]

toc = []
stack = [toc]
for d in data:
    d['sub'] = []   
    while d['level'] < len(stack):
        stack.pop()
    while d['level']  > len(stack):
        stack.append(stack[-1][-1]['sub'])
    stack[-1].append(d)


pprint.pprint(toc)

Result:

[{'level': 1,
  'page_number': 1,
  'sub': [{'level': 2, 'page_number': 2, 'sub': [], 'title': 'Section 1.1'},
          {'level': 2, 'page_number': 3, 'sub': [], 'title': 'Section 1.2'}],
  'title': 'Section 1'},
 {'level': 1,
  'page_number': 4,
  'sub': [{'level': 2,
           'page_number': 42,
           'sub': [{'level': 3,
                    'page_number': 42,
                    'sub': [],
                    'title': 'Section 2.1.1'}],
           'title': 'Section 2.1'}],
  'title': 'Section 2'},
 {'level': 1, 'page_number': 42, 'sub': [], 'title': 'Section 3'}]

EDIT: changed it to have empty 'sub' items where there are no children. See the other variant in edit history.

Does this do what you want?

TITLE, LEVEL, PAGE_NUMBER, SUB = 'title', 'level', 'page_number', 'sub'
data = [
    {TITLE: 'Section 1', LEVEL: 1, PAGE_NUMBER: 1},
    {TITLE: 'Section 1.1', LEVEL: 2, PAGE_NUMBER: 2},
    {TITLE: 'Section 1.1.1', LEVEL: 3, PAGE_NUMBER: 2},
    {TITLE: 'Section 1.2', LEVEL: 2, PAGE_NUMBER: 3},
    {TITLE: 'Section 2', LEVEL: 1, PAGE_NUMBER: 4},
    {TITLE: 'Section 2.1', LEVEL: 2, PAGE_NUMBER: 5},
]

levels = [ { SUB: [] } ]
for section in data:
    section = dict(section)
    current = section[LEVEL]
    section[SUB] = []
    levels[current-1][SUB].append(section)
    del levels[current:]
    levels.append(section)

toc = levels[0][SUB]
from pprint import pprint
pprint(toc)

You could walk through each entry in your list and build a new list from there. Whenever there is a "Section x.y", you'll add it under sub.

newData = []
curParent = None
for d in data:
  # child
  if d['title'].find('.') > 0:
    assert curParent # Make sure we have a valid parent dictionary
    curParent['sub'].append({'title': d['title'], 'page_number': d['page_number'])
  # parent
  else:
    curParent = {'title': d['title'], 'page_number': d['page_number'], 'sub': []}
    newData.append(curParent)

That should work for 2 or 3 levels, if you need many more than a different approach might be better. Also, the find('.') might not work with other titles, but either use the level field (which seems redundant in your example) or regular expressions.