Как разобрать дерево из строки в Python?
Я отформатировал все свои университетские заметки следующим образом:
CourseName: {
Part 1: {
I.I - Intro: {
Topic1: {
descr1;
descr2: {
2.a;
2.b;
2.c.
};
descr3.
};
Topic2: {
descr: {
example.
}.
}.
};
I.II - NextChapter: {
Topic3: {
whatever.
}.
}.
};
Part 2: {
II.I - FinalChapter: {
content.
}.
}.
}
Я хотел бы структурировать их в Древовидная структура данных, и я пытался делать это рекурсивно и итеративно в последние часы, проводя много исследований в Интернете, но ни одна из моих попыток не сработала.
Я уже реализовал Node класс (с self.__value и списком self.__children и всеми полезными методами, которые вы ожидаете от него), а также Класс дерева (с self.__nodes как Словарь и другими служебными методами), поэтому не стесняйтесь использовать такие методы, как add_node или add_child в любой форме ваших ответов.
Я борюсь с тем, чтобы понять, как структурировать функцию def parseTree(s, l) - которая в идеале принимает в качестве входных данных строку s (мои заметки) и список l, устанавливающий разделители, то есть [":{", ";", "}."] или ["{","}"] или аналогичные - и возвращает объект дерева с каждым узел, имеющий в качестве значения текст, предшествующий :{, и список дочерних элементов (если есть), разделенных ; в тексте.
Любое предложение?
Вы должны сначала переформатировать их в анализируемую форму (JSON, yaml и т. д.).
Чепнер и Дэниел Розман правы - всегда проще использовать существующий синтаксический анализатор. Но если вы делать хотите сделать это самостоятельно, я думаю, вам может не хватать того, что вы на 75% прошли путь к разработке пользовательского рекурсивного синтаксического анализатора спуска, но еще не додумались до идеи реализовать его рекурсивно. Это может помочь вам в поиске. Но, с другой стороны, ваш язык более чем достаточно простой, чтобы вы могли написать простую грамматику для передачи в генератор парсера или структуру парсера вместо написания кода, так что вы можете захотеть вместо этого поискать.
@ekhumoro Я знаю, что мне нужно было показать это, но я не мог, потому что это был неработающий беспорядок, результат проб и ошибок и больше общего представления о том, как подойти к проблеме, а не фактического кода
@abarnert Большое спасибо, это именно то, что я пытался сделать и искал. Передо мной открылся целый новый мир! Я также хочу переформатировать свою "грамматику", чтобы сделать ее максимально простой и доступной для анализа, чтобы это работало. Но в 75% случаев это долгий путь ... Я все еще не знаю, как добиться прогресса.
Я не знаю, куда вам указать, чтобы закончить работу над существующим пользовательским парсером. (Я бы не советовал использовать учебник, который я использовал, даже если бы он не предполагал, что вы уже хорошо разбираетесь в рекурсивном манипулировании деревьями в стиле Scheme, но в API Common Lisp.) Большинство примеров рекурсивного спуска парсеров либо тривиальны, либо до смешного сложны, потому что они две крайности там, где вы используете их на практике. Но что касается изучения библиотек и генераторов синтаксического анализатора, я знаю нескольких человек, которые научились создавать свой первый синтаксический анализатор с помощью учебника по pyparsing и вики, полной примеров, так что, возможно, стоит попробовать.
Хотя ответ Ajax1234 - довольно хороший вводный пример, который также точно соответствует вашей грамматике, что значительно упрощает работу, если вы хотите выяснить, как и почему это работает. :)
Ответы 2
На самом деле это почти синтаксически верный YAML. Простая замена сделает его действительным:
data = data.replace(';', ',').replace('.', '')
parsed = yaml.load(data)
Вы, вероятно, захотите более конкретные замены, по крайней мере, только ; и ., которые заканчивают строку.
Предполагая, что ваши данные хранятся в файле, вы можете создать простой класс для синтаксического анализа структуры в словаре. Вы можете рекурсивно просматривать данные, создавая новый объект Notes для каждого найденного ключа:
file_data = filter(None, [i.strip('\n') for i in open('filename.txt')])
import re
class Notes:
def __init__(self, token_data):
self.token_data = token_data
self.current_dict = {}
self.current_vals = []
self.parse()
def parse(self):
while True:
start = next(self.token_data, None)
if not start or "}" in start:
break
if start.endswith('{'):
note = Notes(self.token_data)
final_result = filter(lambda x:x, note.current_vals + [note.current_dict]) if note.current_vals else note.current_dict
self.current_dict[re.findall('[\w\s\-\.]+', re.sub('^\s+', '', start))[0]] = final_result[0] if isinstance(final_result, list) and len(final_result) == 1 else final_result
self.token_data = note.token_data
else:
self.current_vals.append(re.sub('^\s+', '', start))
course_notes = Notes(iter(file_data)).current_dict
Выход:
{'CourseName':
{'Part 1':
{'I.I - Intro':
{'Topic1': ['descr1;',
'descr3.',
{'descr2': ['2.a;',
'2.b;',
'2.c.']
}
],
'Topic2': {'descr': 'example.'}
},
'I.II - NextChapter':
{'Topic3': 'whatever.'}
},
'Part 2':{'II.I - FinalChapter': 'content.'}
}
}
Это круто и эффективно, и да, данные действительно хранятся в текстовом файле. Я просто хотел бы понять половину строк кода, которые вы написали, ха-ха
@FlynnRhodes Рад помочь! Я добавил больше объяснений в сообщение, однако весь код создает новый класс для каждого вхождения ключа данных. Данные файла хранятся в виде итератора, поэтому их легче определить, когда источник данных исчерпан.
Покажи свой код!