python - 如何解析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

解决方案:模块 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)