// queue.h
// linked list implementation of Queue ADT
#include <iostream>
#include <cstddef>		 	// for NULL
#include <new>				// for bad_alloc exception
using namespace std;
 
template <class T>
struct Node;					// forward reference, Node defined below
 
template<class T>
class Queue
{
  private:
	Node<T> * front;			// pointer to front of Queue
	Node<T> * rear;			// pointer to rear of Queue
	int length;				// logical length of Queue
  public:
  	Queue();			// default c-tor
	~Queue();			// d-tor
 
	void makeMT();		// make Queue logically empty
	// Post: front and rear have been reset to the empty state
	bool isMT() const;		// test for Queue being empty
					// returns true if the queue is empty; false otherwise
	bool isFull() const;	// test for Queue being full
					// Returns true if the queue is full; false otherwise
	void enqueue(T item);		// enqueue an item
	// Post: parameter item is at the rear of the queue
	void dequeue(T & item);	// dequeue an item
	// Post: front of queue has been removed and a copy returned in item
	int getLength() const;		// returns length queue  
	// Post: Queue is unchanged
	void replaceItem(T old, T nu);  // replaces all occurrences of old with nu
	// Pre:  queue has been initialized
	// Post:  each occurrence of old in queue has been changed to nu
	void prntQueue() const;	// displays contents of queue
	// Pre:  queue has been initialized
	// Post: contents of queue have been printed
 
}; // end Queue
 
	// implementations
/*template <class T>
struct Node 
{
    T info;
    Node<T> * next;
}; */
 
template<class T>			// default class c-tor
Queue<T>::Queue() : front(NULL), rear(NULL), length(0)			
{ }
 
template<class T>			// d-tor
Queue<T>::~Queue() 			
{
  makeMT();
}
 
template<class T>
void Queue<T>::makeMT()
{
	Node <T> * temp;
 
    while ( front != NULL )
    {
        temp = front;
        front = front->next;
        delete temp;
    } // endwhile
    rear = NULL;
	length = 0;
	return;
} // end makeMT()
 
template<class T>
bool Queue<T>::isMT() const
{
  return ( length == 0 );	// alternative is to return ( front == NULL );
} // end isMT()
 
template<class T>
bool Queue<T>::isFull() const
{
	Node<T> * location;
	try
	{
		location = new Node<T>;
		delete location;
		return false;
	} // endtry
	catch(bad_alloc exception)
	{
		return true;
	} // endcatch
} // end isFull()
 
template<class T>
void Queue<T>::enqueue(T item)
{
	Node<T> * newNode;
 
    newNode = new Node<T>;
    newNode->info = item;
    newNode->next = NULL;
    if ( rear == NULL )
        front = newNode;
    else
        rear->next = newNode;
    rear = newNode;
	length++;
} // end enqueue()
 
template<class T>
void Queue<T>::dequeue(T & item)
{ 
	Node<T> * temp;
 
    temp = front;
    item = front->info;
    front = front->next;
    if ( front == NULL )
        rear = NULL;
    delete temp;
	length--;
	return;
} // end dequeue()
 
template<class T>
int Queue<T>::getLength() const 
{
	return length;
} // end getLength()
 
template<class T>
void Queue<T>::replaceItem(T old, T nu) 
{
  Node<T> * location = front;
 
  while ( location != NULL )
  {
    if ( location->info == old )
        location->info = nu;
    location = location->next;
  } // endwhile
} // end replaceItem()
 
template<class T>
void Queue<T>::prntQueue() const
{
	Node<T> * location = front;
 
	cout << "\n Printing contents of queue:\n";
	while ( location != NULL )
	{
		cout << "\t" << location->info;
		location = location->next;
	} // endwhile
	cout << endl;
	return;
} // end prntQueue()
// end Queue implementations
 
 
// stack.h
// header file for Stack ADT using a templated linked list
//#pragma once
 
//#include "stkxcptn.h"
template <class T>
struct Node;	// forward reference - struct Node is defined below
 
template<class T>
class Stack
{
  private:
    Node<T> * top;
 
  public:
	Stack();
	~Stack();
 
    void makeMT();
    // Function:  sets stack to an empty state
    // Post: Stack is empty
 
    bool isFull() const;
    // Function:  determines whether the stack is full
    // Pre:  Stack has been initialized
    // Post: Function value = false (assuming new succeeds)
 
    bool isMT() const;
    // Function:  determines whether the stack is empty
    // Pre:  Stack has been initialized
    // Post: Function value = (stack is empty)
 
    void push(T item);
    // Function:  adds item to the top of the stack
    // Pre:  Stack has been initialized
    // Post: If (stack is full), PushOnFullStack exception is thrown;
    //       otherwise, item is at the top of the stack
 
    void pop(T & item);
    // Function: removes top item from the stack and returns it in item
    // Pre:  Stack has been initialized 
    // Post: If (stack is MT), PopOnMTStack exception is thrown;
    //       otherwise, top element has been removed from stack
 
	void prntStack() const;
    // Function: displays contents of the stack  
    // Pre:  Stack has been initialized 
    // Post: Stack is walked and members printed
}; // end Stack
 
// stack.cpp
 
// Stack ADT - implementation using a templated linked list  
 
//#include <cstddef>
//#include <new>
template <class T>
struct Node
{
   T info;                                 //  Node data of type T
   Node * next;               				//  link to next Node
 
   Node<T>() : info(0), next(NULL)			// default c-tor for Node
   { }
 
   Node<T>( const T & e, Node * nx = NULL )  // parameterized c-tor for Node
		: info(e), next(nx) 
   { }
};  // end Node
 
template<class T>
Stack<T>::Stack() : top(NULL)
{ }
 
template <class T>
Stack<T>::~Stack()
{
  Node<T> * temp;
 
  while ( top != NULL )
  {
    temp = top;
    top = top->next;
    delete temp;
  } // endwhile
} // end ~Stack()
 
template<class T>
void Stack<T>::pop(T & item)
{
  if ( isMT() )
    throw PopOnMTStack();
  else
  {  
    Node<T> * temp;
    temp = top;
    item = top->info;
    top = top->next;
    delete temp;
  } // endif
} // end pop()
 
template<class T>
bool Stack<T>::isFull() const
{
  Node<T> * location;
  try
  {
    location = new Node<T>;
    delete location;
    return false;
  } // endtry
  catch(bad_alloc exception)
  {
    return true;
  } // endcatch
} // end isFull()
 
template <class T>
void Stack<T>::push(T item)
{
  if ( isFull() )
    throw PushOnFullStack();
  else
  {  
    Node<T> * ptr;
    ptr = new Node<T>(item);
    ptr->next = top;
    top = ptr;
  } // endif 
} // end push()
 
template <class T>
void Stack<T>::makeMT() 
{
  Node<T> * temp;
 
  while ( top != NULL )
  {
    temp = top;
    top = top->next;
    delete temp;
  } // endwhile
} // end makeMT()
 
template <class T>
bool Stack<T>::isMT() const
{
  return ( top == NULL );
} // end isMT()
 
template <class T>
void Stack<T>::prntStack() const
{
	Node<T> * ptr = top;
	cout << "\n Walking the stack:  "
	while ( ptr != NULL )
	{
		cout << "\t" << ptr->info;
		ptr = ptr->next;
	} // endwhile
 
  return;
} // end prntStack()
 
// stkxcptn.h - header file for PopOnMTStack and PushOnFullStack exception class
 
//#include <iostream>
//using namespace std;
 
class PopOnMTStack
{
  private :
	string msg;
 
  public :
	PopOnMTStack()  		// default c-tor
	{
		msg = string("\n Stack underflow - operation aborted");
	}
	const string message() const
	{
		return msg;
	}
}; // end PopOnMTStack
 
 
class PushOnFullStack
{
  private :
	string msg;
 
  public :
	PushOnFullStack()  		// default c-tor
	{
		msg = string("\n Stack overflow - operation aborted");
	}
	const string message() const
	{
		return msg;
	}
}; // end PopOnMTStack
 
 
// File Tree.h contains the definition of class Tree
// Class is templated
 
//#pragma once
//#include "Queue.h"
//#include "Stack.h"
#include <fstream>
 
const char LAST_SYMBOL = '=';
enum OpType { OPERATOR, OPERAND };
 
struct InfoNode
{
  OpType whichType; 	// Type field
  union 		// Anonymous union
  {
    char operation;
    int operand;
  };
};
 
typedef InfoNode T;
 
template <class T>
struct TreeNode;
// Assumption: T is a type for which the operators "<"
// and "==" are defined - either an appropriate built-in type or
// a class that overloads these operators
 
enum OrderType { PRE_ORDER, IN_ORDER, POST_ORDER };
 
template <class T>
class Tree
{
  private:
    TreeNode<T> * root;
    // The following queues are used for traversals
    Queue<T> preQue;
    Queue<T> inQue;
    Queue<T> postQue;
  public:
    Tree();			// constructor
    ~Tree();		// destructor
    Tree(const Tree<T> & oTree);
    // copy constructor
    void operator=(const Tree<T> & oTree);
    // Overloads the assignment operator
    void makeMT();
    // Function: Initializes tree to the empty state
    // Post: Tree is empty
    bool isMT() const;
    // Function: Determines whether the tree is empty
    // Post: Function value = (tree is empty)
    bool isFull() const;
    // Function: Determines whether the tree is full
    // Post: Function value = (tree is full)
    int numberOfNodes() const;
    // Function: Determines the number of elements in the tree
    // Post: Function value = number of elements in the tree
    void retrieveItem(T & item, bool & found);
    // Function: Retrieves item whose key matches item's key (if present)
    // Pre:  Key of item has been initialized
    // Post: If there is an item someItem whose key matches item's
    //       key, then found is true and item is a copy of someItem;
    //       otherwise found is false and item is unchanged
    //       The tree is unchanged
    void insertItem(T item);
    // Function: Adds item to the tree
    // Pre:  Tree is not full; item is not in the tree
    // Post: item is in the tree
    //       Binary search property is maintained
    void removeItem(T item);
    // Function: Deletes the item whose key matches item's key
    // Pre:  Key of item has been initialized
    //       One and only one item in the tree has a key matching
    //       item's key
    // Post: No element in tree has key matching item's key
    void resetTree(OrderType order);
    // Function: Initializes current position for an iteration
    //           through the tree in order specified
    // Post: Current position is prior to root of the tree
    void getNextItem (T & item, OrderType order, bool & fini);
    // Function: Gets the next element in the tree in the order specified in order
    // Pre:  Current position is defined
    //       Item at current position is not last in the tree
    // Post: Current position is one position beyond current position at entry to getNextItem()
    //       fini = (current position is last in tree)
    //       item is a copy of element at current position
    void printTree(std::ofstream & outFile) const;
    // Function: Prints the values in the tree in ascending key
    //           order on outFile
    // Pre:  outFile has been opened for writing
    // Post: Values in the three have been printed in ascending key order
    //       outFile is still open
	friend void buildExprTree(Tree<T> & expr);
	friend int eval(Tree<T> & expr);
}; // end Tree
 
//#include "Tree.cpp"
 
// Implementation file for Binary Search Tree; 
// recursive insertion and deletion functions
 
 
template <class T>
struct TreeNode
{
  T info;
  TreeNode * left;
  TreeNode * right;
  TreeNode() 			// default c-tor for TreeNode
  { }
};
 
template <class T>
int countNodes(Tree<T> * tree)
// Post: returns the number of nodes in the tree
{
  if (tree == NULL)
    return 0;
  else
    return countNodes(tree->left) + countNodes(tree->right) + 1;
}
 
template <class T>
int Tree<T>::numberOfNodes() const
// Calls recursive function CountNodes to count the
// nodes in the tree
{
  return countNodes(root);
}
 
template <class T>
void retrieve(TreeNode<T> * tree, T & item, bool & found)
// Recursively searches tree for item
// Post: If there is an element someItem whose key matches item's, found
//       is true and item is set to a copy of someItem; otherwise found
//       is false and item is unchanged
{
  if (tree == NULL)
    found = false;                          // item is not found
  else if ( item < tree->info )                 // Search left subtree
    retrieve(tree->left, item, found);      // Search right subtree
  else if ( item > tree->info )
    retrieve(tree->right, item, found);
  else
  {
    item = tree->info;                      // item is found
    found = true;
  }
}
 
template <class T>
void Tree<T>::retrieveItem(T& item, bool& found)
// Calls recursive function Retrieve to search the tree for item
{
  retrieve(root, item, found);
}
 
template <class T>
void insert(TreeNode<T> * & tree, T item)
// Inserts item into tree
// Post:  item is in tree; search property is maintained
{
  if ( tree == NULL )
  {							// insertion place found
      tree = new TreeNode<T>;
      tree->right = NULL;
      tree->left = NULL;
      tree->info = item;
  }
  else if ( item < tree->info )
    Insert(tree->left, item);      // insert in left subtree
  else
    Insert(tree->right, item);     // nsert in right subtree
}
 
template <class T>
void Tree<T>::insertItem(T item)
// Calls recursive function Insert to insert item into tree
{
  insert(root, item);
}
 
template <class T>
void removeNode(TreeNode<T> * & tree)
// Deletes the node pointed to by tree
// Post: The user's data in the node pointed to by tree is no longer in the
//       tree.  If tree is a leaf node or has only non-NULL child pointer
//       the node pointed to by tree is deleted; otherwise, the user's data
//       is replaced by its logical predecessor and the predecessor's node
//       is deleted
{
  T data;
  TreeNode<T>* tempPtr;
 
  tempPtr = tree;
  if ( tree->left == NULL )
  {
    tree = tree->right;
    delete tempPtr;
  }  
  else if ( tree->right == NULL )
  {
    tree = tree->left;
    delete tempPtr;
  }  
  else
  {
    getPredecessor(tree->left, data);
    tree->info = data;
    remove(tree->left, data);       // Delete predecessor node
  }
}
 
template <class T>
void remove(TreeNode<T>*& tree, T item)
// Deletes item from tree
// Post:  item is not in tree
{
  if (item < tree->info )
    remove(tree->left, item);         // Look in left subtree
  else if ( item > tree->info )
    remove(tree->right, item);        // Look in right subtree
  else
    removeNode(tree);                 // Node found; call removeNode
} 
 
template <class T>
void Tree<T>::removeItem(T item)
// Calls recursive function remove() to delete item from tree
{
  remove(root, item);
}
 
template<class T>
void getPredecessor(TreeNode<T> * tree, T & data)
// Sets data to the info member of the right-most node in tree
{
  while ( tree->right != NULL )
    tree = tree->right;
  data = tree->info;
}
 
template <class T>
void Tree<T>::printTree(std::ofstream & outFile) const
// Calls recursive function print() to print items in the tree
{
  print(root, outFile);
}
 
template<class T>
void print(TreeNode<T> * tree, std::ofstream & outFile)
// Prints info member of items in tree in sorted order on outFile
{
  if ( tree != NULL )
  {
    print(tree->left, outFile);             // Print left subtree
    outFile << tree->info;
    print(tree->right, outFile);            // Print right subtree
  }
}
 
template <class T>
Tree<T>::Tree()
{
  root = NULL;
}
 
template<class T>
void destroy(TreeNode<T> * & tree)
// Post: tree is empty; nodes have been deallocated
{
  if ( tree != NULL )
  {
    destroy(tree->left);
    destroy(tree->right);
    delete tree;
  }
}
 
template <class T>
Tree<T>::~Tree()
// Calls recursive function destroy() to destroy the tree
{
  destroy(root);
}
 
template <class T>
void copyTree(TreeNode<T> * & copy, TreeNode<T> * originalTree )
// Post: copy is the root of a tree that is a duplicate
//       of tree pointed to by originalTree
{
  if ( originalTree == NULL )
    copy = NULL;
  else
  {
    copy = new TreeNode<T>;
    copy->info = originalTree->info;
    copyTree(copy->left, originalTree->left);
    copyTree(copy->right, originalTree->right);
  }
}
 
 
template <class T>
Tree<T>::Tree(const Tree<T> & originalTree)
// Calls recursive function copyTree() to copy originalTree into root
{
  copyTree(root, originalTree.root);
}
 
template <class T>
void Tree<T>::operator=(const Tree<T> & originalTree)
// Calls recursive function CopyTree to copy originalTree into root
{
  if ( &originalTree == this )
    return;                       // Ignore assigning self to self
  destroy(root);                    // Deallocate existing tree nodes
  copyTree(root, originalTree.root);
}
 
// Function prototypes for auxiliary functions
template <class T>
void buildExprTree(Tree<T> & expr);
// builds a preorder binary expression tree
 
template <class T>
void preorder(TreeNode<T> *, Queue<T> &);
// Enqueues tree items in preorder
 
template <class T>
void inorder(TreeNode<T> *, Queue<T> &);
// Enqueues tree items in inorder
 
template <class T>
void postorder(TreeNode<T> *, Queue<T> &);
// Enqueues tree items in postorder
 
template <class T>
void Tree<T>::resetTree(OrderType order)
// Calls function to create a queue of the tree elements in
// the specified order
{
  switch ( order )
  {
    case PRE_ORDER : preorder(root, preQue);
		     break;
    case IN_ORDER  : inorder(root, inQue);
		     break;
    case POST_ORDER: postorder(root, postQue);
		     break;
  } // endswitch
}
 
template <class T>
void preorder(TreeNode<T> * tree, Queue<T> & preQue)
// Post: preQue contains the tree items in preorder
{
  if (tree != NULL)
  {
    preQue.enqueue(tree->info);
    preorder(tree->left, preQue);
    preorder(tree->right, preQue);
  }
}
 
template <class T>
void inorder(TreeNode<T>* tree, Queue<T>& inQue)
// Post: inQue contains the tree items in inorder
{
  if ( tree != NULL )
  {
    inorder(tree->left, inQue);
    inQue.enqueue(tree->info);
    inorder(tree->right, inQue);
  } // endif
}
 
template <class T>
void postorder(TreeNode<T> * tree, Queue<T> & postQue)
// Post: postQue contains the tree items in postorder
{
  if (tree != NULL)
  {
    postorder(tree->left, postQue);
    postorder(tree->right, postQue);
    postQue.enqueue(tree->info);
  } // endif
}
 
template <class T>
void Tree<T>::getNextItem(T & item, OrderType order, bool & fini)
// Returns the next item in the desired order
// Post: For the desired order, item is the next item in the queue
//       If item is the last one in the queue, fini is true; otherwise
//       fini is false
{
  fini = false;
  switch ( order )
  {
    case PRE_ORDER : preQue.dequeue(item);
					 if ( preQue.isMT() )
						fini = true;
					 break;
    case IN_ORDER  : inQue.dequeue(item);
					 if ( inQue.isMT() )
						fini = true;
					 break;
    case POST_ORDER: postQue.dequeue(item);
					 if ( postQue.isMT() )
						fini = true;
					 break;
  } // endswitched
}
 
template <class T>
void buildExprTree(Tree<T> & expr) 
{
	buildTree(expr.root);
} 
 
// buildTree.cpp
// buildTree() builds a binary expression tree.
// Note:  operands are restricted to single digits
 
//using namespace std;
 
void buildTree(TreeNode<T> * & tree)
{
  enum MoveType { RIGHT, LEFT };
  MoveType nextMove = LEFT;
 
  TreeNode<T> * nptr = new TreeNode<T>;
  TreeNode<T> * last;
  char symbol;
 
  Stack <TreeNode<T> *> stack;
 
  cin >> symbol;
 
  cout << " operator: " << symbol << endl;  // first symbol is an operator
 
  nptr->info.whichType = OPERATOR;
  nptr->info.operation = symbol;
 
  tree = nptr;
 
  cin >> symbol;			// this version uses single-digit operands
 
  while ( symbol != LAST_SYMBOL )
  {
    last = nptr;
    nptr = new TreeNode<T>;
 
    if ( ispunct(symbol) )
    {
      cout << " operator: " << symbol << endl;
      nptr->info.whichType = OPERATOR;
      nptr->info.operation = symbol;
    }
    else
    {
      cout << "  operand: " << symbol << endl;
      nptr->info.whichType = OPERAND;
      nptr->info.operand = int(symbol - '0');
      nptr->right = NULL;
      nptr->left = NULL;
    } // endif
 
    switch (nextMove)
    {
      case LEFT  :	last->left = nptr;
          			stack.push(last);
 					break;
      case RIGHT :	stack.pop(last);
         			last->right = nptr;
					break;
    } // endswitch
 
    if ( nptr->info.whichType == OPERATOR )
      nextMove = LEFT;
    else 
      nextMove = RIGHT;
    cin >> symbol;
  } // endwhile
  return;
} // end buildTree()
 
 
template <class T>
int eval(Tree<T> & expr) 
{
	return eval(expr.root);
} 
 
// Function to evaluate a binary expression tree.
// Pre:   ptr is a pointer to a binary expression tree
// Post:  Function value = the value of the expression
//		  represented by the binary tree pointed to by ptr
int eval(TreeNode<T> * ptr)
{     
	switch ( ptr->info.whichType ) {        				
		case OPERAND :  
			return  ptr->info.operand;
		case OPERATOR :
			switch ( ptr->info.operation ) {
				case  '+' :  return ( eval(ptr->left) + eval(ptr->right) ); 
 
				case  '-' :  return ( eval(ptr->left) - eval(ptr->right) );
 
 				case  '*' :  return ( eval(ptr->left) * eval(ptr->right) ); 
 
				case  '/' :  return ( eval(ptr->left) / eval(ptr->right) );
 
             } // endswitch
       } // endswitch
} // end eval()
 
//tstexpr.cpp
/* ------------------------------------------------------------------------------
 * program to test binary tree expression evaluation
 * 	CS 320 - Data Structures 	l l craddock		   
 */
 
//#include "tree.h"
 
void main()
 {
	Tree<T> e ;  
 
	cout << "\n Use a Binary Tree for Preorder Expression Evaluation\n" ;
 
	cout << "\n Enter an expression terminated by an equal sign, e.g.:  - * 6 3 5 =\n" ;
 
	buildExprTree(e) ;
 
	cout << "\n The value of the expression is " << eval(e) ;
 
	cout << "\n -- Done --\n" ;
	return ;
 } 
 
/* Sample output:
 
 Use a Binary Tree for Preorder Expression Evaluation
 
 Enter an expression terminated by an equal sign, e.g.:  - * 6 3 5 =
*  -  8 5  /  +  4 2 3 =
 operator: *
 operator: -
  operand: 8
  operand: 5
 operator: /
 operator: +
  operand: 4
  operand: 2
  operand: 3
 
 The value of the expression is 6
 -- Done --                            */

template <class T>
class Tree
{
...
template <class T> friend void buildExprTree(Tree<T> & expr);
template <class T> friend int eval(Tree<T> & expr);
...
};

template <class T>
class Tree
{
...
template <typename T> friend void buildExprTree(Tree<T> & expr);
template <typename T> friend int eval(Tree<T> & expr);
...
};