如何解析代码字符串，并根据字符串中的{和}构建分层数组

Question

我有一个类似代码的字符串，如下所示：

a
{
    bcd
    {
        ef
        {
            gh
            {
                i
            }
            j
        }
    }
    k
    {
        lmn
        {
            op
        }
        qr
        {
            st
        }
        uv
        {
            wx
        }
        y
    }
    z
}

我希望解析这个字符串，这样我就可以从这段代码中创建一个分层数组，其中每个树都是基于{创建的，而树在}处结束。

该数组将如下所示：

[
    "a",

    "{",

    [

        "bcd",

        "{",

        [
            "ef",

            "{",

            [
                "gh",

                "{",

                [
                    "i"
                ],

                "}",

                "j"
            ],

            "}"
        ],

        "}",

        "k",

        "{",

        [
            "lmn",
            "{",
            [
                "op"
            ],

            "}",
            "qr",

            "{",

            [
                "st"
            ],

            "}",

            "uv",

            "{",
            [
                "wx"
            ],

            "}",
            "y"
        ],

        "}",
        "z"
    ],

"}"
]

有没有人能帮我了解一下这个算法？

你也可以用Java/C#/PHP/VB.NET/JavaScript/ActionScript中的任何一种语言给我传一个代码。

Answer 1

你对语言并不是很挑剔，所以我很好奇你为什么要这样做。下面是一些可以在C#中执行您想要的操作的代码：

public static object[] ParseSpecial(string s)
{
    string dummy = "";
    Stack<List<object>> result = new Stack<List<object>>();
    result.Push(new List<object>());
    foreach (char character in s)
    {
        switch (character)
        {
            case '{':
                if (dummy.Length > 0)
                    result.Peek().Add(dummy);
                dummy = "";

                result.Peek().Add("{");
                result.Push(new List<object>());
                break;

            case '}':
                if (dummy.Length > 0)
                    result.Peek().Add(dummy);
                dummy = "";

                List<object> temp = result.Pop();
                result.Peek().Add(temp.ToArray());
                result.Peek().Add("}");
                break;

            default:
                dummy += character;
                break;
        }
    }

    if (dummy.Length > 0)
        result.Peek().Add(dummy);

    return result.Peek().ToArray();
}

Answer 2

如果这就是你想要做的，你可以这样写它(C#)：

class Node
{
    public string Name { get; private set; }
    public IEnumerable<Node> Children { get; private set; }

    public Node(string name, IEnumerable<Node> children)
    {
        Name = name;
        Children = children;
    }
}

class Parser
{
    public Node Parse(string s)
    {
        return Parse(s.Split(new char[0], StringSplitOptions.RemoveEmptyEntries));
    }

    public Node Parse(IEnumerable<string> tokens)
    {
        using (var enumerator = tokens.GetEnumerator())
        {
            enumerator.MoveNext(); // move to first token
            return Parse(enumerator);
        }
    }

    Node Parse(IEnumerator<string> enumerator)
    {
        string name = enumerator.Current;
        enumerator.MoveNext();
        var children = new List<Node>();
        if (enumerator.Current == "{")
        {
            enumerator.MoveNext();
            while (enumerator.Current != "}")
            {
                children.Add(Parse(enumerator));
            }
            enumerator.MoveNext();
        }
        return new Node(name, children);
    }
}

这段代码不检查MoveNext()的返回值，这意味着它将在无效输入上产生奇怪的结果(包括无限循环的可能性)。

它还要求标记由空格分隔。因此，像a{b{c}}这样的字符串将被解析为一个名称为a{b{c}}的节点。

创建特殊类型的Node比使用弱类型数组要好得多(即使您使用的是弱类型语言)。并且不需要在结果中包含大括号。

如果你想做一些更复杂的事情，我建议你使用一些解析器库。

如果字符串可能很长，并且您正在从文件或网络读取它，那么您可能希望使用某种形式的流，而不是普通的字符串。