作为字符串的树结构-如何匹配嵌套的大括号

本文关键字：嵌套 何匹配 字符串 结构 | 更新日期: 2023-09-27 18:01:30

我设置了一个树形结构，希望将其保存为/从字符串中读取它，并使用最少的文本(因此XML序列化不存在)。我为此设置了一个简单的(或我认为的)结构，但不知道如何读取它，所以我的结构很可能不得不改变。让我用一个例子来说明。

我的树由X,Y坐标组成，如下例所示:

[a,b]
  |-----|
[c,d] [e,f]
        |-----|-----|
      [g,h] [i,j] [k,l]

当我运行算法将此树转换为字符串时，我得到以下输出:

a,b(c,d()e,f(g,h()i,j()k,l()))

这里是我使用的代码:

public string SerializeMe()
{
    StringBuilder ret = new StringBuilder(this.Value.ToString())
    ret.Append("(");
    foreach (SimpleTreeNode<T> child in _Children)
    {
        ret.Append(child.SerializeMe());
    }
    ret.Append(")");
    return ret.ToString();
}

工作得很好，但是现在我无法将字符串解析回树结构。我可以获得子字符串到第一个开括号并将其转换为节点的值，但我不确定如何将字符串的其余部分拆分为子字符串。有什么方法可以让我很容易地找到一个开始括号，然后找到它的结束括号?我研究了一些复杂的正则表达式的东西，我不能正常工作，很快就完全迷失了。

有人有什么想法吗?

编辑:
下面是我到目前为止的代码:

public static SimpleTreeNode<SPoint> ParsePointTree(string input)
{
    //if the input string is empty, there is no node here. Return null.
    if (string.IsNullOrEmpty(input)) return null;
    else
    {
        //get the value from the first part of the string
        string valString = input.Substring(0, input.IndexOf('('));
        SPoint value = (SPoint)valString;
        SimpleTreeNode<SPoint> node = new SimpleTreeNode<SPoint>(value);
        //now we have the child nodes enclosed in brackets
        string innerstring = input.Substring(input.IndexOf('('));
        List<string> children = new List<string>();
        // how do we split innerstring into siblings?? //
        foreach (string child in children)
        {
            node.Children.Add(SimpleTreeNode<SPoint>.ParsePointTree(child));
        }
        return node;
    }
}

我遇到的问题是，我将得到一个必须拆分为兄弟姐妹的字符串。在上面的例子中，c,d和e,f是兄弟，用(c,d()e,f(g,h()i,j()k,l()))的形式表示。我需要将此字符串拆分为c,d()和e,f(g,h()i,j()k,l())，这就是我卡住的地方。

作为字符串的树结构-如何匹配嵌套的大括号

您可以使用堆栈和2个局部变量解析这样的字符串。如果您使用宽度优先遍历而不是深度优先来序列化树，则不需要堆栈(顺便说一句，在这两种情况下它都不必是递归的)。

递归解决方案只是利用调用堆栈，并可能导致堆栈溢出——请参阅此处，以更好地解释为什么这不是最好的方法。

foreach (char c in "a(c()e(g()i()k()))")
{
    if (c == '(')
    {
        Stack.Push(Parent);
        Parent = Child;
    }
    else if (c == ')')
    {
        Child = Parent;
        Parent = Stack.Pop();
    }
    else
    {
        Child = new SimpleTreeNode() { Value = c };
        Parent.Children.Add(Child);
    }
}

像这样(伪代码):

function parse() =
    label = read_until('(',')');
    read_char('(')
    children = []
    while not peek_char(')') do
        child = parse()
        children.add(child)
    read_char(')')
    return new Node(label,children)
  • read_until(...)读取到给定字符，但不包括给定字符。
  • read_char(c)读取一个字符，如果不匹配则抛出错误。
  • peek_char(c)查看下一个字符，并返回一个指示是否匹配的真值。
相关文章：