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

#include <iostream>
#include <string>
using namespace std;

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

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 (){ 
      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:

    class element{

       string ide;
       int value;
       element* next;

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

    element* first;

  public:

    environment(){
      first = NULL;
    }

    ~environment(){ 
      element* temp;
      while (first != NULL){
         temp = first;
         first = first->next;
         delete temp;
      }
    }
	
    int lookup (string id){
      element* temp = first;
      while(temp != NULL){
        if(temp->ide == id)
	  return temp->value;
        else
	  temp = temp->next;
      }
      cout << "error: undeclared identifier";
      return -1;
    }

    void add(string id, int v){
      first = new element(id, v, first);
    }

    void pop (){
      element* temp = first;
      first = first->next;
      delete temp;
    }
};

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

environment* empty_environment(){
     return (new environment());
}

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

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();
      r->add(x,k);
      int res = eval(t->get_right(), r);
      r->pop();
      return res;
    }
return -1;
}

/*
//////////////////////////////////////////////////

   int main(){
        node* n1 = new node("dec","x");
        node* n2 = new node("num",2);
        node* n3 = new node("op","+");
        node* n4 = new node("ide","x");
        node* n5 = new node("num",5);
        tree* t2 = new tree(n2);
        tree* t4 = new tree(n4);
        tree* t5 = new tree(n5);
        tree* t3 = new tree(n3,t4,t5);
        tree* t1 = new tree(n1,t2,t3);
        environment *r = empty_environment();
        cout << eval(t1,r) << " ";
        delete t1;
        delete r;
   }

//////////////////////////////////////////////////
*/