Pythonで括弧内の木を解析するには？

Question

私が取り組んでいるこのアルゴリズムを開発する上で助けが必要です。

（ルート（AB（ABC）（CBA））（CD（CDE）（FGH）））

これはこれは、次のツリーになります。私は、次の形式で、ツリーの入力を持っています。これは、ルートとその子と子供を持っている他のすべての親をリスト

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

：アルゴリズムは中括弧のフォーマットを読み、次のような出力が得られていると仮定された何

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

。 私はこのことをどうやって始めるのか理解できません。誰かが私にヒントを与えたり、参考文献やリンクをくれたりできますか？

Answer 1

再帰下降構文解析は、多くの文法を解析できるパーザのシンプルな形です。パースの理論全体がスタックオーバーフローの答えには大きすぎますが、パースの最も一般的なアプローチは2つのステップから成ります：まず、文字列のサブワード（ここでは 'Root'や 'ABC' 、 '（'や '）'のような角括弧）を使用して再帰関数を使用して解析します。

このコードは、パーズツリーと呼ばれる入力を解析し、構文解析ツリーを取得する関数 'show_children'を持ち、質問の質問に応じて式の子ビューを生成します。

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

Pythonで解析するための最も一般的なソリューションはPyParsingだと思います。 PyParsingには、S式を解析するための文法が付いています。あなたはそれを使いこなせるはずです。このStackOverflowの答えで議論：

Parsing S-Expressions in Python

Answer 3

これを試してみてください：

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) 

それはルートがキー '' にアクセスすることができ辞書を返します。次に、簡単なBFSを実行して出力を印刷することができます。

OUTPUT：

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

あなたが開始する前に、式中のすべての空白を排除する必要がある、またはのために非常に最初の行として次を追加することによって、式のinrrelevantのcharatersを無視します-loop：

if char == <IRRELEVANT CHARACTER>: 
    continue 

上記のコードは、O（n）時間（nは式の長さ）で実行されます。ここ

EDIT

は、印刷機能である：

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) 

所望の出力は、以下により達成することができる。

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

出力

ノード名を想定し

EDIT

は一意ではありません、私たちはただのノードに新しい名前を与える必要があります。これは、使用して行うことができます。

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 

印刷機能は、今に変更されます：

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) 

出力を使用することによって得ることができる。

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

出力：

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