How to populate the Tree structure Declaratively

Question

I want to define a 'node' class / struct, and then declare a tree of these nodes in the code so that the way the code is formatted reflects the tree structure, and there isn’t “too much” boiler stove in the way.

Please note that this is not a question about data structures, but rather about what C ++ functions I could use to get a similar style of declarative code in the example below.

Perhaps with C ++ 0X this would be easier since it had more features in the field of building objects and collections, but I am using Visual Studio 2008.

Example tree node Type:

struct node { string name; node* children; node(const char* name, node* children); node(const char* name); }; 

What I want to do:

Declare a tree so that its structure is reflected in the source code

 node root = node("foo", [ node("child1"), node("child2", [ node("grand_child1"), node("grand_child2"), node("grand_child3" ]), node("child3") ]); 

NB: what I do not want to do:

Declare a whole bunch of temporary objects / calls and build a back tree

 node grandkids[] = node[3] { node("grand_child1"), node("grand_child2"), node("grand_child3" }; node kids[] = node[3] { node("child1"), node("child2", grandkids) node("child3") }; node root = node("foo", kids); 

Answer 1

If you don't mind over-copying nodes and using brackets () instead of square brackets [] , then this should work.

In fact, you can avoid copying by saving pointers to node_group , not copying, but since it's Friday afternoon, and I'm very lazy, I'll leave it to you.

 struct node { std::string name; std::vector<node> children; node(const char* n) : name (n) { } node(const char* n, const class node_group& group); }; struct node_group { std::vector<node> children; }; node::node(const char* n, const class node_group& group) : name (n) , children (group.children) { } node_group operator ,(const node& n1, const node& n2) { node_group group; group.children.push_back (n1); group.children.push_back (n2); return group; } node_group operator ,(const node_group& gr, const node& n2) { node_group group (gr); group.children.push_back (n2); return group; } int main () { node root ("foo", (node("child1"), node("child2", (node("grand_child1"), node("grand_child2"), node("grand_child3")) ), node("child3")) ); } 

Answer 2

http://en.wikipedia.org/wiki/Expression_templates

Using this technique, you can get the syntax as:

 Node root("bob") = (node("child1") <<( node("grandkid"), node("grandkid2") ) ), node("child2"); 

where you overload operator, and operator<< to build an expression tree that is used to create your node root.

Answer 3

It's not hard to write a parser for the syntax you would like to use. Here is a simple but working code. I allowed myself to slightly modify your node object, it does not use an array of pointers to store children, but std::vector

The advantage of this approach is that you can build a tree from text provided at runtime, for example. read from the configuration file. Also note that ostream& operator<<(ostream&, const node&) prints your trees in one format, this can be convenient for serializing your trees (for writing them to a file or sending over the network) or testing modules.

  #include <stdio.h> #include <stdlib.h> #include <ctype.h> #include <string> #include <vector> #include <iostream> using namespace std; struct node { string name; vector<node*> children; node(const string& name, const vector<node*> children); node(const string& name); }; ostream& operator<<(ostream& o, const node& n) { o << "node('" << n.name << "'"; if (n.children.size()) { o << ", ["; for (size_t i = 0; i < n.children.size(); ++i) o << (i ? "," : "") << *(n.children[i]); o << "]"; } o << ")"; return o; } node::node(const string& s, const vector<node*> children) : name(s), children(children) {} char* parseNode(node** n, const char *ss); char *skipSpace(const char *ss) { char *s = (char *) ss; while (isspace(*s)) ++s; return s; } void expected_error(const char* s) { fprintf(stderr, "Error: expected '%s'\n", s); exit(1); } char *expect(const char *expected, char *s) { char *ex = skipSpace(expected); s = skipSpace(s); for ( ; *ex && *s; ++ex, ++s) if (*ex != *s) expected_error(expected); if (*ex) expected_error(expected); return s; } char *expectString(string& str, const char *ss) { char *s = skipSpace(ss); s = expect("'", s); char *start = s++; while (*s != '\'') ++s; str = string(start, s - start); return ++s; } char * parseChildren(vector<node*>& children, char *s) { s = expect("[", s); s = skipSpace(s); while (*s != ']') { node *n = 0; s = parseNode(&n, s); children.push_back(n); s = skipSpace(s); if (*s == ',') ++s; else break; } s = expect("]", s); return s; } char* parseNode(node** n, const char *ss) { char *s = (char *) ss; s = expect("node", s); s = expect("(", s); string name; s = expectString(name, s); vector<node*> children; s = skipSpace(s); if (*s == ',') s = parseChildren(children, ++s); *n = new node(name, children); s = expect(")", s); return s; } int main() { node * n = 0; parseNode(&n, " node('foo'," " [" " node('child1')," " node('child2', " " [" " node('grand_child1')," " node('grand_child2')," " node('grand_child3')" " ])," " node('child3')" " ])" ); cout << *n; return 0; }