树结构作为字符串 - 如何匹配嵌套的大括号? [英] Tree structure as string - how to match nested braces?

问题描述

我设置了一个树结构，并希望使用最少的文本将其保存为/从字符串中读取它(因此 XML 序列化已结束).我为此设置了一个简单的(或者我认为的)结构，但无法弄清楚如何读取它，所以我的结构很可能不得不改变.让我用一个例子来演示.

I have a tree structure set up and wish to save it to / read it from a string, with a minimal amount of text (so XML serialization is out). I set up a simple (or so I thought) structure for this, but can't figure out how to read it in, so my structure will most likely have to change. Let me demonstrate with an example.

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

My tree is made up of X,Y coordinates, like in the following example:

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

当我运行我的算法将这棵树变成字符串时，我得到以下输出:

When I run my algorithm to turn this tree into a string, I get the following output:

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

这里是我正在使用的代码:

And here it the code I'm using:

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();
}

这很好用，但现在我无法将字符串解析回我的树结构.我可以将子字符串放到第一个开放大括号并将其转换为节点的值，但我不确定如何将字符串的其余部分拆分为子字符串.有什么方法可以轻松找到左大括号，然后找到它的右大括号?我研究了一些复杂的正则表达式，但无法正常工作并很快就完全丢失了.

That works great, but now I can't parse the string back into my tree structure. I can get the substring up to the first open brace and convert that to the node's value, but I'm unsure how to split the rest of the string into children. Is there any way I can easily find an opening brace, and then find it's closing brace? I've looked into some complicated regex stuff that I couldn't get working properly and quickly became completely lost.

有人有什么想法吗?

这是我到目前为止的代码:

Here's the code I have so far:

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())，即我被卡住的地方.

The problem I'm having, is that I will get a string that has to be split up into siblings. In the example above, c,d and e,f are siblings, represented in the form (c,d()e,f(g,h()i,j()k,l())). I need to split this string into c,d() and e,f(g,h()i,j()k,l()), which is where I'm stuck.

推荐答案

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

You can parse a string like that using a stack and 2 local variables. The stack would not be necessary if you serialized the tree using a breadth first traversal rather than depth first (btw it does not have to be recursive in either case).

递归解决方案仅利用调用堆栈并可能导致堆栈溢出 - 请参阅此处以获得更好的解释 为什么这不是最好的方法.

The recursive solution just utilizes the call stack and could result in a stack overflow - see here for a better explanation of why that's not the best way.

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);
    }
}

这篇关于树结构作为字符串 - 如何匹配嵌套的大括号?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！