//--------------------------------------------
//  CLASSES : trees (1)
//--------------------------------------------
#include <iostream.h> 
//======================= for trees ===============
typedef int values;
//----------
class node {
public :
    class leaf
    {public : values value; };

    class unary
    {public : values value1; node*  son; };

    class binary
    {public : values value2; node* left; node* right; } ;

enum  {leafnode, unarynode, binarynode} tag;
union {leaf l; unary u; binary b; };
node(leaf ll); node(unary uu); node(binary bb);
void print(); }; 
//----------
node::node(leaf ll)
   {tag = leafnode ; l.value = ll.value ; }
node::node(unary uu)
   {tag = unarynode ; u.value1=uu.value1;
                      u.son=uu.son; }
node::node(binary bb)
   {tag = binarynode ; b.value2 = bb.value2 ;
                       b.left = bb.left; b.right = bb.right; }
void node::print()  
{switch (tag){
case leafnode:  cout << l.value ; break;
case unarynode:
        cout << "(" << u.value1 << "."; (*(u.son)).print();
        cout << ")" ; break;
case binarynode:
        cout << "(" ; (*(b.left)).print(); 
        cout << "." << b.value2 << "."; (*(b.right)).print(); 
        cout << ")" << endl; break;
default: cout << " Error in node::print !!!" ; }};
//-------------------------------------------
typedef node* treeptr ;

//========================= for stacks ==============
class cell
{public : 
   treeptr tp; cell* next;
   cell(treeptr t, cell* nx) : tp(t), next(nx) { }; 
};

typedef cell* stackptr;

//---------- pop and push -------
void pop(stackptr &S,  treeptr &x)
{ if (S == 0) {cout << "\n error: pop of empty stack ! \n"; } 
  else {x = S->tp; S = S->next; } ; }

void push(treeptr x,  stackptr &S)
{stackptr S1 = new cell(x,S); S = S1 ; }

//-------------------------------------------
void main()
{node::leaf l; l.value = 49;  node L(l); 
node * Lpr = & L ; (* Lpr).print();
cout << endl;

node::unary un; un.value1 = 67; un.son = Lpr; node R(un); 
node * Rpr = & R; (*Rpr).print();
cout << endl;

node::binary b1; b1.value2 = 13;  
b1.left = Lpr; b1.right = Rpr; node B(b1); 
node * Bpr = & B ; (*Bpr).print(); 
cout << "--------------" << endl;

treeptr t = 0; stackptr st = 0;

push(Lpr,st); push(Lpr,st); push(Rpr,st);

pop(st,t); (*t).node::print(); cout <<  endl;
pop(st,t); (*t).node::print(); cout <<  endl; 
pop(st,t); (*t).node::print(); cout <<  endl;
pop(st,t); 
}
/*--------------------------------------------
input:             output:
                   49
                   (67.49)
                   (49.13.(67.49))
                   --------------
                   (67.49)
                   49
                   49
 
                   error: pop of empty stack ! 
---------------------------------------------- */