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

enum node_type { toperator, tnumber, tvariable, tend };

class token
{ protected:
    node_type type;
    string str;
    int val;

  public:
    token(node_type t, string s, int v)
    { type = t;
      str = s;
      val = v; }

    static token var(string s)
    { return token(tvariable, s, 0); }

    static token num(int v)
    { return token(tnumber, "", v); }

    static token op(string s)
    { return token(toperator, s, 0); }

    static token end()
    { return token(tend, "", 0); }

    node_type gettype()
    { return type; }

    string getstring()
    { return str; }

    int getvalue()
    { return val; }

    void print();
};

void token::print()
{ node_type t = gettype();
  if (t == tnumber)
    cout << "number: " << getvalue() << "\n";
  else if (t == tvariable)
    cout << "variable: " << getstring() << "\n";
  else if (t == toperator)
    cout << "operator: " << getstring() << "\n";
  else if (t == tend)
    cout << "end\n";
  else
    cout << "bad token\n"; }

class node: public token
{ protected:
    vector <node *> links;

  public:
    node(node_type t, string s, int v): token(t, s, v)
    { }

    static node * var(string s)
    { return new node(tvariable, s, 0); }

    static node * num(int v)
    { return new node(tnumber, "", v); }

    static node * op(string s)
    { return new node(toperator, s, 0); }

    node * add(node * n)
    { links.push_back(n);
      return this; }

    int getnumlinks()
    { return links.size(); }

    node * getlink(int i)
    { return links[i]; }

    void print();
    int evaluate();
    void print1(int depth = 0);
};

int node::evaluate()
{ node_type t = gettype();
  if (t == tnumber)
    return getvalue();
  else if (t == tvariable)
  { // look it up in a hash table
    return 0; }
  else if (t == toperator)
  { int L = getlink(0)->evaluate();
    int R = getlink(1)->evaluate();
    char c = getstring()[0];
    switch (c)
    { case '+': return L + R;
      case '-': return L - R;
      case '*': return L * R;
      case '/': { if (R == 0)
                  { cout << "diedivision by zero!\n";
                    return 0; }
                  return L / R; }
      default: { cout << "error '" << c << "'\n";
                 return 0; } } } }

void node::print()
{ node_type t = gettype();
  if (t == tnumber)
    cout << getvalue();
  else if (t == tvariable)
    cout << getstring();
  else if (t == toperator)
  { cout << "(";
    getlink(0)->print();
    cout << getstring();
    getlink(1)->print();
    cout << ")"; } }

void node::print1(int depth)
{ cout << setw(depth*3) << " ";
  node_type t = gettype();

  if (t == tnumber)
    cout << getvalue() << "\n";

  else if (t == tvariable)
    cout << getstring() << "\n";

  else if (t == toperator)
  { cout << getstring() << "\n";
    int num = getnumlinks();
    for (int i = 0; i < num; i += 1)
      getlink(i)->print1(depth+1); } }

class lexan
{ protected:
    istream & in;

  public:
    lexan(): in(cin)
    { }

    lexan(istream & i): in(i)
    { }

    token next()
    { char c = ' ';
      while (c == ' ')
        c = in.get();
      if (in.fail())
        return token::end();

      switch (c)
      { case 'a': case 'j': case 's': case 'A': case 'J': case 'S': 
        case 'b': case 'k': case 't': case 'B': case 'K': case 'T': 
        case 'c': case 'l': case 'u': case 'C': case 'L': case 'U': 
        case 'd': case 'm': case 'v': case 'D': case 'M': case 'V': 
        case 'e': case 'n': case 'w': case 'E': case 'N': case 'W': 
        case 'f': case 'o': case 'x': case 'F': case 'O': case 'X': 
        case 'g': case 'p': case 'y': case 'G': case 'P': case 'Y': 
        case 'h': case 'q': case 'z': case 'H': case 'Q': case 'Z': 
        case 'i': case 'r':           case 'I': case 'R': 
        { string t;
          while (isalpha(c))
          { t += (char) tolower(c);
            c = in.get(); }
          in.unget();
          return token::var(t); }

        case '0': case '1': case '2': case '3': case '4': 
        case '5': case '6': case '7': case '8': case '9': 
        { int v = 0;
          while (isdigit(c))
          { v = v * 10 + digittoint(c);
            c = in.get(); }
          in.unget();
          return token::num(v); }

        case '+': case '-': case '*': case '/': case '^': 
        case '(': case ')':
          return token::op(string(1, c));

        case '\n':
          return token::end();

        default:
        { cout << "Bad character '" << c << "' at beginning of token\n";
          return token::end(); } } } };
          
void main()
{ node * t1 = node::op("+")
                             ->add(node::op("*")
                                                  ->add(node::op("-")
                                                                       ->add(node::num(7))
                                                                       ->add(node::num(2)))
                                                  ->add(node::op("-")
                                                                       ->add(node::num(11))
                                                                       ->add(node::num(3))))
                             ->add(node::op("*")
                                                  ->add(node::op("+")
                                                                       ->add(node::num(1))
                                                                       ->add(node::num(2)))
                                                  ->add(node::op("+")
                                                                       ->add(node::num(3))
                                                                       ->add(node::num(4))));
  t1->print1();
  t1->print();
  cout << "\nthe value is " << t1->evaluate() << "\n";
  lexan L;
  while (true)
  { token t = L.next();
    t.print();
    if (t.gettype() == tend)
      break; } }