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

// a cheap and nasty symbol table:

vector<string> var_names;
vector<int> var_values;

int findvar(string name)
{ for (int i=0; i<var_names.size(); i+=1)
    if (var_names[i]==name)
      return i;
  return -1; }

int getvar(string name)
{ int pos=findvar(name);
  if (pos<0)
    return 0;
  return var_values[pos]; }

int getvar(int i)
{ if (i<0 || i>=var_values.size())
    return 0;
  return var_values[i]; }

void setvar(string name, int val)
{ int pos=findvar(name);
  if (pos<0)
  { var_names.push_back(name);
    var_values.push_back(val); }
  else
    var_values[pos]=val; }

void printvars()
{ for (int i=0; i<var_names.size(); i+=1)
    cout << "  " << setw(6) << var_names[i] << " = " << var_values[i] << "\n"; }

const int _binop=1, _number=5, _variable=6;

struct node
{ int kind;
  int value;
  string name;
  vector <node *> sub;

  node(int k, int v=0, string n="")
  { kind=k;
    value=v;
    name=n; }

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

node * num(int v)
{ return new node(_number, v); }

node * var(string n)
{ return new node(_variable, 0, n); }

node * binop(string o)
{ return new node(_binop, 0, o); }

int evaluate(node * n)
{ if (n==NULL)
  { cout << "NULL!!!";
    return 0; }
  else if (n->kind == _number)
    return n->value;
  else if (n->kind == _variable)
  { int p = findvar(n->name);
    if (p<0)
    { cout << "undefined variable '" << n->name << "'\n";
      return 0; }
    return getvar(p); }
  else if (n->kind == _binop)
  { if (n->sub.size() != 2)
    { cout << "ERROR IN +!!!";
      return 0; }
    else
    { int a=evaluate(n->sub[0]);
      int b=evaluate(n->sub[1]);
      if (n->name=="+")
        return a+b;
      else if (n->name=="-")
        return a-b;
      else if (n->name=="*")
        return a*b;
      else if (n->name=="/")
      { if (b==0)
        { cout << "division by zero";
          return 0; }
        return a/b; }
      else
      { cout << "bad operator";
        return 0; } } }
  else
  { cout << "ERROR BAD KIND";
    return 0; } }

void print(node *n)
{ if (n==NULL)
    cout << "NULL!!!";
  else if (n->kind == _number)
    cout << n->value;
  else if (n->kind == _variable)
    cout << n->name;
  else if (n->kind == _binop)
  { if (n->sub.size() != 2)
      cout << "ERROR IN +!!!";
    else
    { cout << "(";
      print(n->sub[0]);
      cout << n->name;
      print(n->sub[1]);
      cout << ")"; } }
  else
    cout << "ERROR BAD KIND"; }

void main()
{
  // some variables to play with:

  setvar("a", 2);
  setvar("cat", 7); 

  node * root = binop("+")
                   ->add(binop("*")
                            ->add(var("a"))
                            ->add(num(100)))
                   ->add(binop("-")
                            ->add(binop("-")
                                      ->add(num(8))
                                      ->add(var("cat")))
                            ->add(num(6)));

  cout << "given\n";
  printvars();
  cout << "the formula\n  ";
  print(root);
  cout << "\nevaluates to\n  " << evaluate(root) << "\n";
 }