#include <iostream>
#include <string>
#include <vector>
#include <stdlib.h>
#include <math.h>

/* The abstract data type symbol_table should be implemented
   as a hash table, but I'm not putting the code for that
   here, I'm going to do something cheap and dirty instead */

class symbol_table
{ protected:
    vector<string> names;
    vector<int> values;
    int whereis(string name);
  public:
    symbol_table();
    void add(string name, int value);
    void update(string name, int newvalue);
    int lookup(string name);
    void print(); };

symbol_table::symbol_table()
{ /* nothing really needs to be done */ }

void symbol_table::add(string name, int value)
{ names.push_back(name);
  values.push_back(value); }

int symbol_table::whereis(string name)
{ for (int i=0; i<names.size(); i+=1)
    if (names[i]==name)
      return i;
  return -1; }

void symbol_table::print()
{ for (int i=0; i<names.size(); i+=1)
    cout << "    " << names[i] << " = " << values[i] << "\n"; }

void symbol_table::update(string name, int newvalue)
{ int pos = whereis(name);
  if (pos<0)
  { cerr << "in update(\"" << name << "\", " << newvalue << "): " <<
            "variable not known\n"; 
    return; }
  values[pos] = newvalue; }

int symbol_table::lookup(string name)
{ int pos = whereis(name);
  if (pos<0)
  { cerr << "in lookup(\"" << name << "\"): " <<
            "variable not known\n"; 
    return 0; }
  return values[pos]; }

struct node
{ string kind;  // will be things like "+", "*", "variable", etc
  vector<node *> subtrees;
  string detail;

  node(string knd, string det = "");
  void oldadd(node *);
  node * add(node *);
  void print();
  int evaluate(symbol_table & environment); };

// we will also need a destructor

node::node(string knd, string det)  // annoyingly, C++ does not permit the
                                    // default value to be repeated here
{ kind = knd;
  detail = det; }

node * var(string name)
{ return new node("variable", name); }

node * num(string value)
{ return new node("number", value); }

node * op(string name)
{ return new node(name); }

node * assign(string name)
{ return new node("assign", name); }

void node::oldadd(node * st)
{ subtrees.push_back(st); }

node * node::add(node * st)
{ oldadd(st);
  return this; }

void node::print()
{ if (this==NULL)
    cout << "NULL";

  else if (kind=="+" || kind=="-" || kind=="*" || kind=="/")
                                    // that would be annoying if we had more
                                    // operators, perhaps we can do better
  { cout << "(";
    for (int i=0; i<subtrees.size(); i+=1)
    { if (i>0)
        cout << kind;
      subtrees[i]->print(); }
    cout << ")"; }

  else if (kind=="assign")
  { cout << "(" << detail << " = ";
    subtrees[0]->print();
    cout << ")"; }

  else
    cout << kind << ":" << detail; }

int node::evaluate(symbol_table & env)
{ if (this==NULL)
  { cerr << "in evaluate(NULL), error! null!\n";
    return 0; }

  else if (kind=="variable")                         // evaluate variable
    return env.lookup(detail);

  else if (kind=="number")                           // evaluate number
    return atol(detail.c_str());

  else if (kind=="assign")                           // evaluate assignment
  { string var = detail;
    int value = subtrees[0]->evaluate(env);
    env.update(var, value);
    return value; }

  else
  { int numsubs = subtrees.size();
    if (numsubs==0)
    { cerr << "in evaluate(...), error! operator without operands\n";
      return 0; }
    int val = subtrees[0]->evaluate(env);
    for (int i=1; i<numsubs; i+=1)
    { int y = subtrees[i]->evaluate(env);
      if (kind=="+")                                 // evaluate +
        val += y;
      else if (kind=="-")                            // evaluate -
        val -= y;
      else if (kind=="*")                            // evaluate *
        val *= y;
      else if (kind=="/")                            // evaluate /
      { if (y==0)
        { cerr << "in evaluate(...), error! attempted division by zero\n";
          return 0; }
        val /= y; }
      else if (kind=="^")                            // evaluate ^
        val = (int)pow(val, y);
      else
      { cerr << "in evaluate(...), unknown operator \"" << kind << "\"\n";
        return 0; } }
    return val; } }

void main()
{ symbol_table ST;
  ST.add("a", 12);
  ST.add("x", 7);
  ST.add("cat", 8);

  node * n = assign("x")
                    ->add(op("*")
                         ->add(op("+")
                              ->add(var("x"))
                              ->add(num("4")))
                         ->add(op("+")
                              ->add(num("4"))
                              ->add(num("5"))));

  cout << "\nVariables:\n";
  ST.print();
  cout << "\nThe formula:\n    ";
  n->print();
  cout << "\nThe value:\n    ";
  cout << n->evaluate(ST);
  cout << "\n\nVariables:\n";
  ST.print();
  cout << "\n\n"; }