Binary Tree Revisited: Near Completion

This is a discussion on Binary Tree Revisited: Near Completion within the C++ Programming forums, part of the General Programming Boards category; With the help of Nick I am coming very close to being able to insert data into this binary tree... ...

  1. #1
    Registered User
    Join Date
    Oct 2002
    Posts
    155

    Binary Tree Revisited: Near Completion

    With the help of Nick I am coming very close to being able to insert data into this binary tree... yet some parts still refuse to work.

    Here is the entire code segment thus far


    Code:
    #include <iostream>
    #include <ctype>
    #include <conio>
    using namespace std;
    
    
    struct Token {
        char type;
        double val;
    };
    
    
    struct node{
    	node();
    	char data;
    	node *left, *right;
    };
    
    
    node::node(){
    	left = NULL;
    	right = NULL;
    }
    
    
    void read_next_token(Token &next_token);
    node* start(Token &next_token);
    node* expr(Token &next_token);
    node* term(Token &next_token);
    node* factor(Token &next_token);
    void traverseInOrder(node *root);
    
    
    int main(){
        node* val;
    	Token next_token;
    	
    	cout << "Parenthesized Infix equation: ";
    	
        read_next_token(next_token);   
        val = start(next_token);       
        cout << "Result = ";
    	traverseInOrder(val);
    	getch();
        return 0;
    }  //end main
            
    
    void read_next_token(Token &next_token){
        double c;
    
        c = cin.get();    //doesn't require an enter press
    
        if (isdigit(c)) {
            next_token.type = '#';         
            next_token.val  = c - 48;    //to get rid of the ascii value offset
            return;
        }
    	
    	next_token.type = char(c);   
    }  
    
    
    node* start(Token &next_token){
        node* val = expr(next_token);  
        return val;                     
    }
    
    
    node* expr(Token &next_token){
        node* val = new node;
    
        if (val -> left == NULL)
       				val -> left = term(next_token);
    			else
    				val -> right = term(next_token); 
    	   
    	
        switch(next_token.type){
    	
    	    case '+':
    		case '-':
    	        read_next_token(next_token);
    	        if (val -> left == NULL)
       				val -> left = expr(next_token); 
    			else
    				val -> right = expr(next_token); 
    	        break;
    	     
    			
    	 
    			
    	    default:
    	        break;
        }
     
        return val;
    }
    
    
    node* term(Token &next_token){
        node* val = new node;
    	//zerotest;
    
    	if (val -> left == NULL)
        val -> left = factor(next_token);
    	else
    	val -> right = factor(next_token); 
    	
        switch(next_token.type){
    	
    	    case '*':
    		case '/':
    	        read_next_token(next_token);  //get the next inputted letter
    			
    	        if (val -> left == NULL)
       				val -> left = term(next_token); 
    			else
    				val -> right = term(next_token); 
    	        break;
    			
    	
    			
    	    default:
    	        break;
        }
    
        return val;
    }
        
    
    node* factor(Token &next_token){
        node* val = new node;
        
        switch(next_token.type){
    	
    	    case '#':                         //if the type of the token is a number
    	        val -> data = char(next_token.val);       
    	        read_next_token(next_token);  //get the next inputted letter
    	        break;
    			
    	    case '(':            //the only other thing it can be here is a (
    	        read_next_token(next_token);  //get the next inputted letter
    	        if (val -> left == NULL)
       				val -> left = expr(next_token); 
    			else
    				val -> right = expr(next_token); 
    	        read_next_token(next_token);  //get the next inputted letter
    	        break;
    			
    	    default:
    	        break;
        }
        
        return val;  
    }
    
    
    void traverseInOrder(node *root){
    	
    	if (!root)		//test first to see if done
    		return;
    		
    	traverseInOrder(root->left);
    	cout << root->data << " ";	
    	traverseInOrder(root->right);	   
    }

    Nick: Now I understand how this "descended recurse" works. Very spiffy :P Unfortunately I am now having trouble converting this to the node insertions. Anyone able to tell me why I am not able to view the data I desire when I do an inOrder traversal? Perhaps I am not inserting correctly...
    Last edited by Nakeerb; 01-20-2003 at 11:28 PM.

  2. #2
    Registered User
    Join Date
    Oct 2002
    Posts
    155
    Alright there we go. Alignments fixed

  3. #3
    Registered User
    Join Date
    Oct 2002
    Posts
    155
    Does this have anything to do with checking for left?

  4. #4
    Blank
    Join Date
    Aug 2001
    Posts
    1,034
    In each function you just look at the different cases
    that can arise and return a tree representing them.
    You only need to use the constructor
    node(char data, node* left, node* right). This way
    you return a tree even if it has incorrect data.

    In most of the functions all you need is
    node* root, *right, *left. So for example if your
    parsing 5 + 6 in expr you would create a tree for it by
    doing
    left = term();
    right = expr();
    root = new node('+', left, right);

    Be aware that if your just parsing
    4;
    your function must basically do
    left = term();
    root = left;
    This will go through the default case in expr and term.
    Last edited by Nick; 01-21-2003 at 12:47 AM.

  5. #5
    Its not rocket science vasanth's Avatar
    Join Date
    Jan 2002
    Posts
    1,683
    i dint go through your entire program.. but i feel your traversal is wrong... You have to start from the root but display it only after the leaf node is done etc.. fro different taversal...



    example
    Code:
    FOR PRE ORDER DISPLAY
    
    tree::predisplay(node *te)
    {
    
    cout<<"\n"<<te->key;
    
    if(te->left!=NULL)
    predisplay(te->left);
    
    if(te->right!=NULL)
    predisplay(te->right);
    
    return SUCCESS;
    }
    
    
    POST ORDER DISPLAY
    
    tree::postdisplay(node *te)
    {
    
    if(te->left!=NULL)
    postdisplay(te->left);
    
    if(te->right!=NULL)
    postdisplay(te->right);
    
    cout<<"\n"<<te->key;
    
    return SUCCESS;
    }
    
    
    INORDER DISPLAY
    tree::indisplay(node *te)
    {
    
    if(te->left!=NULL)
    indisplay(te->left);
    
    cout<<"\n"<<te->key;
    
    if(te->right!=NULL)
    indisplay(te->right);
    
    
    
    return SUCCESS;
    }


    so all these functions are called with the root as argument.. and what is !root supposed to do...

  6. #6
    Blank
    Join Date
    Aug 2001
    Posts
    1,034
    His traversal is correct. As long as the tree is formed
    correctly it should run. But I think passing next_token
    into each function is ugly. Better to use a class or use
    a global variable.

    You should probably skip white space at the beginning of
    read_next_token and I'm not sure why you are using double c. Try to test each function in isolation. Simply test read_next_token then test factor, term, expr in that order.

  7. #7
    Registered User
    Join Date
    Jan 2003
    Posts
    1
    Nakeerb here, temporary name.

    Nick, then is all the new code I wrote a waste? I understand how you mean but I have a feeling I'd have to clean up SO much code to get it working. The ( and ) are not supposed to be part of the binary tree at all. only numbers and operators, and all evaluations are FULLY parenthesized.

    As in you'll never see (3 + 2 + (4 + 5)), it'd be ((3 + 2)+(4+5))



    However, I have too much crappy code written in alerady. What would I do in place of something such as this:

    Code:
     switch(next_token.type){
    	
    	    case '#':                         //if the type of the token is a number
    	        val -> data = char(next_token.val);       
    	        read_next_token(next_token);  //get the next inputted letter
    	        break;
    			
    	    case '(':            //the only other thing it can be here is a (
    	        read_next_token(next_token);  //get the next inputted letter
    	        if (val -> left == NULL) //EQUAL TERMS YOU FOOL
       				val -> left = expr(next_token); 
    			else
    				val -> right = expr(next_token); 
    	        read_next_token(next_token);  //get the next inputted letter
    	        break;
    			
    	    default:
    	        break;
        }
    If you can help me with this function I will do the rest. I am just totally lost. Do I need to declare two node pointers *val and *root? Or declare root when I... auugh! I couldn't sleep last night because of this stupid binary tree problem O.o;;

    when you say left, I assumed you meant a temp node's left is equal. Then you pass the temp node's left into the constructor... oyyy, no idea.

  8. #8
    Blank
    Join Date
    Aug 2001
    Posts
    1,034
    Code:
    switch(next_token.type){
        case '#':                         //if the type of the token is a number
            val -> data = char(next_token.val);       
            read_next_token(next_token);  //get the next inputted letter
            break;
        case '(':            //the only other thing it can be here is a (
            read_next_token(next_token);  //get the next inputted letter
            if (val -> left == NULL) //EQUAL TERMS YOU FOOL
    	val -> left = expr(next_token); 
            else
    	val -> right = expr(next_token); 
    	 read_next_token(next_token);  
                     break;
            default:
                     break;
    }
    You could do something like this
    Code:
    node* factor(Token &next_token){
        node* root = NULL;
         
        switch(next_token.type){
        case '#':                         
               root = new node(next_token.val, NULL, NULL);       
               read_next_token(next_token);  
               break;
         case '(':           
               read_next_token(next_token); 
               root = expr(next_token); 
               read_next_Token(next_token);
         default:
               break;
        }
        
        return root;  
    }
    Last edited by Nick; 01-21-2003 at 02:51 PM.

  9. #9
    Registered User
    Join Date
    Oct 2002
    Posts
    155
    So I can do this for all functions? When would I need to append to right side or left?

  10. #10
    Blank
    Join Date
    Aug 2001
    Posts
    1,034
    This is just for factor. The functions like expr there
    are cases where you would set root = term() (this is
    in the default cases) and there
    are cases where you would do something like
    node* left = term();
    node* right = expr();
    root = node('+', left, right)

  11. #11
    Registered User
    Join Date
    Oct 2002
    Posts
    155
    I rewrote another program that does the same based on the psuedocode I was given today at around noon. However it still does not work. I know I am going off on an extreme tangent by posting this, but any help would be appreciated.

    Code:
    #include <iostream>
    #include <conio>
    #include <ctype>
    #include <cstdlib>
    using namespace std;
    
    class BinaryTree{
    	public:
    		
    		~BinaryTree(){
    		
    			if (left != NULL)
    				delete left;
    				
    			if (left != NULL)
    				delete right;
    				
    		}
    		
    	BinaryTree *left;     //pointer to a left subtree
    	BinaryTree *right;    //pointer to a right subtree
    	char data;            //node data
    };
    
    BinaryTree* buildTree(char *infix, int &pos);
    void preOrderTraverse(BinaryTree *root);
    void postOrderTraverse(BinaryTree *root);
    double evaluate(BinaryTree *root);
    bool isOperator(char ch);
    void changecolor(char* word, int color);
    void flushin();
    
    
    int main(){
    	char infix[50], yesOrNo;
    	BinaryTree *tree;
    	int pos = 1;
    	
    	do{
    		clrscr();
    		changecolor("Binary Expression Tree\r\n\r\n", LIGHTGREEN);
    		cout << "Give me a <fully> parenthesized infix equation: \n";
    		changecolor("\r\nInfix Expression: ", WHITE); 
    		cin.getline(infix, '\n');
    		cout << endl << endl;
    		
    		tree = buildTree(infix, pos);      //inserts infix expression into a binary tree
    		cout << "Prefix form of infix: "; 
    		preOrderTraverse(tree);            //outputs prefix form of infix
    		cout << "\nPostfix form of infix: "; 
    		postOrderTraverse(tree);           //outputs postfix form of infix
    		 
    		cout << "\n\nEvaluation of tree: ";
    		evaluate(tree);
    		
    		delete tree;   //returns the memory to the heap
    		
    		cout << "\nAgain? ";
    		
    		do{
    			cin.get(yesOrNo);
    		}while((tolower(yesOrNo) != 'y') && (tolower(yesOrNo) != 'n'));
    		
    		flushin();   //clear input buffer
    	}while(tolower(yesOrNo) == 'y');
    	
    	return 0;
    }
    
    
    BinaryTree* buildTree(char *infix, int &pos){
    	BinaryTree *root = new BinaryTree;
    	
    	if(infix[pos] == '(')
    		root -> left = buildTree(infix, ++pos);    //recursive call: builds a subtree to the left
    	
    	else{
    		root -> left = new BinaryTree;
    		cout << infix[pos] << " being added to left branch...\n";
    		root -> left -> data = infix[pos];         //assigns data unit
    	}
    	
    	pos++;                        //so we are able to get the next character of infix
    	root -> data = infix[pos];    //assigns the operator to the root's data character
    	pos++;                        //so we are able to get the next character of infix
    	
    	if (infix[pos] == '(')
    		root -> right = buildTree(infix, ++pos);   //recursive call: builds a subtree to the right
    	
    	else{
    		root -> right = new BinaryTree;
    		cout << infix[pos] << " being added to right branch...\n";
    		root -> right -> data = infix[pos];
    	}
    	
    	pos++;       //skip over the ending ) bracket
    	return root;
    		
    }
    
    
    void preOrderTraverse(BinaryTree *root){
    	cout << (root -> data);			   //output the data of the root
    	
    	if (root -> left)
    		preOrderTraverse(root -> left);  //traverse down to the left side of the tree
    		
    	if (root -> right)	  
    		preOrderTraverse(root -> right); //traverse down to the right side of the tree	
    }
    
    
    void postOrderTraverse(BinaryTree *root){	 
    
    	if (root -> left)
    		postOrderTraverse(root -> left);  //traverse down to the left side of the tree
    	
    	if (root -> right)	 	 
    		postOrderTraverse(root -> right); //traverse down to the right side of the tree
    		
    	cout << (root -> data);	      //output the data of the root
    }
    
    
    double evaluate(BinaryTree *root){
    	double temp, divisor;
    	
    	if (isdigit(root -> data))       //if the data character is a number
    		temp = (root -> data) - 48;  //convert it's ascii value to a format a double can recognize
    		
    		
    	if (isOperator(root -> data)){   //if the data character is an operator
    	
    		switch (root -> data){   //apply the operator to the left and right values using inorder recursive traversal
    			case '+': temp = evaluate(root -> left) + evaluate(root -> right); break;
    			case '-': temp = evaluate(root -> left) - evaluate(root -> right); break;
    			case '*': temp = evaluate(root -> left) * evaluate(root -> right); break;
    			case '/':
    				divisor = evaluate(root -> right);
    				
    				if (divisor == 0){   //cannot divide by 0
    					cout << "\nDivide by 0 error.\n";
    					exit(1);
    				}
    				
    				else
    					temp = evaluate(root -> left) / divisor;
    					
    				break;
    				
    			case '^':	 temp = pow(evaluate(root -> left), evaluate(root -> right)); break;
    			default: cout << "\nError, operator unknown\n"; break;	
    			  
    		}
    	
    	}	 
    		
    	return temp;
    }
    
    
    bool isOperator(char ch){
    	string acceptedOperators = "+-*/^";
    	
    	if(acceptedOperators.find(ch, 0) != string::npos)    //if ch can't be found in the string
    		return true;
    		
    	else
    		return false;
    		
    } //end bool isOperator
    
    
    void changecolor(char* word, int color){
    	textcolor(color); 		 //changes text to the color given through the argument
    	cprintf("%s", word);	   	    //outputs the string in the given color
    	//cprintf(word);
    	textcolor(LIGHTGRAY);	 //change color back to the default light gray
    } //end void changecolor
    
    
    void flushin(){
    
    	while (cin.get() != '\n'){}
    	
    } //end void flushin

  12. #12
    Blank
    Join Date
    Aug 2001
    Posts
    1,034
    It took me only about 10 minutes
    to add the few lines to build the tree (:

    These are the two most important functions to build the
    tree the rest of the functions follow the same form.

    Code:
    Node* term()
    {
        Node* root, *left, *right;
        
        left = factor();
    
        switch(next_token.type) {
        case MULTIPLY:
            match(MULTIPLY);
            right = term();
            root = new Node('*', left, right);
            break;
        case DIVIDE:
            match(DIVIDE);
            right = term();
            root = new Node('/', left, right);
            break;
        default:
            root = left;
            break;
        }
    
        return root;
    }
        
    
    Node* factor()
    {
        Node* root = 0;
        
        switch(next_token.type) {
        case NUMBER:
            root = new Node('0' + next_token.val, 0, 0);
            match(NUMBER);
            break;
        case LEFT_PARAN:
            match(LEFT_PARAN);
            root = expr();
            match(RIGHT_PARAN);
            break;
        default:
            break;
        }
        
        return root;
    }

  13. #13
    Registered User
    Join Date
    Oct 2002
    Posts
    155
    Code:
    //This is the header file "binary_tree.h"
    
    
    //===========================/=/=/=/=/=/=/=========================//
    //                            STRUCTURES                           //
    //===========================/=/=/=/=/=/=/=========================//
    
    #ifndef BINARY_TREE_H
    #define BINARY_TREE_H
    
    
    struct BinaryTree{    //contains the neccessary functions and data for a functioning binary expression tree
    
    	BinaryTree();   //Default constructor
    	//Precondition: Object has been declared with no arguments
    	//Postcondition: The left and right pointers have been set to NULL
    	
    	~BinaryTree();  //Destructor
    	//Precondition: The object exists, and has been deleted by "delete"
    	//Postcondition: The left and right pointers' memory are sent back to the heap
    	
    	char data;            //node data (can be either a digit or an operator)
    	BinaryTree *left;     //pointer to a left subtree
    	BinaryTree *right;    //pointer to a right subtree
    };  //end struct BinaryTree
    
    
    #endif

    Code:
    //===========================/=/=/=/=/=/=/=========================//
    //                              INCLUDES                           //
    //===========================/=/=/=/=/=/=/=========================//
    
    
    #include <iostream>       //for the insertion operators, cout, and cin
    #include <conio>          //for the color functions and clrscr()
    #include <ctype>          //for the isdigit() and tolower() functions
    #include <cstdlib>        //for the exit() function 
    #include <cmath>          //for the pow function
    #include "binary_tree.h"  //contains the struct for the binary tree
    using namespace std;
    
    
    //===========================/=/=/=/=/=/=/=========================//
    //                        FUNCTION PROTOTYPES                      //
    //===========================/=/=/=/=/=/=/=========================//
    
    
    BinaryTree* buildTree(char *infix, int &pos);
    //Precondition: infix has been given an infix equation string by the user, and
    //pos has been given a value (to begin with, it is 1)
    //Postcondition: A binary expression tree is created, returning the root from 
    //a fully parenthesized expression given through infix. It stores digits under
    //left and right nodes, and if a parentheses is encountered, it will branch
    //off into a new subtree and populate the node with data. The roots of the subtrees
    //are operators, with digits (or a new operator possessing more children) for children.
    
    void preOrderTraverse(BinaryTree *root);
    //Precondition: root points to a populated binary expression tree
    //Postcondition: Traverses the list recursively and outputs the prefix form of the
    //infix expression
    
    void postOrderTraverse(BinaryTree *root);
    //Precondition: root points to a populated binary expression tree
    //Postcondition: Traverses the list recursively and outputs the postfix
    //form of the infix expression
    
    void inOrderTraverse(BinaryTree *root);
    //Precondition: root points to a populated binary expression tree
    //Postcondition: Traverses the list recursively and outputs the infix
    //form of the infix expression, but it will be in order (order of operations will not
    //apply here since it's outputted in the order of evaluation).
    
    double evaluate(BinaryTree *root);
    //Precondition: root points to a populated binary expression tree
    //Postcondition: The solution to the calculation of the data in the binary
    //tree is returned recursively
    
    bool isOperator(char ch);
    //Precondition: ch has been given a value
    //Postcondition: returns true if ch is either +, -, *, /, or ^
    
    void changecolor(char* word, int color);
    //precondition: word has been given a string value, and color has been given a number
    //postcondition: conio function textcolor() has been called within function changecolor,
    //changing the char* word into the color given by the int color.
    
    void flushin();
    //Postcondition: input buffer cleared to avoid unwanted input values
    
    
    //===========================/=/=/=/=/=/=/=========================//
    //                           IMPLEMENTATION                        //
    //===========================/=/=/=/=/=/=/=========================//
    
    
    int main(){
    	char infix[50], yesOrNo; 
    	int pos;                 //index variable
    	BinaryTree *tree;        //our binary tree! Everyone say hi!
    	
    	do{
    	
    		clrscr();
    		pos = 0;  //to be used as the index variable for infix. 0 is the start of a string
    		changecolor("Binary Expression Tree\r\n\r\n", LIGHTGREEN);
    		cout << "Give me a <fully> parenthesized infix equation: \n";
    		changecolor("\r\nInfix Expression: ", WHITE); 
    		cin.getline(infix, '\n');
    		cout << endl << endl;
    		
    		tree = buildTree(infix, pos);      //inserts infix expression into a binary tree
    		cout << "Prefix form of infix (preorder traversal): \n\t"; 
    		preOrderTraverse(tree);   
    		         
    		cout << "\n\nPostfix form of infix (postorder traversal): \n\t"; 
    		postOrderTraverse(tree);     
    		     
    		cout << "\n\nInfix form of infix (inorder traversal, read from left to right): \n\t"; 
    		inOrderTraverse(tree);           //outputs infix form of infix, but from the tree! Amazing! 
    		 
    		changecolor("\r\n\r\nEvaluation of tree: ", LIGHTBLUE);
    		cout << evaluate(tree);   //outputs the solution to the infix equation from the tree
    		
    		delete tree;   //returns the memory to the heap
    		
    		cout << "\n\n\nAgain? ";
    		
    		do{
    			cin.get(yesOrNo);
    		}while((tolower(yesOrNo) != 'y') && (tolower(yesOrNo) != 'n'));  //repeats if user doesn't enter y or n
    		 
    		flushin();   //clear input buffer
    	}while(tolower(yesOrNo) == 'y');   //continues the program as long as they say 'y'
    	
    	return 0;
    } //end main
    
    
    /*struct BinaryTree function definitions*/
    
    
    BinaryTree::BinaryTree(){   
    	left = NULL;     
    	right = NULL;
    } //end BinaryTree default constructor
    
    
    BinaryTree::~BinaryTree(){
    		
    	if (left != NULL)   //if the pointer is being used 
    		delete left;    //return it to the heap
    				
    	if (left != NULL)   //if the pointer is being used 
    		delete right;   //return it to the heap
    				
    } //end BinaryTree destructor
    
    
    /*driver file function definitions*/
    
    
    BinaryTree* buildTree(char *infix, int &pos){
    	BinaryTree *temp_root = new BinaryTree;       //allocates memory
    	
    	pos++; //advance one character (either a ( or a digit)
    	
    	if (infix[pos] == '(')  //if you encounter a parenthese
    		temp_root -> left = buildTree(infix, pos);    //recursive call: creates a subtree to the left
    	
    	else{
    		temp_root -> left = new BinaryTree;             //allocate memory
    		temp_root -> left -> data = infix[pos];         //assigns data unit
    	}
    	
    	pos++;                        //so we are able to get the next character of infix
    	temp_root -> data = infix[pos];    //assigns the operator to the root's data character
    	pos++;                        //so we are able to get the next character of infix
    	
    	if (infix[pos] == '(')   //if a nested parenthese arises
    		temp_root -> right = buildTree(infix, pos);   //recursive call: creates a subtree to the right!
    	
    	else{	
    		temp_root -> right = new BinaryTree;           //allocate memory
    		temp_root -> right -> data = infix[pos];       //assigns data unit
    	}
    	
    	pos++;       //skip over the ending ) bracket
    	return temp_root;
    } //end buildTree()
    
    
    void preOrderTraverse(BinaryTree *root){
    	cout << (root -> data);			   //output the data of the root
    
    	if (root -> left != NULL)
    		preOrderTraverse(root -> left);  //traverse down to the left side of the tree
    		
    	if (root -> right != NULL)	  
    		preOrderTraverse(root -> right); //traverse down to the right side of the tree	
    		
    } //end preOrderTraverse()
    
    
    void postOrderTraverse(BinaryTree *root){	 
    
    	if (root -> left != NULL)
    		postOrderTraverse(root -> left);  //traverse down to the left side of the tree
    	
    	if (root -> left != NULL)		
    		postOrderTraverse(root -> right); //traverse down to the right side of the tree
    		
    	cout << (root -> data);	      //output the data of the root
    	
    } //end postOrderTraverse()
    
    
    void inOrderTraverse(BinaryTree *root){	   
    
    	if (root -> left != NULL)
    		inOrderTraverse(root -> left);  //traverse down to the left side of the tree
    		
    	cout << (root -> data);	      //output the data of the root	
    	
    	if (root -> left != NULL)		
    		inOrderTraverse(root -> right); //traverse down to the right side of the tree
    	
    } //end inOrderTraverse()
    
    
    double evaluate(BinaryTree *root){
    	double temp, divisor;
    	
    	if (isdigit(root -> data))       //if the data character is a number
    		temp = (root -> data) - 48;  //convert char to the respective int/double value (48 is the ascii offset)
    		
    		
    	if (isOperator(root -> data)){   //if the data character is an operator
    	
    		switch (root -> data){   //apply the operator to the left and right values using recursive traversal
    		
    			case '+': 
    				temp = evaluate(root -> left) + evaluate(root -> right); 
    				break;
    				
    			case '-': 
    				temp = evaluate(root -> left) - evaluate(root -> right); 
    				break;
    				
    			case '*': 
    				temp = evaluate(root -> left) * evaluate(root -> right); 
    				break;
    				
    			case '/':
    				divisor = evaluate(root -> right);   
    				
    				if (divisor == 0){   //in math, you cannot divide by 0
    					cout << "\nDivide by 0 error.\n";
    					exit(1);
    				}
    				
    				else    //it's not 0, we can divide by it
    					temp = evaluate(root -> left) / divisor;
    					
    				break;
    				
    			case '^': 
    				temp = pow(evaluate(root -> left), evaluate(root -> right)); //raises the first arg to the second arg
    				break;
    				
    			default: 
    				cout << "\nError, operator unknown\n"; 
    				break;	
    			  
    		}
    	
    	}	 
    		
    	return temp;
    } //end evaluate()
    
    
    bool isOperator(char ch){
    	string acceptedOperators = "+-*/^";
    	
    	if(acceptedOperators.find(ch, 0) != string::npos)    //if ch can't be found in the string
    		return true;
    		
    	else
    		return false;
    		
    } //end isOperator()
    
    
    void changecolor(char* word, int color){
    	textcolor(color); 		 //changes text to the color given through the argument
    	cprintf("%s", word);	   	    //outputs the string in the given color
    	textcolor(LIGHTGRAY);	 //change color back to the default light gray
    } //end changecolor()
    
    
    void flushin(){
    
    	while (cin.get() != '\n'){}   //clear the input buffer
    	
    } //end flushin()
    My finished code.

    It works for the most part. Unfortunately, it doesn't like equations like "(((3+4)*6)/7)" even though it should. Anyone able to spot why?

  14. #14
    Registered User
    Join Date
    Oct 2002
    Posts
    155
    It must be something small, this entire program works fairly well

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 0
    Last Post: 11-04-2006, 10:07 AM
  2. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 03:00 PM
  3. Tutorial review
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 11
    Last Post: 03-22-2004, 08:40 PM
  4. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 09:33 AM
  5. BST/Red and Black Tree
    By ghettoman in forum C++ Programming
    Replies: 0
    Last Post: 10-24-2001, 10:45 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21