A parse tree builder; Stacks and pointers

Question

My task, is to implement a build a parse tree for a very simplified language.

Part of this entails creating a iterator to insert nodes and preform a Depth First Search without using recursion

This requires creating a stack and pushing the current state of the iterator onto the stack.

this state includes the parent node and the index of the child which being visited at the moment.

Since I am still inexperienced using C++. I have being do some research of various features of C++. With regards to stacks, I haven't be able to find example/information with complex a structure.

I would appreciate any hints, suggestions and pointers (no pun intended ) on how to implement this.

Edit: I felt the need to add additional information about the nodes

in my node class , I have following initialization variable/s:

 node** children; //This create a array of pointers to children 

My custom iterator is not build using templates

Answer 1

Here is a rough sketch you can start working with (no templates, no STL containers, static arrays, macro constants, no real error handling, no cool C++11 features etc.):

tree_node.h

#ifndef _TREE_NODE_H_
#define _TREE_NODE_H_

#define NODE_TEXT_LENGTH_MAX 10
#define NODE_CHILDREN_COUNT_MAX 10

class tree_node {
public:
  tree_node(const char* text);
  ~tree_node();
  const char* text() const { return _text; }
  int child_count() const { return _child_count; }
  tree_node* child(const int i) const;
  tree_node* add_child(const char* text);
private:
  char _text[NODE_TEXT_LENGTH_MAX + 1];
  tree_node* _children[NODE_CHILDREN_COUNT_MAX];
  int _child_count;
};

#endif // _TREE_NODE_H_

tree_node.cpp

#include "tree_node.h"

tree_node::tree_node(const char* text) {
  int i = 0;
  while (i < NODE_TEXT_LENGTH_MAX && text[i] != '\0') {
    _text[i] = text[i];
    ++i;
  }
  _text[i] = '\0';
  _child_count = 0;
}

tree_node::~tree_node() {
  for (int i = 0; i < _child_count; ++i) {
    delete _children[i];
  }
}

tree_node* tree_node::child(const int i) const {
  return 0 <= i && i < _child_count ? _children[i] : 0;
}

tree_node* tree_node::add_child(const char* text) {
  if (_child_count < NODE_CHILDREN_COUNT_MAX) {
    ++_child_count;
    _children[_child_count - 1] = new tree_node(text);
  }
  return this;
}

tree_iterator.h

#ifndef _TREE_ITERATOR_H_
#define _TREE_ITERATOR_H_

#include "tree_node.h"

#define ITERATOR_STATE_STACK_DEPTH_MAX 10

struct tree_iterator_state {
  tree_node* parent;
  int i;
};

class tree_iterator {
public:
  tree_iterator(tree_node* p);
  tree_iterator(const tree_iterator& other);
  tree_iterator& operator++();
  tree_iterator operator++(int) { tree_iterator temp(*this); operator++(); return temp; }
  bool operator==(const tree_iterator& other) { return _p == other._p; }
  bool operator!=(const tree_iterator& other) { return _p != other._p; }
  tree_node* operator*() { return _p; }
private:
  tree_node* _p;
  tree_iterator_state _state_stack[ITERATOR_STATE_STACK_DEPTH_MAX];
  int _state_stack_depth;
};

#endif // _TREE_ITERATOR_H_

tree_iterator.cpp

#include "tree_iterator.h"

tree_iterator::tree_iterator(tree_node* p) {
  _p = p;
  _state_stack[0].parent = 0;
  _state_stack[0].i = 0;
  _state_stack_depth = 1;
}

tree_iterator::tree_iterator(const tree_iterator& other) {
  _p = other._p;
  _state_stack_depth = other._state_stack_depth;
  for (int i = 0; i < _state_stack_depth; ++i) {
    _state_stack[i].parent = other._state_stack[i].parent;
    _state_stack[i].i = other._state_stack[i].i;
  }
}

tree_iterator& tree_iterator::operator++() {
  if (_p != 0 && _p->child_count() > 0 && _state_stack_depth < ITERATOR_STATE_STACK_DEPTH_MAX) {
    ++_state_stack_depth;
    _state_stack[_state_stack_depth - 1].parent = _p;
    _state_stack[_state_stack_depth - 1].i = 0;
    _p = _p->child(0);
  } else {
    while (true) {
      tree_node* parent = _state_stack[_state_stack_depth - 1].parent;
      int i = _state_stack[_state_stack_depth - 1].i;
      if (parent == 0) {
        _p = 0;
        break;
      } else if (i < parent->child_count() - 1) {
        ++i;
        _p = parent->child(i);
        _state_stack[_state_stack_depth - 1].i = i;
        break;
      } else {
        --_state_stack_depth;
      }
    }
  }
  return *this;
}

main.cpp

#include <iostream>
#include "tree_node.h"
#include "tree_iterator.h"

void test1() {
  std::cout << "Test 1:" << std::endl;
  tree_node* root = 0;
  tree_iterator begin(root);
  tree_iterator end(0);
  for (tree_iterator it = begin; it != end; ++it) {
    std::cout << (*it)->text() << std::endl;
  }

  std::cout << std::endl;
}

void test2() {
  std::cout << "Test 2:" << std::endl;
  tree_node* root = new tree_node("x");
  tree_iterator begin(root);
  tree_iterator end(0);
  for (tree_iterator it = begin; it != end; ++it) {
    std::cout << (*it)->text() << std::endl;
  }
  std::cout << std::endl;
}

void test3() {
  std::cout << "Test 3:" << std::endl;
  tree_node* root = new tree_node("*");
  root->add_child("2")->add_child("+");
  root->child(1)->add_child("3")->add_child("4");
  tree_iterator begin(root);
  tree_iterator end(0);
  for (tree_iterator it = begin; it != end; ++it) {
    std::cout << (*it)->text() << std::endl;
  }
  std::cout << std::endl;
}

void test4() {
  std::cout << "Test 4:" << std::endl;
  tree_node* root = new tree_node("1");
  root->add_child("2")->add_child("7")->add_child("8");
  root->child(0)->add_child("3")->add_child("6");
  root->child(0)->child(0)->add_child("4")->add_child("5");
  root->child(2)->add_child("9")->add_child("12");
  root->child(2)->child(0)->add_child("10")->add_child("11");
  tree_iterator begin(root);
  tree_iterator end(0);
  for (tree_iterator it = begin; it != end; ++it) {
    std::cout << (*it)->text() << std::endl;
  }
  std::cout << std::endl;
}

void test5() {
  std::cout << "Test 5:" << std::endl;
  tree_node* root = new tree_node("1");
  root->add_child("2")->add_child("7")->add_child("8");
  root->child(0)->add_child("3")->add_child("6");
  root->child(0)->child(0)->add_child("4")->add_child("5");
  root->child(2)->add_child("9")->add_child("12");
  root->child(2)->child(0)->add_child("10")->add_child("11");
  tree_iterator begin(root->child(2));
  tree_iterator end(0);
  for (tree_iterator it = begin; it != end; ++it) {
    std::cout << (*it)->text() << std::endl;
  }
  std::cout << std::endl;
}

void test6() {
  std::cout << "Test 6:" << std::endl;
  tree_node* root = new tree_node("1");
  root->add_child("2")->add_child("7")->add_child("8");
  root->child(0)->add_child("3")->add_child("6");
  root->child(0)->child(0)->add_child("4")->add_child("5");
  root->child(2)->add_child("9")->add_child("12");
  root->child(2)->child(0)->add_child("10")->add_child("11");
  tree_iterator begin(root->child(2));
  tree_iterator end(root->child(2)->child(0)->child(1));
  for (tree_iterator it = begin; it != end; ++it) {
    std::cout << (*it)->text() << std::endl;
  }
  std::cout << std::endl;
}

int main(int argc, char** argv) {
  test1();
  test2();
  test3();
  test4();
  test5();
  test6();
  return 0;
}

Output

Test 1:

Test 2:
x

Test 3:
*
2
+
3
4

Test 4:
1
2
3
4
5
6
7
8
9
10
11
12

Test 5:
8
9
10
11
12

Test 6:
8
9
10

How does it work?

The tree_node class represents tree nodes: each node has a text label and an arbitrary number of child nodes. A tree can be built by creating a root node, and adding child nodes repeatedly.

The tree_iterator class is initialized with one of the nodes. The subtree, the root of which is this node, can be walked in a depth-first manner by repeatedly calling the ++ operator of the iterator. The iteration can be stopped when one of the nodes of this subtree is reached, or when there is no more nodes to be visited. In the latter case the iterator becomes equal with the end iterator, that is, a tree iterator initialized with the NULL pointer (= 0). (The end iterator could have been defined as a special object.)

The tests use the following trees:

1. The empty tree.
2. A one-node tree.
3. The AST of the expression 2 * (3 + 4).

4. The example tree from the DFS article of Wikipedia:

   

5. The subtree of the latter, the root of which is node-8.
6. The same subtree, but the iteration is stopped before node-11 is reached.