#include <iostream>
#include <iomanip>
#include <string>
#include <vector>

using namespace std;

class node
{ protected:
    string data;
    vector <node *> child;

  public:
    node(string d)
    { data = d; }

    node * add(node * p)
    { child.push_back(p);
      return this; }

    string getdata()
    { return data; }

    int getnumchildren()
    { return child.size(); }

    node * get(int i)
    { return child[i]; } };

node * mn(string s)
{ return new node(s); }



class stack_frame
{ public:
    string type;
    int where;

    stack_frame(string t)
    { type = t;
      where = 0; }
      
    virtual void print() = 0; };



class reverse_stack_frame: public stack_frame
{ public:
    string s;

    reverse_stack_frame(string s0): stack_frame("R")
    { s = s0; }
    
    virtual void print()
    { cout << "where = " << where << 
              ", s = \"" << s << "\""; } };



class print_stack_frame: public stack_frame
{ public:
    node * p;
    int depth, num, i;

    print_stack_frame(node * p0, int depth0): stack_frame("P")
    { p = p0;
      depth = depth0; }

    virtual void print()
    { cout << "where = " << where <<
              ", p contains \"" << (p == NULL ? "(nothing)" : p->getdata()) << "\""; } };



void print(node * t)
{ vector <stack_frame *> stack;
  stack.push_back(new print_stack_frame(t, 0));
  stack.push_back(new reverse_stack_frame("esrever"));
  stack.push_back(new print_stack_frame(NULL, -1234));
  stack.push_back(new reverse_stack_frame("hippopotamus"));
  stack.push_back(new print_stack_frame(t->get(1), 99));

  while (stack.size() > 0)
  { stack_frame * sf = stack.back();
    stack.pop_back();

    reverse_stack_frame * rsf = dynamic_cast<reverse_stack_frame *>(sf);
    if (rsf != NULL)
    { cout << "reverse: ";
      rsf->print();
      cout << "\n";
      continue; }

    print_stack_frame * psf = dynamic_cast<print_stack_frame *>(sf);
    if (psf != NULL)
    { cout << "print: ";
      psf->print();
      cout << "\n";
      continue; }
      
    cout << "stack_frame with bad type\n";
    break; } }


int main()
{ node * t = mn("ant")
                      ->add(mn("bat")
                                     ->add(mn("egg")
                                                    ->add(mn("kit"))
                                                    ->add(mn("log")))
                                     ->add(mn("fig"))
                                     ->add(mn("git")
                                                    ->add(mn("map"))
                                                    ->add(mn("nut"))
                                                    ->add(mn("old"))
                                                    ->add(mn("pig"))))
                      ->add(mn("cat")
                                     ->add(mn("hat")))
                      ->add(mn("dog")
                                     ->add(mn("ink")
                                                    ->add(mn("qat"))
                                                    ->add(mn("rat")))
                                     ->add(mn("jug")
                                                    ->add(mn("sud"))
                                                    ->add(mn("tip"))));
  print(t); }