// btreeEx.h
 
// queue.h
// linked list implementation of Queue ADT
#include <cstddef>		 	// for NULL
#include <new>				// for bad_alloc exception
#include <iostream>
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
 
 
// 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
 
// 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 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()
 
 
// file tree.h contains the definition of class Tree
// class is templated
 
#include <fstream>
#include <cmath>				// for pow()
#include <string>				// Assign #19
const char LAST_SYMBOL = '='; 
enum OpType { OPERATOR, OPERAND };
struct InfoNode
{
  OpType whichType; 	// type field
  union 			// anonymous union
  {
    char operation;
    double operand;	// Assign #19 - change type from int to double
  };
};
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
	template <class T>
	friend void buildExprTree(Tree<T> & expr);
	template <class T>
	friend double 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 nodes in the tree
  return countNodes(root);
}
 
// 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
template <class T>
void retrieve(TreeNode<T> * tree, T & item, bool & found)
{
  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;
  } // endif
}
 
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>
// Deletes the node pointed to by tree
// Post: 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
void removeNode(TreeNode<T> * & tree)
{
  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
  } // endif
}
 
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;
  } // endif
}
 
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> * origTree )
{     // Post: copy is root of a tree that is a dup of tree pointed to by origTree
  if ( origTree == NULL )
    copy = NULL;
  else {
    copy = new TreeNode<T>;
    copy->info = origTree->info;
    copyTree(copy->left, origTree->left);
    copyTree(copy->right, origTree->right);
  } // endif
}
 
template <class T>
Tree<T>::Tree(const Tree<T> & origTree)
{     // calls recursive function copyTree() to copy origTree into root
  copyTree(root, origTree.root);
}
 
template <class T>
void Tree<T>::operator=(const Tree<T> & origTree)
{     // calls recursive function CopyTree to copy origTree into root
  if ( &origTree == this )
    return;                       // Ignore assigning self to self
  destroy(root);                  // Deallocate existing tree nodes
  copyTree(root, origTree.root);
}
 
  // function prototypes for auxiliary functions
template <class T>
void buildExprTree(Tree<T> & expr);  // builds 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 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);
  } // endif
}
 
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
}
 
// 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
template <class T>
void Tree<T>::getNextItem(T & item, OrderType order, bool & fini)
{
  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;
  } // endswitch
}
 
void parseStr(string s, char & sym, double & d);  // Assign #19 - prototype
 
template <class T>
void buildExprTree(Tree<T> & expr) 
{
	buildTree(expr.root);
} 
 
// buildTree.cpp
// buildTree() builds a binary expression tree
// Note:  operands are NOT restricted to single digits 	 
void buildTree(TreeNode<T> * & tree)
{
  string inStr;			// Assign #19
  double opnd;			// Assign #19
 
  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 operator
  nptr->info.whichType = OPERATOR;
  nptr->info.operation = symbol;
  tree = nptr;
    // instead of 
    // cin >> symbol; // this version uses single-digit operands – we have
  cin >> inStr;				// Assign #19 - uses type double operands
  parseStr(inStr, symbol, opnd);	// Assign #19
 
  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;
	  cout << "  operand: " << opnd << endl;	// Assign #19
	  nptr->info.whichType = OPERAND;
		//nptr->info.operand = int(symbol - '0');
	  nptr->info.operand = opnd;			// Assign #19
	  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;
						  // instead of cin >> symbol;
	 cin >> inStr;			  // Assign #19 - uses type double operands
	 parseStr(inStr, symbol, opnd);	// Assign #19
  } // endwhile
  return;
} // end buildTree()
 
void parseStr(string s, char & sym, double & d)	 	// Assign #19 
{
	const char * p = s.c_str();	// convert to C-style string
	if ( p[0] == '+' || p[0] == '^' || p[0] == '/' || p[0] == '*' || 
		p[0] == '-' || p[0] == LAST_SYMBOL )  {	 // symbol is an operator
		sym = p[0];
		d = 0.0;
	} // endif-thenpart
	else {				// input is type double operand
		d = atof(p);	// convert input to type double operand
		sym = '1';		// can make symbol any non-operator
	} // endif-elsepart
} // end parseStr()
 
template <class T>			//int eval(Tree<T> & expr) 
double eval(Tree<T> & expr)		// Assign #19
{
	return eval(expr.root);
} 
 
// 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)
double eval(TreeNode<T> * ptr)	// Assign #19
{     // function to evaluate a binary expression tree
   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) );
 
		case '^' : return ( pow(eval(ptr->left), eval(ptr->right)) );
         } // endswitch
	} // endswitch
	return 0.0;
} // end eval()
 
//tstexpr.cpp
/* ------------------------------------------------------------------------------
 * program to test binary tree expression evaluation
 * 	CS 320 - Data Structures 		   
 */
 
#include "btreeEx.h"
void main()
 {
	Tree<T> e;  
 
	cout << "\n Use a Binary Tree for Preorder Expression Evaluation\n";
	cout << "\n Enter expression terminated by an equal sign, e.g.:  - * 6.2 3.1 5.8 =\n";
 
	buildExprTree(e);
	cout << "\n The value of the expression is " << eval(e);
 
	cout << "\n -- Done --\n";
	return;
 }

^ ^ 2 3 4 = 2^81

^ 2 ^ 3 4 = ?

* = Operand or operator not applicable

* ^ ^ 2 3 4 *

Find adjacent operators:
* ^ ^ 2 3 4 *

Count the operands that apply:
* ^ ^ 2 3 4 *

Move the operators to postfix position:
* 2 3 4 ^ ^ *

Evaluate:
Push 2
Push 3
Push 4
Found ^: Pop 4, 3, Evaluate
Push 81
Found ^, Pop 81, 2, Evaluate
Push 2^81