Сплит «Вложенная» строка по скобкам во вложенный список

Question

У меня есть строковое представление дерева. Я хотел бы преобразовать его во вложенный список. Есть ли способ сделать это рекурсивно, так что я получаю вложенные списки?

Пример строка выглядит следующим образом:

(TOP (S (NP (PRP I)) (VP (VBP need) (NP (NP (DT a) (NN flight)) (PP 
(IN from) (NP (NNP Atlanta))) (PP (TO to) (NP (NP (NNP Charlotte)) (NP 
(NNP North) (NNP Carolina)))) (NP (JJ next) (NNP Monday)))))) 

До сих пор я ниже, но это не дает мне то, что я ищу, вообще.

import sys 
import re 

for tree_str in sys.stdin: 
    print [", ".join(x.split()) for x in re.split(r'[()]',tree_str) if x.strip()] 

Answer 1

Мой подход был бы что-то вроде этого:

import re 


def make_tree(data): 
    items = re.findall(r"\(|\)|\w+", data) 

    def req(index): 
     result = [] 
     item = items[index] 
     while item != ")": 
      if item == "(": 
       subtree, index = req(index + 1) 
       result.append(subtree) 
      else: 
       result.append(item) 
      index += 1 
      item = items[index] 
     return result, index 

    return req(1)[0] 


string = "(TOP (S (NP (PRP I))..." # omitted for readability 
tree = make_tree(string) 

print(tree) 
# Output: ['TOP', ['S', ['NP', ['PRP', 'I']]... 

Answer 2

Немного хакерский, но любопытный делает трюк в любом случае :) У вас определенно есть ваши вложенные списки.

import re 
import ast 

input = "(TOP (S (NP (PRP I)) (VP (VBP need) (NP (NP (DT a) (NN flight)) (PP (IN from) (NP (NNP Atlanta))) (PP (TO to) (NP (NP (NNP Charlotte)) (NP (NNP North) (NNP Carolina)))) (NP (JJ next) (NNP Monday))))))" 

# replaces all brackets by square brackets 
# and adds commas when needed 
input = input.replace("(", "[")\ 
      .replace(")", "]")\ 
      .replace("] [", "], [") 

# places all the words between double quotes 
# and appends a comma after each 
input = re.sub(r'(\w+)', r'"\1",', input) 

# safely evaluates the resulting string 
output = ast.literal_eval(input) 

print(output) 
print(type(output)) 

# ['TOP', ['S', ['NP', ['PRP', 'I']], ['VP', ['VBP', 'need'], ['NP', ['NP', ['DT', 'a'], ['NN', 'flight']], ['PP', ['IN', 'from'], ['NP', ['NNP', 'Atlanta']]], ['PP', ['TO', 'to'], ['NP', ['NP', ['NNP', 'Charlotte']], ['NP', ['NNP', 'North'], ['NNP', 'Carolina']]]], ['NP', ['JJ', 'next'], ['NNP', 'Monday']]]]]] 
# <class 'list'> 

Примечание: по соображениям безопасности, ast.literal_eval() выдает ошибку, если выражение содержит операторы или какой-то логики, так что вы можете использовать его без необходимости проверки на наличие вредоносного кода первым.

Answer 3

Это называется "разбор". Один генератор парсера для Python, кажется, Yapps. Документация Yapps даже shows как написать синтаксический анализатор Lisp, из которых ваше приложение кажется просто подмножеством.

Подмножество, что вам нужно, кажется:

parser Sublisp: 
    ignore:  '\\s+' 
    token ID: '[-+*/!@%^&=.a-zA-Z0-9_]+' 

    rule expr: ID  {{ return ('id', ID) }} 
       | list {{ return list }} 
    rule list: "\\(" {{ result = [] }} 
       (expr {{ result.append(expr) }} 
       )* 
       "\\)" {{ return result }} 

После компиляции, это будет разбирать вашу строку дерева кортежей («ид», «Foo»). Чтобы получить дерево в желаемой форме, вы можете либо изменить сгенерированный код на Python (это вполне читаемо), либо впоследствии преобразовать дерево.

Answer 4

Дать простой синтаксический анализатор для S-Expressions не так уж трудно:

import pprint 
import re 

pattern = r''' 
    (?P<open_paren> \() | 
    (?P<close_paren> \)) | 
    (?P<word> \w+) | 
    (?P<whitespace> \s+) | 
    (?P<eof> $) | 
    (?P<error> \S) 
''' 

scan = re.compile(pattern=pattern, flags=re.VERBOSE).finditer 

text = ''' 
(TOP (S (NP (PRP I)) (VP (VBP need) (NP (NP (DT a) (NN flight)) 
(PP (IN from) (NP (NNP Atlanta))) (PP (TO to) (NP (NP (NNP Charlotte)) 
(NP (NNP North) (NNP Carolina)))) (NP (JJ next) (NNP Monday)))))) 
''' 

ERR_MSG = 'input string kaputt!!' 

stack = [[]] 

for match in scan(text): 
    token_type = match.lastgroup 
    token = match.group(0) 
    if token_type == 'open_paren': 
     stack.append([]) 
    elif token_type == 'close_paren': 
     top = stack.pop() 
     stack[-1].append(top) 
    elif token_type == 'word': 
     stack[-1].append(token) 
    elif token_type == 'whitespace': 
     pass 
    elif token_type == 'eof': 
     break 
    else: 
     raise Exception(ERR_MSG) 

if 1 == len(stack) == len(stack[0]): 
    pprint.pprint(stack[0][0]) 
else: 
    raise Exception(ERR_MSG) 

Результат:

['TOP', 
['S', 
    ['NP', ['PRP', 'I']], 
    ['VP', 
    ['VBP', 'need'], 
    ['NP', 
    ['NP', ['DT', 'a'], ['NN', 'flight']], 
    ['PP', ['IN', 'from'], ['NP', ['NNP', 'Atlanta']]], 
    ['PP', 
    ['TO', 'to'], 
    ['NP', 
     ['NP', ['NNP', 'Charlotte']], 
     ['NP', ['NNP', 'North'], ['NNP', 'Carolina']]]], 
    ['NP', ['JJ', 'next'], ['NNP', 'Monday']]]]]]