如何从字符串构造树？

Question

输入字符串：'(SBARQ (WHADVP (WRB Where)) (VBZ is) (NP (DT the) (NN cow)))'

这是一棵树，看起来像：

目的是构建一个树节点，其中标签作为节点，其所有覆盖字符串作为值

class TreeNode:
   def __init__(self):
        self.childre=[]
        self.label=""
        self.text=""

这是树的预期外观：

SBARQ: "Where is the cow"
WHADVP: "Where"
WRB: "Where"
VBZ: "is"
NP: "the cow"
DT: "the"
NN: "cow"

Answer 1

可以使用递归同时创建树和聚合文本

我想：

• 允许使用标签参数调用构造函数
• 将从字符串创建树的函数定义为类上的静态方法
• 使用正则表达式标记输入
• 添加一些assert语句，当输入格式不符合预期时，这些语句将显示可读的异常消息
• 在类上定义__iter__，以便可以轻松地迭代树中存在的所有节点

import re

class TreeNode:
    def __init__(self, label=""):
        self.children = []
        self.label = label
        self.text = ""

    @staticmethod
    def create_from_string(text):
        tokens = re.finditer(r"[()]|[^\s()]+", text)
        match = next(tokens)
        token = match.group()
        assert token == "(", "Expected '(' at {}, but got '{}'".format(match.start(), token)

        def recur():
            node = None
            while True:
                match = next(tokens)
                i = match.start()
                token = match.group()
                if token == ")":
                    assert node, "Expected label at {}, but got ')'".format(i)
                    assert node.text, "Expected text at {}, but got ')'".format(i)
                    return node
                if token == "(":
                    assert node, "Expected label at {}, but got '('".format(i)
                    child = recur()
                    node.children.append(child)
                    token = child.text
                if node:
                    node.text = "{} {}".format(node.text, token).lstrip() 
                else:
                    node = TreeNode(token)

        return recur()

    def __iter__(self):
        def nodes():
            yield self
            for child in self.children:
                yield from child
        return nodes()

以下是如何将上述内容用于您的具体示例：

s = '(SBARQ (WHADVP (WRB Where)) (VBZ is) (NP (DT the) (NN cow)))'
tree = TreeNode.create_from_string(s)
for node in tree:
    print("{}: {}".format(node.label, node.text))

后一个代码将输出：

SBARQ: Where is the cow
WHADVP: Where
WRB: Where
VBZ: is
NP: the cow
DT: the
NN: cow

Answer 2

最主要的是识别孩子。我将尝试解释我的代码：

class TreeNode:
    def __init__(self, string):
        
        self.im_leaf = string[0] != '('
        self.children = []

        if not self.im_leaf:
            first_space_index = string.index(" ")
            self.label = string[1:first_space_index]
            
            string = string[first_space_index + 1 : -1] #rest of the tree
            for node in self.split(string):
                self.children.append(TreeNode(node))
        else:
            self.label = string

        self.text = self.calculate_text()

    def calculate_text(self):
        if self.im_leaf:
            return self.label + ' '
        
        text = ''
        for node in self.children:
            text += node.calculate_text()

        return text


    def split(self, string):
        
        splitted = []
        pair_parenthesis = 0 
        index = 0

        for i in range(len(string)):
            char = string[i]

            if char == '(':
                pair_parenthesis += 1
            elif char == ')':
                pair_parenthesis -= 1
                if pair_parenthesis == 0:

                    new_node = string[index:i+1]
                    if new_node[0] == ' ':
                        new_node = new_node[1:]
                    splitted.append(new_node)
                    index = i + 1

        if len(splitted) == 0:  
            splitted = [string]
        
        return splitted

首先，在__init__中，我识别给定字符串是否描述了由第一个字符确定的叶，如果它不是“开括号”（'('），则当前字符串描述了叶，例如"cow"或Where；与“非叶字符串”不同，例如"(NP (DT the) (NN cow))"

如果string描述一个叶，那么label = string，否则label是第一个括号（总是在第一个位置）和第一个空白之间的子字符串。另外，在后一种情况下，有必要识别不同的分支，这是通过方法split完成的。然后，递归地识别children

split方法通过计算开括号和闭括号来识别分支。请注意"(WHADVP (WRB Where)) (VBZ is) (NP (DT the) (NN cow))"中的第一个分支是(WHADVP (WRB Where))，也就是说，当代码中第一次开括号的数量等于闭括号的数量时（这个差异存储在pair_parenthesis）。第二个和第三个分支也是如此。如果分支只有一个子级，例如"(WRB Where)"，则将使用字符串"Where"调用该方法，在这些情况下，该方法返回"[Where]"

最后，使用方法calculate_text分配text，该方法基本上通过树进行递归调用来搜索叶子。如果节点是叶，则其标签将添加到text

现在进行一些测试：

test_tree = TreeNode('(SBARQ (WHADVP (WRB Where)) (VBZ is) (NP (DT the) (NN cow)))')

print(test_tree.label)
#SBARQ

print(test_tree.text)
#Where is the cow 

print(test_tree.children[0].text) #text from the "WHADVP" node
#Where

如果有什么不清楚的地方，请告诉我