#include <iostream>
#include <conio>
#include <ctype>
#include <string>
#include "binary_tree.h"
using namespace std;

template <class E> BinaryTree<E>* buildTree(char *infix, int pos);
	
int main(){
	BinaryTree<char> mytree;
	char dummy, yesOrNo;
	char *infix;
	
	do{
		clrscr();
		infix[0] = '\0';
		cout << "Infix Program (Binary Trees)\n\n";
		cout << "Give me a string in infix form <example: (4 + (4 * 5) / 6) ^ 2)>\r\n";
		cout << "\nInfix Expression: "; 
		cin >> dummy >> infix;
		
		mytree = buildTree(infix, 0);
		
		//traversePostOrder();
		
		getch();
	
		cout << "\nWould you like to evaluate more expressions (Y or N): ";
		
		do{
			cin >> yesOrNo;
		}while ((tolower(yesOrNo) != 'y') && (tolower(yesOrNo) != 'n'));
		
	}while (tolower(yesOrNo) == 'y');

	return 0;
}


template <class E> BinaryTree<E>* buildTree(char *infix, int pos){
	BinaryTree *root;
	char next;
	
	for(pos; pos < strlen(infix) - 1; pos++){
		next = infix[i];
		
			if (next == '(')
				root -> left = buildTree(infix, ++pos);
			
			else{
				root -> left = new BinaryTree;	  
				root -> left -> data = (next - 48);
			}
			
			pos++;
			next = infix[i];
			
			 if (next == '(')
			 	root -> right = buildTree(infix, ++pos);
			
			 else{
			 	root -> right = new BinaryTree;
				root -> right -> data = (next - 48);
			} 
			
	}
	
	return root;
}

//Binary Tree header file.


#ifndef BINARY_TREE_H
#define BINARY_TREE_H


template <class E> struct node{
    E data;       //data unit of any given datatype
    node<E> *left;   //pointer to a "lesser-than" child             
    node<E> *right;  //pointer to a "greater-than" child          
};


template <class E> class BinaryTree{

	public:             
    	BinaryTree();       //default constructor, sets root to NULL
		~BinaryTree();      //default destructor (memory leaks are bad)                   
      
		bool isEmpty(const node<E> *&root); 
		bool insert(node<E> *&root, const E &data);        //insert a node into the tree
        bool remove(node<E> *&root, const E &data);     //checks if a node can be deleted
		
		
		
		void traverseInOrder(node<E> *root);
		void traversePreOrder(node<E> *root);
		void traversePostOrder(node<E> *root);
                          
	private:
    	node<E> *root;              //the root of the tree      
};

	

#include "binary_tree.cpp"
#endif

//Binary Tree implementation

template <class E> BinaryTree<E>::BinaryTree(){
	root = NULL;
}


template <class E> BinaryTree<E>::~BinaryTree(){   
	//delete node<E>;
} 

template <class E> bool BinaryTree<E>::isEmpty(const node<E> *&root){
	
	if (!root)
		return true;
		
	else
		return false;
}


template <class E> bool BinaryTree<E>::insert(node<E> *&root, const E &data){
	
	if (!root){
		node<E> *temp = new node;
		
		if (!temp)               //memory couldn't be allocated, node can't be inserted
			return false;
			
		temp -> data = data;
		temp -> left = NULL;
		temp -> right = NULL;
		root = temp;
		return true;             //successful
	}
	
	if (data <= root -> data)
		return insert(root -> left, data);         //recurse to the left
	
	else if (data > root -> data)
		return insert(root -> right, data);        //recurse to the right
	
}


template <class E> bool BinaryTree<E>::remove(node<E> *&root, const E &data){
	
	if (!root)                 //base case, tree is empty
		return false;
	
	if (data == root -> data){      //found node to be removed
		node *oldroot = root;       //first save-root, points to removal-node
		//Case 1 - one or no children
		
		if (root -> left == NULL)          //no left child
			root = root -> right;
		
		else if (root -> right == NULL)    //no right child
			root = root -> left;
			
		if (oldroot != root){		//if one of the above is true
			delete oldroot;
			return true;	
		}  //root is reassigned, node to be removed is deleted
		
		node<E>* parent = root;
		node<E>* next = root -> right;
		
		while (next -> left){	//navigate right to smallest
			parent = next;
			next = next -> left;
		}
		
		if (parent == root)		//unlink this node from the tree
			root -> right = next -> right;
			
		else
			parent -> left = next -> right;
			
		next -> left = root -> left;   //Make this element the new root	
		next -> right = root -> right;
		delete root;
		root = next;
		return true;   
	}	 
	
	else if (data <= root -> data);
		return remove(root -> left, data);
	
	else if (data > root -> data)
		return remove(root -> right, data);
	
}


template <class E> void BinaryTree<E>::traverseInOrder(node<E> *root){
	
	if (!root)		//test first to see if done
		return;
		
	traverseInOrder(root -> left);
	cout << root -> data << " ";	
	traverseInOrder(root -> right);	   
}


template <class E> void BinaryTree<E>::traversePreOrder(node<E> *root){
	
	if (!root)		//test first to see if done
		return;
		
	cout << root -> data << " ";		
	traversePreOrder(root -> left);
	traversePreOrder(root -> right);	
}


template <class E> void BinaryTree<E>::traversePostOrder(node<E> *root){
	
	if (!root)		//test first to see if done
		return;
		
	traversePostOrder(root -> left);
	traversePostOrder(root -> right);
	cout << root -> data << " ";	
}

template <class E> BinaryTree<E>* buildTree(char *infix, int pos);
	
int main(){
	BinaryTree<char> mytree;
	char dummy, yesOrNo;
	char *infix;
	
	do{
		clrscr();
		infix[0] = '\0';
		cout << "Infix Program (Binary Trees)\n\n";
		cout << "Give me a string in infix form <example: (4 + (4 * 5) / 6) ^ 2)>\r\n";
		cout << "\nInfix Expression: "; 
		cin >> dummy >> infix;
		
		mytree = buildTree<char>(infix, 0);
		
		//traversePostOrder();
		
		getch();
	
		cout << "\nWould you like to evaluate more expressions (Y or N): ";
		
		do{
			cin >> yesOrNo;
		}while ((tolower(yesOrNo) != 'y') && (tolower(yesOrNo) != 'n'));
		
	}while (tolower(yesOrNo) == 'y');

	return 0;
}


template <class E> BinaryTree<E>* buildTree(char *infix, int pos){
	BinaryTree<E> *root;