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...

Alright there we go. Alignments fixed

Does this have anything to do with checking for left?

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.

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...

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.

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.

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;  
}

So I can do this for all functions? When would I need to append to right side or left?

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)

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

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;
}

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?

It must be something small, this entire program works fairly well