Как я могу разобрать строку кода и построить иерархический массив на основе {и} в строке

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 #):

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 намного лучше, чем использование массива со слабым типом (даже если вы используете слабо типизированныйязык).И нет необходимости включать фигурные скобки в результат.

Если вы хотите сделать что-то более сложное, я бы рекомендовал использовать некоторую библиотеку синтаксического анализатора.

Если строка может быть очень длинной ивы читаете его из файла или сети, возможно, вы захотите использовать некоторую форму потока вместо обычной строки.

Answer 2

Вы не очень разборчивы в языке, поэтому мне довольно любопытно, почему вы этого хотите. Вот код, который должен делать то, что вы хотите в 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();
}