Good ol binary tree stuff

gistfile1.cpp

//
//  main.cpp
//  Trees
//
//  Created by Jacob Wilson on 3/27/12.
//  Copyright (c) 2012 Weber State. All rights reserved.
//

#include <iostream>
#include <string>
#include <stack>
#include <sstream>

using namespace std;
////////////////////////////////////////////////////////
//// Tree Stuff
////////////////////////////////////////////////////////
template <typename Type> 
class nodeType {
public:
	Type info;
	nodeType<Type> *llink;
	nodeType<Type> *rlink;
    
    nodeType<Type>(){
        this->llink = NULL; 
        this->rlink = NULL; 
    }
    
};

template <typename Type>
class binaryTreeType {
public:
	void inOrderTraversal() { 
		inorder(root); 
	}
    
	void postOrderTraversal() { 
		postorder(root); 
	}
    
    
    
	binaryTreeType();
	//~binaryTreeType();
protected:
	nodeType<Type> *root;
private:
	void inorder(nodeType<Type> *p);
    void postorder(nodeType<Type> *p);
};

template <typename Type> 
binaryTreeType<Type>::binaryTreeType() {
	root = NULL;
}

template <typename Type>
void binaryTreeType<Type>::inorder(nodeType<Type> *p) {
	if (p != NULL) {
		inorder(p->llink);
		cout << p->info << " ";
		inorder(p->rlink);
	}
}

template <typename Type>
void binaryTreeType<Type>::postorder(nodeType<Type> *p) {
	if (p != NULL) {
		postorder(p->llink);		
		postorder(p->rlink);
		cout << p->info << " ";
	}
}



template <typename Type>
class bSearchTreeType : public binaryTreeType<Type> {
public:
	void insert(const Type& insertItem);
	void deleteNode(const Type& deleteItem);
private:
	void deleteFromTree(nodeType<Type>* &p);
};

template <typename Type>
void bSearchTreeType<Type>::insert(const Type& insertItem) {
	nodeType<Type> *current;
	nodeType<Type> *trailCurrent;
	nodeType<Type> *newNode;
	newNode = new nodeType<Type>;
	if (newNode != NULL) {
		newNode->info = insertItem;
		newNode->llink = NULL;
		newNode->rlink = NULL;
		if (this->root == NULL) 
		{				
			this->root = newNode;
		} else {
			current = this->root;
			while (current != NULL) {
				trailCurrent = current;
				//go left or right?
				if (current->info == insertItem) {
					cerr << "Duplicate items are not allowed, dummy!" << endl;
					return;
				} else if (current->info > insertItem) {
					current = current->llink;
				} else {
					current = current->rlink;
				}
			}
			//current is pointing to NULL, and trailCurrent
			//is pointing to the node in which we should place the data
			if (trailCurrent->info > insertItem) {
				trailCurrent->llink = newNode;
			} else {
				trailCurrent->rlink = newNode;
			}
		}		
	}
}

template <class Type>
void bSearchTreeType<Type>::deleteNode(const Type& deleteItem) {
	nodeType<Type> *current;
	nodeType<Type> *trailCurrent;
	bool found = false;
    
	if (this->root == NULL) {
		cerr << "Can't delete from an empty tree!" << endl;
	} else {
		current = this->root;
		trailCurrent = this->root;
		while (current != NULL && !found) {
			if (current->info == deleteItem) {
				found = true;
			} else {
				trailCurrent = current;
				if (current->info > deleteItem) {
					current = current->llink;
				}else {
					current = current->rlink;
				}
			}
		}
		if (current == NULL) {
			cerr << "The item wasn't even in the list at all!" << endl;
		} else {
			if (current == this->root) 
				deleteFromTree(this->root);
			else if (trailCurrent->info > deleteItem) {
				deleteFromTree(trailCurrent->llink);
			} else {
				deleteFromTree(trailCurrent->rlink);
			}
		}
	}
}

template <class Type>
void bSearchTreeType<Type>::deleteFromTree(nodeType<Type>* &p){
    
	nodeType<Type> *current;
	nodeType<Type> *trailCurrent;
	nodeType<Type> *temp;
    
	if (p == NULL) {
		cerr << "The node to be deleted is NULL" << endl;
	} else if (p->llink == NULL && p->rlink == NULL) {
		temp = p;
		p = NULL;
		delete temp;
	} else if (p->llink == NULL) {
		//right link has children
		temp = p;
		p = temp->rlink;
		delete temp;
	} else if (p->rlink == NULL) {
		temp = p;
		p = temp->llink;
		delete temp;
	} else {
		current = p->llink;
		trailCurrent = NULL;
		while (current->rlink != NULL) {
			trailCurrent = current;
			current = current->rlink;
		}
		p->info = current->info;
		if (trailCurrent == NULL)  {// we never went to the right any
			p->llink = current->llink;
		} else {
			trailCurrent->rlink = current->llink;
		}
		delete current;
	}
}
////////////////////////////////////////////////////////
//// End Tree Stuff
////////////////////////////////////////////////////////
class mathProcessor : public binaryTreeType<string>{
private:
    stack<string> theStack; 
    void reset(); 
    double convertStringToDouble(const string &s); 
    string convertDoubleToString(const double d); 
    
    bool isDigit(char c); //Done
    bool isOperator(char c); 
    void processExpression(nodeType<string> *p); 
    void compute(nodeType<string> *p); 
    
protected:
    string expression; 
    int position; 
    
public:
    mathProcessor();    
    void displayStatus(); 
    void processExpression (string &expression); 
    double compute(); 
    
    
}; 
void mathProcessor::processExpression(nodeType<string> *p){
    if(expression[position] == '('){
        p->llink = new nodeType<string>; 
        this->position++; 
        processExpression(p->llink); 
    }
    if(isDigit(expression[position])){
        
        while(isDigit(expression[position])){
            
            p->info += expression[position]; 
            
            this->position++; 
        }
        return;    
    } if(isOperator(expression[position])){
        
        p->info = expression[position]; 
        this->position++; 
        
        p->rlink = new nodeType<string>; 
        processExpression(p->rlink); 
    }
    if(expression[position] == ')'){
        this->position++; 
        return; 
    }
    
    
}
void mathProcessor::processExpression(string &myexpression){
    if(&myexpression == NULL){
        cerr << "You suck at everything" << endl; 
        
    }else{
        expression = myexpression; 
        root = new nodeType<string>; 
        processExpression(root); 
    }
}
double mathProcessor::compute(){
    this->compute(root); 
    double answer = convertStringToDouble(theStack.top());
    this->reset(); 
    return answer; 
}
void mathProcessor::compute(nodeType<string> *p){
 	if (p != NULL) {
		compute(p->llink);		
		compute(p->rlink);
		if(isOperator(p->info[0]))
		{
			double right = convertStringToDouble(theStack.top());
			theStack.pop();
			double left = convertStringToDouble(theStack.top());
			theStack.pop();
            switch(p->info[0]){
                case '/':
                theStack.push(convertDoubleToString((left/right)));
                    break; 
                case '-':
                theStack.push(convertDoubleToString((left-right)));
                    break;
                case '+':
                theStack.push(convertDoubleToString((left+right)));    
                    break;
                case '*':
                theStack.push(convertDoubleToString((left*right)));        
                    break;
                default: cerr << "Something went wrong. " << endl; 
            }
		}
		else{
			theStack.push(p->info);
		}
	}

    
    
    
 
    
}
bool mathProcessor::isDigit(char c){
    
    switch (c){
        case '0':
            return true; 
            break; 
        case '1':
            return true; 
            break; 
        case '2': 
            return true; 
            break; 
        case '3':
            return true; 
            break; 
        case '4':
            return true; 
            break; 
        case '5': 
            return true; 
            break; 
        case '6':
            return true; 
            break; 
        case '7': 
            return true; 
            break; 
        case '8':
            return true; 
            break; 
        case '9':
            return true; 
            break; 
    default: 
            return false; 
            break; 
    }

    
}

bool mathProcessor::isOperator(char c){
    switch (c){
        case '*':
            return true; 
            break;
        case '/':
            return true; 
            break; 
        case '+':
            return true; 
            break; 
        case '-':
            return true; 
            break; 
        default:
            return false;
            break; 
    }
}
void mathProcessor::reset() {
	expression = "";
	position = 0;
	theStack.empty();
    
}

double mathProcessor::convertStringToDouble(const string &s) {
	istringstream iss(s);
	double x;
	iss >> x;
	return x;
} 

string mathProcessor::convertDoubleToString(const double d) {
	ostringstream oss;
	oss << d;
	return oss.str();
    
} 

mathProcessor::mathProcessor() {
	reset();
}


void mathProcessor::displayStatus() {
	cout << "The data in an in-order traversal is: "; 
	inOrderTraversal();
	cout << endl;
	cout << "The data in an post-order traversal is: "; 
	postOrderTraversal();
	cout << endl;
	
}

int main() {
	mathProcessor *mp = new mathProcessor;
	string expression = "(2+3)";
	mp->processExpression(expression);
	mp->displayStatus();
	cout << "The result is: " << mp->compute() << endl; //Should display 5

	expression = "(123+456)";
	mp->processExpression(expression);
	mp->displayStatus();
    cout << "The result is: " << mp->compute() << endl; //Should display 579
	expression = "(8-5)";
	mp->processExpression(expression);
	mp->displayStatus();
	cout << "The result is: " << mp->compute() << endl; //Should display 3
	expression = "((3-4)-5)";
	mp->processExpression(expression);
	mp->displayStatus();
	cout << "The result is: " << mp->compute() << endl; //Should display -6
	expression = "(3*(8/2))";
	mp->processExpression(expression);
	mp->displayStatus();
	cout << "The result is: " << mp->compute() << endl; //Should display 12
	expression = "((((3+12)-7)*120)/(2+3))";
	mp->processExpression(expression);
	mp->displayStatus();
	cout << "The result is: " << mp->compute() << endl; //Should display 192
	expression = "(((((9+(2*(110-(20/2))))*8)+1000)/2)-((400*2500)-1000001))";
	mp->processExpression(expression);
	mp->displayStatus();
	cout << "The result is: " << mp->compute() << endl; //Should display 1337

	return 0;
}