Разбор текста для создания древовидной структуры данных

Question

Допустим, я читаю строку из файла:

{Parent{{ChildA}{ChildB}}}

Более сложный пример:

{Parent{{ChildA{ChildC}{ChildD}}{ChildB{ChildE}{ChildF}}}}

Какая грамматика используется для построения дерева.

Любое имя в {} скобках является узлом, и если внутри этой скобки есть другие узлы (скобки), эти узлы являются дочерними.

Я могу проанализировать первый конкретный пример, используя счетчик, но только для того, чтобы найти текстовые имена узлов. Как я могу разобрать это, чтобы я мог определить, какие узлы являются дочерними по отношению друг к другу? Кажется, я не могу сосредоточиться на коде, который буду использовать. У меня есть ощущение, что я бы использовал рекурсию.

Буду признателен за любую помощь или совет.

C ++ является предпочтительным.

Большое спасибо.

Answer 1

Вам придется отслеживать текущее вложение.Для этого вы можете использовать стек.

Каждый раз, когда вы сталкиваетесь с { (за которым следует имя узла), вы знаете, что это начало нового узла.Этот новый узел является дочерним по отношению к текущему узлу.

Каждый раз, когда вы сталкиваетесь с }, вы знаете, что текущий узел завершен, а это означает, что вы должны сообщить своей программе, что текущий узел теперь заменен на родителя текущего узла.

Пример:

{A{B{C}{D}{E}}{F{G}{H}}}  Stack:
^

{A{B{C}{D}{E}}{F{G}{H}}}  Stack: A // A is root
 ^

{A{B{C}{D}{E}}{F{G}{H}}}  Stack: A, B // B is child of A
   ^

{A{B{C}{D}{E}}{F{G}{H}}}  Stack: A, B, C // C is child of B
     ^

{A{B{C}{D}{E}}{F{G}{H}}}  Stack: A, B, // C has no child, C done
      ^

{A{B{C}{D}{E}}{F{G}{H}}}  Stack: A, B, D // D is child of B
        ^

{A{B{C}{D}{E}}{F{G}{H}}}  Stack: A, B, 
         ^

{A{B{C}{D}{E}}{F{G}{H}}}  Stack: A, B, E // E child of B
           ^

{A{B{C}{D}{E}}{F{G}{H}}}  Stack: A, B, 
            ^

{A{B{C}{D}{E}}{F{G}{H}}}  Stack: A, // B has no more children, B done
             ^

{A{B{C}{D}{E}}{F{G}{H}}}  Stack: A, F // F child of A
               ^

{A{B{C}{D}{E}}{F{G}{H}}}  Stack: A, F, G // G child of F
                 ^

{A{B{C}{D}{E}}{F{G}{H}}}  Stack: A, F, 
                  ^

{A{B{C}{D}{E}}{F{G}{H}}}  Stack: A, F, H
                    ^

{A{B{C}{D}{E}}{F{G}{H}}}  Stack: A, F, 
                     ^

{A{B{C}{D}{E}}{F{G}{H}}}  Stack: A, 
                      ^

{A{B{C}{D}{E}}{F{G}{H}}}  Stack: 
                       ^

DONE.

Answer 2

Испортить удовольствие от ответа, который вы все равно не сможете использовать, если это домашнее задание:

Минимальная реализация с Boost Spirit Qi:

#include <boost/spirit/include/qi.hpp>
namespace qi = boost::spirit::qi;

typedef boost::make_recursive_variant<
    std::vector<boost::recursive_variant_>, 
    std::string>::type ast_t;

void dump(const ast_t&);

// adhoc parser rule:
static const qi::rule<std::string::iterator, ast_t()> node = 
    '{' >> *node >> '}' | +~qi::char_("{}");

int main()
{
     std::string input = "{Parent{{ChildA{ChildC}{ChildD}}{ChildB{ChildE}{ChildF}}}}";
     std::string::iterator f(input.begin()), l(input.end());

     ast_t tree;
     if (qi::parse(f, l, node, tree))
         dump(tree);
     else
         std::cerr << "Unparsed: " << std::string(f, l) << std::endl;
}

Реализация dump вызывает сожалениепочти эквивалентное количество кода:)

---

Будет напечатано:

{
    Parent
    {
        {
            ChildA
            {
                ChildC
            }
            {
                ChildD
            }
        }
        {
            ChildB
            {
                ChildE
            }
            {
                ChildF
            }
        }
    }
}

_{Вот определение dump(const ast_t&):}

struct dump_visitor : boost::static_visitor<>
{
    dump_visitor(int indent=0) : _indent(indent) {}

    void operator()(const std::string& s) const { print(s); }

    template <class V>
        void operator()(const V& vec) const
    {
        print("{");
        for(typename V::const_iterator it=vec.begin(); it!=vec.end(); it++)
            boost::apply_visitor(dump_visitor(_indent+1), *it);
        print("}");
    }

  private:
    template <typename T> void print(const T& v) const 
      { std::cout << std::string(_indent*4, ' ') << v << std::endl; }
    int _indent;
};

void dump(const ast_t& tree)
{
    boost::apply_visitor(dump_visitor(), tree);
}

Answer 3

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

Каждый раз, когда вы видите{ вы создаете новый узел с данными после него и помещаете его в стек.

Каждый раз, когда вы видите }, вы вытаскиваете последний узел из стека и добавляете его в свойформа дерева.

Еще одна вещь, которая понадобится вам для этого подхода, - указатель на узел, мы назовем его currentNode, чтобы мы могли реализовать фактическую иерархию.Для начала currentNode будет нулевым;при первом извлечении узла из стека вы помещаете этот узел в currentNode.В противном случае, когда вы извлекаете значение, мы знаем, что у нас есть оба потомка следующего узла в стеке.

Я позволю вам работать с ним оттуда, но если вам понадобится больше, я буду поддерживать.

Answer 4

Грамматика у вас относительно простая.

На основании ваших примеров узлы могут быть объявлены одним из двух способов:

{nodename}

что является простым и

{nodename{childnodes}}

сложный

Теперь, чтобы превратить это в более формальную грамматику, мы сначала напишем составные части:

"{" nodename "}"
"{" nodename "{" childnodes "}" "}"

Тогда мы можем определить грамматику (нетерминалы пишутся с большой буквы)

Node :: = "{" Nodename "}" | "{" Nodename "{" Childnodes "}" Nodename :: = хотя бы одна буква Childnodes :: = один или несколько узлов

Стандартный способ превратить его в парсер (при условии, что вы должны написать его вручную, что вы и сделаете правильно, потому что он настолько мал), - написать метод, который может анализировать каждый из нетерминалов (что вы видите на слева от знака: ==).

Единственная сложная проблема заключается в том, что вам нужно написать функцию Nodename, чтобы проверить, есть ли "{" (в этом случае у узла есть дочерний элемент) или "}" (в этом случае у него нет дочернего элемента) ) после конца имени узла.

Также я позволил себе не записывать все возможные строки ascii как Nodename.

Answer 5

Каждый раз, когда вы находите "{", затем добавляете дочерний элемент к родительскому элементу, а затем каждый раз, когда вы находите "}", задайте текущее дерево как родительское дерево.

    public class Tree 
    { 
       public Tree Parent { get; set; }
       public string Value { get; set; }
       public List<Tree> Children { get; set; }
    }

    public Tree Parsing()
    {
        string rawString = this._rawData;
        Tree parent = new Tree { Parent = null,Value = "",Children = new List<Tree>()};
        Tree child = parent;

         foreach (char c in rawString)
          {
             if (c == '{')
             {
                child = new Tree { Parent = child, Value = string.Empty, Children = new List<Tree>() };
                child.Parent.Children.Add(child);
             }
             else if (c == '}')
             {
               child = new Tree { Parent = child.Parent.Parent, Value = string.Empty, Children = new List<Tree>() };
               if (child.Parent != null)
               {
                   child.Parent.Children.Add(child);
                }
              }
             else
             {
                   child.Value += c;
             }
         }

          return parent;
 }

public void RenderTree(Tree tree, string level)
{
    if (tree.Value.Length > 0)
         Console.WriteLine(level + tree.Value);

    foreach (Tree t in tree.Children)
    {
        RenderTree(t, level + "  ");
    }
}

Answer 6

Представьте, что это что-то вроде этого (даже если оно является линейным по отношению к файлу, из которого вы читаете, просто попробуйте визуализировать его таким образом)

{
 Parent
  {
    {
     ChildA
       {
         ChildC
       }
       {
        ChildD
       } 
     }
     {
      ChildB
       {
         ChildE
       }
       {
         ChildF
       }
     }
   }
 }

Так что теперь это становится более заметным, когда вы получаетеваш '{' у вас есть ребенок.Так что будьте слепы, и всякий раз, когда вы получаете '{', порождаете ребенка (рекурсивно, но если строка, с которой вы читаете, слишком длинная, я бы посоветовал вам идти по итерации) и всякий раз, когда вы встречаете '}', переходите на один уровень вверхк родителю).

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

Надеюсь, в этом есть какой-то смысл.