/*------------------------------------------------
/  CLASSES : trees or nodes  
/                     (thanks to Nicholas Amadori)
/                      use of inheritance.
/  DEPTH FIRST VISIT OF A TREE (recursive) Version 1
/                
/  Grammar for the input tree:
/  char ::= '0' | '1' | ... | '9'
/  node ::= char | - char node | (node char node)
/
/  internal tree:
/  Tree = Num | Num x Tree | Tree x Num x Tree
/
/  Grammar for the output tree:
/  t ::= n | (n.t) | (t.n.t)
/------------------------------------------------*/
#include <iostream.h> 
#include <stdlib.h> 
//======================= for trees ===============
typedef int values;
//----------
class node {
public :
virtual void dfv() = 0;  // dfv is depth_first_visit
virtual void print() = 0;
};
//---------------------------
class leaf: public node{
public:
   values value; 
   void dfv(); void print();};

void leaf::dfv()   {cout << value << " ";};
void leaf::print() {cout << value;};
//---------------------------
class unary: public node{
public:
   values value1; node*  son; 
   void dfv(); void print();};

void unary::dfv()   {(*son).dfv(); cout << value1 << " ";};
void unary::print() {cout << "(" << value1 << ".";
                     (*son).print(); cout << ")";};
//---------------------------
class binary: public node{
public:
   values value2; node* left; node* right;  
   void dfv(); void print();};

void binary::dfv()   {(*left).dfv(); (*right).dfv();
                      cout << value2 << " ";};
void binary::print() {cout << "("; (*left).print(); 
                      cout << "." << value2 << ".";   
                      (*right).print(); cout << ")";};
//---------------------------
int v(char c) {return c-48;};

node* ptree()  
{char c; cin >> c;
if ('0' <= c && c <= '9') {leaf* l = new leaf; (*l).value = v(c);
                           return l;} else 
if (c == '-') {unary* u = new unary; cin >> c; (*u).value1 = v(c);
               (*u).son = ptree(); return u;} else 
if (c == '(') {binary* b = new binary; (*b).left = ptree(); cin >> c; 
               (*b).value2 = v(c); (*b).right = ptree(); cin >> c; 
               return b; } 
else {cerr << " Error in node::ptree !!!" ; exit(EXIT_FAILURE); }
};


//-------------------------------------------
int main()
{node* t; 
cout << "Input a tree according to the given grammar above, please."
     << endl;
t = ptree(); 
cout << endl << "Tree in input: " << endl; 
(*t).print(); cout << endl; cout << endl; 

cout << "Depth first visit of the tree:" << endl;
(*t).dfv(); cout << endl; 
return(EXIT_SUCCESS);
}
/*-------------------------------------------- 
input:       output:
             Input a tree according to the given grammar above, please.
             (-231(-564-78))
 
             Tree in input:
             ((2.3).1.((5.6).4.(7.8)))
 
             Depth first visit of the tree:
             3 2 6 5 8 7 4 1     
---------------------------------------------- */