Parsing Text to Make a Tree Data Structure

Question

Let's say I'm reading a line from a file:

{Parent{{ChildA}{ChildB}}}

More complex example:

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

Which is the grammar used to construct a tree.

Any name inside {} brackets is a node, and if within that bracket there are other nodes (brackets), those nodes are children.

I'm able to parse the first specific example using a counter, but only to find the text names of the nodes. How can I parse this so that I can determine what nodes are children of one another? I can't seem to wrap my mind around the code I would use. I have a feeling I would use recursion.

Any help or advice would be appreciated.

C++ is preferred.

Thank you very much.

This looks like a simple context-free grammar, so you could use any number of standard tools to create a lexer and a parser for that. — Kerrek SB, Oct 18 '11 at 21:55
@LearningPython : Are you new to C++ as well, or relatively familiar with the language? — ildjarn, Oct 18 '11 at 21:58
@ildjarn I'm familiar with the basics (I can read in a file and what not), but I have never parsed anything to this extent before into a tree data structure. I'm familiar with data structures in other languages like Python, but not recursion or parsing like this. — , Oct 18 '11 at 22:01
@Mooing Duck Yes, I don't want it to be done for me, but any suggestions that would push me in the right direction would be very much appreciated. — , Oct 18 '11 at 22:03
Do you know SGML? If you read the SGML grammar and can make sense of it, then this should be a breeze. But even if you don't, see if you can make sense of [this description](http://en.wikipedia.org/wiki/EBNF). — Kerrek SB, Oct 18 '11 at 22:05

phimuemue · Answer 1 · 2016-01-09T12:30:16.583

You'll have to keep track of the current nesting. For this you can use a stack.

Each time, you encounter a { (followed by node name), you know that this is the beginning of a new node. This new node is a child of the current node.

Each time you come across }, you know that the current node is finished now, meaning that you have to tell your program that the current node is now changed to the parent of the current node.

Example:

{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.

score 4 · Accepted Answer · answered Oct 18 '11 at 23:58

Spoiling the fun with an answer you can't use anyway if it's homework:

A minimal implementation with 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;
}

The implementation of dump is regrettably almost the equivalent amount of code :)

It will print:

_{Here is the definition of 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);
}

Vorapsak · Answer 3 · 2011-10-18T22:39:05.290

Since it's homework, I would assume you have to implement the solution by hand, so you would probably want to use a Stack to hold the data while you're parsing the input.

Each time you see an { you create a new node with the data following it, and push it onto the stack.

Each time you see an } you pop the last node off the stack, and add it into your tree shape.

The other thing you would need for this approach is a Node pointer, we'll call it currentNode, so that we can make the actual hierarchy happen. To begin with, currentNode will be null; the first time a node is popped off the stack, you put that node into currentNode. Otherwise, when you pop a value, we know we have both children of the next node on the stack.

I'll let you run with it from there, but if you need more I'll be standing by.

Thank you Vorapsak. Quick Question: how would you handle knowing which nodes are children of other nodes? — , Oct 18 '11 at 22:10

score 1 · Answer 4 · answered Oct 18 '11 at 22:15

The grammar you have is relatively simple.

Based on your examples the nodes may be declared in one of two different ways:

{nodename}

which is the simple one and

{nodename{childnodes}}

which is the complex one

Now to turn this into a more formal grammar we first write of the constituent parts:

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

Then we can define the grammar (the non terminals are capitalized)

Node ::= "{" Nodename "}" | "{" Nodename "{" Childnodes "}" Nodename ::= at least one letter Childnodes ::= one or more Node

The standard way to turn than into a parser (assuming you have to write it by hand, which you properly will because it is so small) is to write a method that can parse each of the non terminals (what you see on the left of the :== sign).

The only thorny issue is that you have to write the Nodename function to check if there is a "{" (in which case the node has a child) or a "}" (in which case it does not have a child) after the end of the node name.

Also I took the liberty of not writing down all possible ascii strings as the Nodename.

score 0 · Answer 5 · answered Jun 25 '13 at 13:11

Each time you find "{" then add child to the parent then each time you find "}" set the current tree to be parent tree.

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

score 0 · Answer 6 · answered Oct 18 '11 at 22:13

Imagine this to be something like this (Even though it is linear from the file that you are reading from, just try visualizing it this way)

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

So now its more visible that whenever you get your '{' you have a child. So go blind and whenever you get a '{' spawn a child (recursively but if the line that you are reading from is too long then I would suggest you go by iteration) and whenever you encounter a '}' move one level up (to the parent).

I suppose you would have be having a function for adding a node to the tree and moving up your tree one level. If that is all you have then all you need to do is just put the pieces together.

I hope this makes some sense.

Parsing Text to Make a Tree Data Structure

6 Answers6

Linked