9

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

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

这看起来是下面的树。

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

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

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

它列出了根和它的孩子以及所有其他有孩子的父母。我无法理解如何开始，有人可以帮我提示或提供一些参考或链接吗？

4

4 回答 4

4

解决方案：Tree模块中的类nltk

（又名自然语言工具包）

进行实际解析

这是您的输入：

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根据需要使用）

于 2018-04-06T15:52:59.707 回答
1

递归下降解析器是一种简单形式的解析器，可以解析许多语法。虽然整个解析理论对于堆栈溢出答案来说太大了，但最常见的解析方法涉及两个步骤：首先，标记化，它提取字符串的子词（这里可能是像“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)))
于 2013-11-03T07:15:30.773 回答
1

尝试这个 ：

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 来打印输出。

输出 ：

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

在开始之前，您必须消除表达式中的所有空格，或者通过在 for-loop 的第一行添加以下内容来忽略表达式中不相关的字符：

if char == <IRRELEVANT CHARACTER>:
    continue

上面的代码将在 O(n) 时间内运行，其中 n 是表达式的长度。

编辑

这是打印功能：

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])

输出

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

编辑

假设节点名称不是唯一的，我们只需为节点指定新名称。这可以使用：

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
于 2013-11-03T14:14:05.490 回答
0

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

在 Python 中解析 S 表达式

于 2013-11-03T05:00:31.500 回答