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

struct node
{ string data;
  node * left, * right;

  node * add(node * p)
  { if (left == NULL)
      left = p;
    else
      right = p;
    return this; } 
};

node * nn(string s)
{ node * n = new node;
  n->data = s;
  n->left = NULL;
  n->right = NULL; 
  return n; }

void print1(node * n)
{ if (n == NULL)
  { cout << ". ";
    return; }
  cout << "(";
  print1(n->left);
  cout << n->data << " ";
  print1(n->right);
  cout << ")"; }

void print2(node * n, int depth)
{ if (n == NULL)
    return;
  print2(n->left, depth+1);
  cout << depth << ": " << n->data << "\n";
  print2(n->right, depth+1); }

void print3(node * n, int depth)
{ if (n == NULL)
    return;
  print3(n->left, depth+1);
  cout << setw(depth*3) << " " << n->data << "\n";
  print3(n->right, depth+1); }

void print4(node * n, int depth)
{ if (n == NULL)
    return;
  cout << "( ";
  print4(n->left, depth+1);
  cout << n->data;
  print4(n->right, depth+1);
  cout << ") "; }

void print5(node * n)
{ if (n == NULL)
    return;
  print5(n->left);
  cout << n->data << " ";
  print5(n->right); }

void print6(node * n)
{ if (n == NULL)
    return;
  cout << n->data << " ";
  print6(n->left);
  print6(n->right); }

void print7(node * n)
{ if (n == NULL)
    return;
  print7(n->left);
  print7(n->right);
  cout << n->data << " "; }

void main1()
{ node * a = nn("narwhal")->add(nn("kraken")->add(nn("c")))
                          ->add(nn("unicorn")->add(nn("rhinoceros")->add(nn("p"))
                                                                   ->add(nn("sloth")))
                                             ->add(nn("wolf")));
  print3(a, 1);
  cout << "\n"; }

int eval(node * p)
{ if (p->data == "+")
  { int L = eval(p->left);
    int R = eval(p->right);
    return L+R; }
  else if (p->data == "-")
  { int L = eval(p->left);
    int R = eval(p->right);
    return L-R; }
  else if (p->data == "*")
  { int L = eval(p->left);
    int R = eval(p->right);
    return L*R; }
  else
    return atol(p->data.c_str()); }

void main()
{ node * a = nn("*")->add(nn("+")->add(nn("2"))
                                 ->add(nn("3")))
                    ->add(nn("+")->add(nn("*")->add(nn("5"))
                                              ->add(nn("3")))
                                 ->add(nn("5")));
  print5(a);
  cout << "\n";
  print6(a);
  cout << "\n";
  print7(a);
  cout << "\n";
  cout << "value = " << eval(a) << "\n"; }