//////////////////////////////////////////////////
// CSE 428, Spring 2000, solution of HW #2
// File S2.C
//////////////////////////////////////////////////

#include <iostream>
#include <string>

//////////////////////////////////////////////////

class node{

  private:
    int value;  
    string type;
    string content;

  public:
    node (string t, int v){
      if(t != "num")
        cout << "error in node construction ";
      type = t;
      value = v;
    }

    node (string t, string c){
      type = t;
      content = c;
    }

    string get_type(){ // returns the type
      return type;
    }

    int get_value(){ // returns the value
      return value;
    }

    string get_ide(){ // returns the identifier
      return content;
    }

    string get_op(){ // returns the operator
      return content;
    }

};

//////////////////////////////////////////////////

class tree{

  private:
    node* root;
    tree* left;
    tree* right;

  public:
    tree (node* n){
      root = n;
      left=NULL;
      right=NULL;
    }

    tree (node* n, tree* l, tree* r){
      root = n;
      left = l;
      right = r;
    }

    ~tree (){ // this destructor was not required in the Assignment 
      delete root;
      delete left;
      delete right;
    }

    node* get_root(){ // returns the root
      return root;
    }

    tree* get_left(){ // returns the left subtree
      return left;
    }

    tree* get_right(){ // returns the right subtree
      return right;
    }

};

//////////////////////////////////////////////////

class environment{
  private:
    string ide;
    int value;
    environment* next;

  public:
    environment(string id, int v, environment* e){
      ide = id;
      value = v;
      next = e;
    }

    ~environment(){ // this destructor was not required in the Assignment 
      delete next;
    }
	
    int lookup (string id){
      environment* assoc = this;
      while(assoc != NULL){
        if(assoc->ide == id)
	  return assoc->value;
        else
	  assoc = assoc->next;
      }
      cout << "error: undeclared identifier";
      return -1;
    }

    environment* add (string id, int v, environment* r){
      environment* assoc = new environment(id, v, r);
      return assoc;
    }

};

//////////////////////////////////////////////////

int eval(tree* t, environment* r){
  node* n = t->get_root();
  string ty = n->get_type();
  if(ty == "num")
    return n->get_value();
  else if(ty == "ide")
      return r->lookup(n->get_ide());
  else if(ty == "op"){
      int k1 = eval(t->get_left(), r);
      int k2 = eval(t->get_right(), r);
      if((n->get_op()) == "+")
	  return k1+k2;
      else if((n->get_op()) == "*")
	  return k1*k2;
      else if((n->get_op()) == "-")
	  return k1-k2;
      else if((n->get_op()) == "/")
	  return k1/k2;
      }
  else if(ty=="dec"){
      string x = n->get_ide();
      int k = t->get_left()->get_root()->get_value();
      environment* r1 = r->add(x,k,r);
      return eval(t->get_right(), r1);
    }
return 0;
}

//////////////////////////////////////////////////