如何解析python中的插入树？

Question

我需要帮助开发我正在研究的算法。我有一个树的输入，格式如下：

（根（AB（ABC）（CBA））（CD（CDE）（FGH）））

这看起来像下面的树。

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

算法假设是读取括号格式并给出以下输出：

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

它列出了根及其子代以及所有其他有子代的父代。 我不知道如何开始这个，有人能帮我给我提示或给一些参考或链接吗？

Answer 1

我认为Python中最流行的解析解决方案是PyParsing。PyParsing附带了用于解析S表达式的语法，您应该能够直接使用它。在这个StackOverflow答案中讨论过：

Parsing S-Expressions in Python

Answer 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 3

解决方案：来自模块nltk的Tree类

（又名自然语言工具包）

进行实际分析

这是您的输入：

input = '( Root ( AB ( ABC ) ( CBA ) ) ( CD ( CDE ) ( FGH ) ) )'

你可以简单地分析它：

from nltk import Tree
t = Tree.fromstring(input)

玩解析树

>>> t.label()
'Root'
>>> len(t)
2
>>> t[0]
Tree('AB', [Tree('ABC', []), Tree('CBA', [])])
>>> t[1]
Tree('CD', [Tree('CDE', []), Tree('FGH', [])])
>>> t[0][0]
Tree('ABC', [])
>>> t[0][1]
Tree('CBA', [])
>>> t[1][0]
Tree('CDE', [])
>>> t[1][1]
Tree('FGH', [])

如您所见，您可以将每个节点视为子树列表。

漂亮地打印树

>>> t.pretty_print()
            Root            
      _______|________       
     AB               CD    
  ___|___          ___|___   
ABC     CBA      CDE     FGH
 |       |        |       |  
...     ...      ...     ...

获得想要的输出

from sys import stdout

def showtree(t):
    if (len(t) == 0):
        return
    stdout.write(t.label() + ' ->')
    for c in t:
        stdout.write(' ' + c.label())
    stdout.write('\n')
    for c in t:
        showtree(c)

用法：

>>> showtree(t)
Root -> AB CD
AB -> ABC CBA
CD -> CDE FGH

安装模块

pip install nltk

（如果需要，请使用sudo）