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

// stdlib.h is where the atol() function lives

// remember I said strtod when I meant strtol.

/* 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::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 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; }

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

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
    cout << kind << ":" << detail; }

int node::evaluate(symbol_table env)   // is this the right way to pass
                                       // in a symbol table?
{ if (this==NULL)
  { cerr << "in evaluate(NULL), error! null!\n";
    return 0; }
  else if (kind=="variable")
    return env.lookup(detail);
  else if (kind=="number")
    return atol(detail.c_str());
  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=="+")
        val += y;
      else if (kind=="-")
        val -= y;
      else if (kind=="*")
        val *= y;
      else if (kind=="/")
      { if (y==0)
        { cerr << "in evaluate(...), error! attempted division by zero\n";
          return 0; }
        val -= y; }
      else if (kind=="^")
        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 * n1 = new node("variable", "a");
  node * n2 = new node("number", "1");
  node * n3 = new node("+");
  n3->add(n1);
  n3->add(n2);
  node * n4 = new node("number", "3");
  node * n5 = new node("variable", "cat");
  node * n6 = new node("variable", "x");
  node * n7 = new node("+");
  n7->add(n4);
  n7->add(n5);
  n7->add(n6);
  node * n8 = new node("*");
  n8->add(n3);
  n8->add(n7);

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