如何从字符串解析二进制树？

Question

我想编写一个BinaryTree解析器。我不知道如何解决这个问题。我尝试过递归地使用正则表达式，但找不到好的资源。我的目标是：

• BinaryTree.from_string("('a') 'b' ('c')")-->BinaryTree("a", "b", "c")
• BinaryTree.from_string("")-->None
• BinaryTree.from_string("() ()")-->BinaryTree(None, None, None)
• BinaryTree.from_string("((1) 2 (3)) 4 (5)")-->BinaryTree(BinaryTree(1, 2, 3), 4, 5)

以下是一些源代码：

class BinaryTree:
    def __init__(self, left=None, name=None, right=None):
        self.left = left
        self.name = name
        self.right = right

    def __str__(self):
        return f"({self.left}) {self.name} ({self.right})"

    def __repr__(self):
        return f"BinaryTree({repr(self.left)}, {repr(self.name)}, {repr(self.right)})"

    def __len__(self):
        if self.name is not None:
            output = 1
        else:
            output = 0
        if self.left is not None:
            output += len(self.left)
        if self.right is not None:
            output += len(self.right)
        return output

    @staticmethod
    def from_string(string):
        # "(x) y (z)" --> BinaryTree("x", "y", "z")
        # "((a) b (c)) y (z)" --> BinaryTree(BinaryTree("a", "b", "c"), "y", "z")
        # "" --> None
        # ()  () --> BinaryTree("", "", "")
        pass

Answer 1

您可以使用正则表达式，但只能将其用于标记输入，即它应将所有括号作为单独的匹配项进行匹配，并匹配带引号或不带引号的文字。必须注意在引用的子字符串中支持反斜杠转义

要将带引号的字符串和数字转换为相应的Python数据类型值，可以使用ast.literal_eval。当然，如果输入格式是一个有效的Python表达式（使用逗号分隔符等），则可以将解析完全留给ast.literal_eval。但由于情况并非如此，您必须对输入进行标记化并对标记进行迭代

因此，请输入以下内容：

import re
import ast

然后：

    @staticmethod
    def from_string(string):
        tokens = re.finditer(r"[()]|'(?:\\.|[^'])*'|[^\s()]+|$", string)

        def format(token):
            return f"'{token}'" if token else "end of input"

        def take(end, expect=None, forbid=None):
            token = next(tokens).group(0)
            if expect is not None and token != expect:
                raise ValueError("Expected {}, got {}".format(format(expect), format(token)))
            if end != "" and token == "" or token == forbid:
                raise ValueError("Unexpected {}".format(format(token)))
            if token not in ("(", ")", ""):
                token = ast.literal_eval(token)
            return token

        def recur(end=")"):
            token = take(end)
            if token == end:  # it is an empty leaf
                return None  
            if token != "(":  # it is a leaf
                take(end, end)
                return token
            # It is a (left)-name-(right) sequence:
            left = recur()
            name = None
            token = take(end, None, end)
            if token != "(":
                name = token
                take(end, "(")
            right = recur()
            take(end, end)
            return BinaryTree(left, name, right)

        return recur("")

Answer 2

首先，我认为您需要放弃正则表达式的概念，专注于简单的括号匹配。这里有一个非常简单的表达式语法。我不想重复这样一个旅行频繁的练习，而是简单地指导您研究如何用括号解析二叉树表达式

基本表达式是

left root right

其中left和right中的每一个

• 子树（第一个字符是左括号）
• 叶节点标签（第一个字符是其他字符）
• 空（空白）

请注意，您有一些歧义。例如，给定a b，结果树是(a, b, None)、(None, a, b)还是错误

在任何情况下，如果您专注于简单的字符串处理，您应该能够在没有外部包的情况下完成这项工作：

• 查找第一个左括号及其匹配的右括号
• 在之后的字符串中，再次查找左右对
• 如果在第一个左paren之前有任何内容，那么它必须是左边的叶节点和根的节点标签 无论哪种方式，中间必须有根节点（除非这是退化树）。<李>
• 在您进行的每个paren匹配中重复出现

你能从那里拿走吗