Древовидная структура в виде строки - как сопоставить вложенные скобки? - PullRequest
Новая
       13

Древовидная структура в виде строки - как сопоставить вложенные скобки?

2 голосов
/ 07 июля 2011

У меня настроена древовидная структура, и я хочу сохранить ее в / прочитать из строки с минимальным количеством текста (поэтому сериализация 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 ]

3 голосов
/ 07 июля 2011

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

Примерно так (псевдокод): 

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) просматривает следующий символ и возвращает значение истины, указывающее, соответствует ли оно.
...