Jak parsować drzewa w nawiasie w pythonie?

Question

Potrzebuję pomocy w opracowaniu tego algorytmu, nad którym pracuję. Mam wejście drzewa w następującym formacie:

(głównej (AB (ABC) (CBA) (CD) (CDE) (FGH)))

Wygląda to następujące drzewo.

    Root 
        | 
       ____________ 
       AB   CD 
       |    | 
     __________   ___________ 
     ABC  CBA  CDE  FGH 

Co algorytm jest przypuszczać, aby się odczytać formatu w nawiasie oraz podać następujące dane wyjściowe:

Root -> AB CD 
AB -> ABC CBA 
CD -> CDE FGH 

To listy korzeń i jego dzieci i wszystkich innych rodziców, którzy mają dzieci. Nie jestem w stanie zrozumieć, jak zacząć to robić. Czy ktoś może mi pomóc w udzielaniu wskazówek lub przekazywaniu referencji lub linków?

Answer 1

rekurencyjna zejście parser jest prostą formą parsera które można analizować wiele gramatyk. Podczas gdy cała teoria analizowania jest zbyt duża, aby uzyskać odpowiedź przepełnienia stosu, najbardziej powszechne podejście do analizowania składa się z dwóch kroków: po pierwsze, tokenizacji, która wyodrębnia podciągi twojego łańcucha (tutaj, prawdopodobnie słowa takie jak "Root" i "ABC" lub nawiasy, takie jak '(' i ')'), a następnie parsowanie za pomocą funkcji rekursywnych.

Ten kod analizuje dane wejściowe (np. Przykład), tworząc tak zwane drzewo analizy, a także ma funkcję "show_children", która pobiera drzewo analizy i generuje widok podrzędny wyrażenia jako pytanie zadane.

import re 

class ParseError(Exception): 
    pass 

# Tokenize a string. 
# Tokens yielded are of the form (type, string) 
# Possible values for 'type' are '(', ')' and 'WORD' 
def tokenize(s): 
    toks = re.compile(' +|[A-Za-z]+|[()]') 
    for match in toks.finditer(s): 
     s = match.group(0) 
     if s[0] == ' ': 
      continue 
     if s[0] in '()': 
      yield (s, s) 
     else: 
      yield ('WORD', s) 


# Parse once we're inside an opening bracket. 
def parse_inner(toks): 
    ty, name = next(toks) 
    if ty != 'WORD': raise ParseError 
    children = [] 
    while True: 
     ty, s = next(toks) 
     if ty == '(': 
      children.append(parse_inner(toks)) 
     elif ty == ')': 
      return (name, children) 

# Parse this grammar: 
# ROOT ::= '(' INNER 
# INNER ::= WORD ROOT* ')' 
# WORD ::= [A-Za-z]+ 
def parse_root(toks): 
    ty, _ = next(toks) 
    if ty != '(': raise ParseError 
    return parse_inner(toks) 

def show_children(tree): 
    name, children = tree 
    if not children: return 
    print '%s -> %s' % (name, ' '.join(child[0] for child in children)) 
    for child in children: 
     show_children(child) 

example = '(Root (AB (ABC) (CBA)) (CD (CDE) (FGH)))' 
show_children(parse_root(tokenize(example))) 

Answer 2

Myślę, że najbardziej popularnym rozwiązaniem do parsowania w Pythonie jest PyParsing. PyParsing posiada gramatykę do analizowania wyrażeń S i powinieneś być w stanie go po prostu użyć. Omówione w tym StackOverflow odpowiedź:

Parsing S-Expressions in Python

Answer 3

Spróbuj tego:

def toTree(expression): 
    tree = dict() 
    msg ="" 
    stack = list() 
    for char in expression: 
     if(char == '('): 
      stack.append(msg) 
      msg = "" 
     elif char == ')': 
      parent = stack.pop() 
      if parent not in tree: 
       tree[parent] = list() 
      tree[parent].append(msg) 
      msg = parent 
     else: 
      msg += char 
    return tree 

expression = "(Root(AB(ABC)(CBA))(CD(CDE)(FGH)))" 
print toTree(expression) 

Zwraca słownika, gdzie korzeń można uzyskać dostęp za pomocą klawisza ''. Następnie można wykonać prosty plik BFS, aby wydrukować dane wyjściowe.

WYJŚCIE:

{ 
'' : ['Root'], 
'AB' : ['ABC', 'CBA'], 
'Root': ['AB', 'CD'], 
'CD' : ['CDE', 'FGH'] 
} 

Trzeba będzie wyeliminować wszystkie spacje w wyrażeniu przed rozpoczęciem lub ignorować charaters inrrelevant w ekspresji poprzez dodanie następujących jako pierwszy wiersz w za -lub:

if char == <IRRELEVANT CHARACTER>: 
    continue 

Powyższy kod będzie działać w czasie O (n), gdzie n jest długością wyrażenia.

EDIT

Tutaj funkcja druku:

def printTree(tree, node): 
    if node not in tree: 
     return 
    print '%s -> %s' % (node, ' '.join(child for child in tree[node])) 
    for child in tree[node]: 
     printTree(tree, child) 

pożądany wynik można osiągnąć za pomocą następujących:

expression = "(Root(AB(ABC)(CBA))(CD(CDE)(FGH)))" 
tree = toTree(expression) 
printTree(tree, tree[''][0]) 

wyjścia

Root -> AB CD 
AB -> ABC CBA 
CD -> CDE FGH 

EDIT

Zakładając nazwy węzłów nie są wyjątkowe, po prostu trzeba dać nowych nazw węzłów. Można to zrobić za pomocą:

def parseExpression(expression): 
    nodeMap = dict() 
    counter = 1 
    node = "" 
    retExp ="" 
    for char in expression: 
     if char == '(' or char == ')' : 
      if (len(node) > 0): 
       nodeMap[str(counter)] = node; 
       retExp += str(counter) 
       counter +=1 
      retExp += char 
      node ="" 
     elif char == ' ': continue 
     else : 
      node += char 
    return retExp,nodeMap 

Funkcja druku będzie teraz zmienić:

def printTree(tree, node, nodeMap): 
    if node not in tree: 
     return 
    print '%s -> %s' % (nodeMap[node], ' '.join(nodeMap[child] for child in tree[node])) 
    for child in tree[node]: 
     printTree(tree, child, nodeMap) 

Wyjście może być pobrany za pomocą:

expression = " (Root(SQ (VBZ) (NP (DT) (NN)) (VP (VB) (NP (NN)))))" 
expression, nodeMap = parseExpression(expression) 
tree = toTree(expression) 
printTree(tree, tree[''][0], nodeMap) 

wyjściowy:

Root -> SQ 
SQ -> VBZ NP VP 
NP -> DT NN 
VP -> VB NP 
NP -> NN