Thread: C++ Tree Calculator

  1. #1
    Registered User
    Join Date
    Dec 2007
    Posts
    20

    C++ Tree Calculator

    Hello everyone Im new here, and I hope to get to know all of you well

    but anyways...on to my problem

    Ok Im going to admit this is a HW project, but i've done half of it.
    basically
    ok.
    were making a c++ calculator.
    using a binary tree "i think"
    it has to take note of "paranthesis"
    like 2+5
    and 2+(5+2)
    will have to be different

    He wrote the driver for us.
    we have to write the .h and implementation file

    I've written the .h and checked with him he said it was perfect
    BTW all the //comments are stuff he wrote on our code for us to use and help with (small class)
    Code:
    #ifndef CALCTREE_H
    #define CALCTREE_H
    
    #include<iostream>
    #include<cstdlib>
    using namespace std;
    
    //This file defines a binary tree class which is used for
    //parsing and evaluating simple mathematical expressions.
    //The binary tree is implemented using dynamic linked nodes.
    
    //This enumeration defines the 5 possible types of nodes
    enum NodeType{ ADD, SUB, MUT, DIV, OPR };
    //ADD - Addition Operator
    //SUB - Subtraction Operator
    //MUT - Multiplication Operator
    //DIV - Division Operator
    //OPR - Operand
    
    //A CTnode can either be an operand or an operation
    //A CTnode contains pointers to it's left and right children if present
    struct CTNode
    {
    	NodeType type;
    	int operand;
    	CTNode *left, *right;
    };
    
    class CalcTree
    {
    public:
    	CalcTree(); //default constructor
    	CalcTree( CalcTree& otherTree ); //copy constructor
    	~CalcTree(); //destructor
    
    	void setRoot( NodeType type_, int operand_ );
    	//construct a node with the given characteristics and place it at the root of this tree
    
    	void setLeft( CalcTree& otherTree );
    	//place a copy of the parameter tree as the left subtree of this tree
    
    	void setRight( CalcTree& otherTree );
    	//place a copy of the parameter tree as the right subtree of this tree
    
    	void printIN( ); 
    	//member function to print the stored expression in this tree using INFIX notation
    
    	void printPOST( );
    	//member function to print the stored expression in this tree using POSTFIX notation
    
    	float evaluate( );
    	//member function to evaluate the stored expression and return an answer
    	//assumes that the expression tree is well-formed
    	//the client must make sure the expression tree is well fromed before calling this function
    	
    private:
    	CTNode *copyHelper( CTNode *thatroot ); //recursive helper for copy constructor and "set" functions
    	//constructs an exact copy of the tree rooted at "thatroot" and returns a pointer to it
    
    	void destHelper( CTNode *thisroot ); //recursive helper for destructor
    	//completely deallocates all dynamic memory in the tree rooted at "thisroot"
    
    	void printINhelper( CTNode *thisroot ); //recursive helper for INFIX printing
    	//prints the expression tree rooted at "thisroot" in INFIX order
    
    	void printPOSThelper( CTNode *thisroot ); //recursive helper for POSTFIX printing
    	//prints the expression tree rooted at "thisroot" in POSTFIX order
    
    	float evalHelper( CTNode *thisroot ); //recursive helper for expression evaluation
    	//evaluates the expression tree rooted at "thisroot" and returns the answer
    	//returns a float so that integer division is avoided
    
    	CTNode *root; //pointer to the root node of this expression tree
    };
    
    #endif
    thats just the .h file

    HIS file he wrote for us is just the driver file
    Code:
    #include <iostream>
    #include <string>
    using namespace std;
    #include "CalcTree.h"
    
    //this enumeration defines the token types
    enum Token{LPAREN, RPAREN, PLUS, MINUS, MULT, DIVIDE, OPERAND, ETR, EXT, ERR};
    //LPAREN - left parenthesis
    //RPAREN - right parenthesis
    //PLUS - plus symbol
    //MINUS - minus symbol
    //MULT - multiply symbol
    //DIVIDE - divide symbol
    //OPERAND - an integer operand
    //ETR - the enter key
    //EXT - the exit token
    //ERR - the error token (parse error)
    
    //this function parses the cin stream and returns the next single token found
    Token parse( int& operand, string& message );
    //if an operand token is found, it is placed in the reference parameter "operand"
    //if an error is encountered, an error message will be placed in the reference parameter "message"
    
    //this function builds an expression tree from the parsed input tokens
    //returns true if a valid expression was built, false otherwise
    bool BuildEXP( CalcTree& expression );
    
    int main( )
    {
    cout<<"Welcome to the simple calculator."<<endl;
    
    bool POSTFIX = false; //default to infix notation printing
    char choice; //user choice
    cout<<"Would you like to print expressons in POSTFIX before evaluating? (y/n)"<<endl;
    cin.get(choice); //get user choice
    cin.ignore(255,'\n');
    //loop as long as user doesn't enter a valid choice
    while(choice!='y' && choice!='Y' && choice!='n' && choice!='N')
    	{
    	cout<<"Invalid choice...would you like to activate POSTFIX mode? (y/n)"<<endl;
    	cin.get(choice); //get user choice
    	cin.ignore(255,'\n');
    	}
    if(choice=='Y' || choice=='y') POSTFIX = true; //set boolean if user wants postfix printing
    
    //give user instructions
    cout<<"Enter any INFIX expression."<<endl;
    cout<<"Use only operators + , - , * , and /"<<endl;
    cout<<"Use only integer operands and parenthesize your expressions!"<<endl;
    cout<<"Type \"EXIT\" to quit."<<endl<<endl;
    
    int operand; //store a parsed operand
    string message; //store an error message
    Token next; //store the next token coming from the input
    CalcTree expression; //store the parsed expression in a tree structure
    
    next = parse(operand,message); //get the first token from the input
    while( next != EXT ) //while the token is not the exit token
    	{
    	if(next==LPAREN) //if the token is left parenthesis
    		{
    		bool result = BuildEXP( expression ); //build an expression
    		if(!result) //if the expression doesn't build properly
    			{
    			cout<<endl<<"Syntax error: Invalid Expression!";
    			}
    		else //if it is built properly
    			{
    			//re-print the expression in the user's desired format
    			cout<<endl;
    			if(POSTFIX) expression.printPOST();
    			else expression.printIN();
    			cout<<" = "<<expression.evaluate(); //evaluate the expression
    			cin.ignore(255,'\n');
    			}
    		}
    	else if(next==ERR) //if the token is an error
    		{
    		cout<<endl<<message; //output the error message
    		}
    	else //if the token is anything else, the expression doesn't begin properly
    		{
    		cout<<endl<<"Syntax error: Expressions must begin with \"(\".";
    		}
    
    	cout<<endl<<endl; //move prompt past any output messages
    	next = parse(operand,message); //get the next token
    	}
    }
    
    Token parse( int& operand, string& message )
    {
    string history=""; //keep history of characters gotten for multi-character tokens
    char next; //store the next character from the input
    cin.get(next); //get the next character from the input
    if(next=='(') return LPAREN; //left parenthesis found
    else if(next==')') return RPAREN; //right parenthesis found
    else if(next=='+') return PLUS; //plus sign found
    else if(next=='-') return MINUS; //minus sign found
    else if(next=='*') return MULT; //multiplication symbol found
    else if(next=='/') return DIVIDE; //division symbol found
    else if(next=='\n') return ETR; //new like character (enter) found
    else if(next=='E' || next=='e') //check for exit token if an E or e is found
    	{
    	history=history+next; //store the E or e
    	cin.get(next); //get the next character
    	if(next=='X' || next=='x') //if an X or x is found continue looking for exit
    		{
    		history=history+next; //store the X or x
    		cin.get(next); //get the next character
    		if(next=='I' || next=='i') //if an I or i is found continue looking for exit
    			{
    			history=history+next; //store the I or i
    			cin.get(next); //get the next character
    			if(next=='T' || next=='t') //if a T or t is found, we have exit
    				{
    				return EXT;
    				}
    			else //if not T or t, it's a parse error
    				{
    				message = "Parse error: unrecognized input token \""+history+next+"\".";
    				return ERR;
    				}
    			}
    		else //if not I or i, it's a parse error
    			{
    			message = "Parse error: unrecognized input token \""+history+next+"\".";
    			return ERR;
    			}
    		}
    	else //if not X or x, it's a parse error
    		{
    		message = "Parse error: unrecognized input token \""+history+next+"\".";
    		return ERR;
    		}
    	}
    else if(isdigit(next)) //check for an operand (begins with a digit)
    	{
    	history=history+next; //store the current digit character in the history
    	while(isdigit(cin.peek())) //peek at the next input character, is it another digit?
    		{
    		cin.get(next); //if so, get it and add it to the history
    		history=history+next;
    		}//at the end of this loop, all consecutive digits found are in the "history" string
    	operand = atoi(history.c_str()); //convert the digit characters to an actual number
    	return OPERAND;
    	}
    else //unrecognized character
    	{
    	message = "Parse error: unrecognized input character \"";
    	message = message+next;
    	message = message+"\".";
    	return ERR;
    	}
    }
    
    bool BuildEXP( CalcTree& expression )
    {
    CalcTree left, right; //create trees for the left and right sub-expressions
    
    int operand; //store an operand
    string message; //store an error message
    Token next; //store the next token
    
    //get first part of expression
    //should be an operand or another sub-expression
    next = parse(operand,message);
    
    if(next==LPAREN) //left parenthesis here means there is a left sub-expression
    	{
    	bool Lresult = BuildEXP( left ); //build the left expression tree
    	if(!Lresult) //if there is an error in the left expression
    		{
    		cin.ignore(255,'\n'); //clear all remaining input
    		return false; //return an error code
    		}
    	}
    else if(next==OPERAND) //operand here means no left sub-expression
    	{
    	left.setRoot(OPR,operand); //just set the left tree to the operand value
    	}
    
    // All of these are errors, the first part of an expression should not be any of these! //
    else if(next==PLUS)
    	{
    	cout<<endl<<"Syntax error: Found operator \"+\" when operand or sub-expression expected.";
    	cin.ignore(255,'\n');
    	return false;
    	}
    else if(next==MINUS)
    	{
    	cout<<endl<<"Syntax error: Found operator \"-\" when operand or sub-expression expected.";
    	cin.ignore(255,'\n');
    	return false;
    	}
    else if(next==MULT)
    	{
    	cout<<endl<<"Syntax error: Found operator \"*\" when operand or sub-expression expected.";
    	cin.ignore(255,'\n');
    	return false;
    	}
    else if(next==DIVIDE)
    	{
    	cout<<endl<<"Syntax error: Found operator \"/\" when operand or sub-expression expected.";
    	cin.ignore(255,'\n');
    	return false;
    	}
    else if(next==ETR)
    	{
    	cout<<endl<<"Syntax error: End of line found in middle of expression";
    	return false;
    	}
    else if(next==EXT)
    	{
    	cout<<endl<<"Syntax error: Exit token found in middle of expression";
    	cin.ignore(255,'\n');
    	return false;
    	}
    else if(next==RPAREN)
    	{
    	cout<<endl<<"Syntax error: \")\" found before expected";
    	cin.ignore(255,'\n');
    	return false;
    	}
    else if(next==ERR)
    	{
    	cout<<endl<<message;
    	cin.ignore(255,'\n');
    	return false;
    	}
    
    //get second part of expression
    //should be an operator
    next = parse(operand,message);
    
    //look for one of the four operators, if found place at the root of this expression tree
    if(next==PLUS)
    	{
    	expression.setRoot(ADD,0);
    	}
    else if(next==MINUS)
    	{
    	expression.setRoot(SUB,0);
    	}
    else if(next==MULT)
    	{
    	expression.setRoot(MUT,0);
    	}
    else if(next==DIVIDE)
    	{
    	expression.setRoot(DIV,0);
    	}
    // All of these are errors, the second part of an expression should not be any of these! //
    else if(next==LPAREN)
    	{
    	cout<<endl<<"Syntax error: Found sub-expression when operator was expected.";
    	cin.ignore(255,'\n');
    	return false;
    	}
    else if(next==OPERAND)
    	{
    	cout<<endl<<"Syntax error: Found operand when operator was expected.";
    	cin.ignore(255,'\n');
    	return false;
    	}
    else if(next==ETR)
    	{
    	cout<<endl<<"Syntax error: End of line found in middle of expression";
    	return false;
    	}
    else if(next==EXT)
    	{
    	cout<<endl<<"Syntax error: Exit token found in middle of expression";
    	cin.ignore(255,'\n');
    	return false;
    	}
    else if(next==RPAREN)
    	{
    	cout<<endl<<"Syntax error: \")\" found before expected";
    	cin.ignore(255,'\n');
    	return false;
    	}
    else if(next==ERR)
    	{
    	cout<<endl<<message;
    	cin.ignore(255,'\n');
    	return false;
    	}
    
    
    //get third part of expression
    //should be an operand or another sub-expression
    next = parse(operand,message);
    
    if(next==LPAREN) //left parenthesis here means there is a right sub-expression
    	{
    	bool Rresult = BuildEXP( right ); //build the right expression tree
    	if(!Rresult) //if there is an error in the right expression
    		{
    		cin.ignore(255,'\n'); //clear all remaining input
    		return false; //return an error code
    		}
    	}
    else if(next==OPERAND) //operand here means no right sub-expression
    	{
    	right.setRoot(OPR,operand); //just set the right tree to the operand value
    	}
    // All of these are errors, the third part of an expression should not be any of these! //
    else if(next==PLUS)
    	{
    	cout<<endl<<"Syntax error: Found operator \"+\" when operand or sub-expression expected.";
    	cin.ignore(255,'\n');
    	return false;
    	}
    else if(next==MINUS)
    	{
    	cout<<endl<<"Syntax error: Found operator \"-\" when operand or sub-expression expected.";
    	cin.ignore(255,'\n');
    	return false;
    	}
    else if(next==MULT)
    	{
    	cout<<endl<<"Syntax error: Found operator \"*\" when operand or sub-expression expected.";
    	cin.ignore(255,'\n');
    	return false;
    	}
    else if(next==DIVIDE)
    	{
    	cout<<endl<<"Syntax error: Found operator \"/\" when operand or sub-expression expected.";
    	cin.ignore(255,'\n');
    	return false;
    	}
    else if(next==ETR)
    	{
    	cout<<endl<<"Syntax error: End of line found in middle of expression";
    	return false;
    	}
    else if(next==EXT)
    	{
    	cout<<endl<<"Syntax error: Exit token found in middle of expression";
    	cin.ignore(255,'\n');
    	return false;
    	}
    else if(next==RPAREN)
    	{
    	cout<<endl<<"Syntax error: \")\" found before expected";
    	cin.ignore(255,'\n');
    	return false;
    	}
    else if(next==ERR)
    	{
    	cout<<endl<<message;
    	cin.ignore(255,'\n');
    	return false;
    	}
    
    
    //get fourth part of expression
    //should be a right parenthesis
    next = parse(operand,message);
    
    if(next==RPAREN) //right parenthesis means the end of an expression
    	{
    	expression.setLeft(left); //set the left subtree of this expression to the left expression tree
    	expression.setRight(right); //set the right subtree of this expression to the right expression tree
    	}
    // All of these are errors, the third part of an expression should not be any of these! //
    else if(next==LPAREN)
    	{
    	cout<<endl<<"Syntax error: Found sub-expression when \")\" was expected.";
    	cin.ignore(255,'\n');
    	return false;
    	}
    
    else if(next==PLUS)
    	{
    	cout<<endl<<"Syntax error: Found operator \"+\" when \")\" expected.";
    	cin.ignore(255,'\n');
    	return false;
    	}
    else if(next==MINUS)
    	{
    	cout<<endl<<"Syntax error: Found operator \"-\" when \")\" expected.";
    	cin.ignore(255,'\n');
    	return false;
    	}
    else if(next==MULT)
    	{
    	cout<<endl<<"Syntax error: Found operator \"*\" when \")\" expected.";
    	cin.ignore(255,'\n');
    	return false;
    	}
    else if(next==DIVIDE)
    	{
    	cout<<endl<<"Syntax error: Found operator \"/\" when \")\" expected.";
    	cin.ignore(255,'\n');
    	return false;
    	}
    else if(next==OPERAND)
    	{
    	cout<<endl<<"Syntax error: Found operand when \")\" was expected.";
    	cin.ignore(255,'\n');
    	return false;
    	}
    else if(next==ETR)
    	{
    	cout<<endl<<"Syntax error: End of line found in middle of expression";
    	return false;
    	}
    else if(next==EXT)
    	{
    	cout<<endl<<"Syntax error: Exit token found in middle of expression";
    	cin.ignore(255,'\n');
    	return false;
    	}
    else if(next==ERR)
    	{
    	cout<<endl<<message;
    	cin.ignore(255,'\n');
    	return false;
    	}
    
    return true; //return success (no erros have been encountered
    }
    confusing eh. it's tokenizing then parsing the functions which we honestly havent been over alot in class.

    here's all i have for my implementation file
    Code:
    //Matt Smith
    //Cs 215 Section 2
    //Program 5
    #include "CalcTree.h"
    
    
    CalcTree::CalcTree()
    {
    root = NULL;
    
    
    
    }
    
    CalcTree::~CalcTree()
    {
           destHelper(thisroot); 
    }
    
    
    
    
    void CalcTree::destHelper( CTNode *thisroot )
    {     
    	if  ( thisroot != NULL )    
           {     
    	destHelper( thisroot->left );
    	destHelper( thisroot->right );
    	delete  thisroot ;
           }
    }
    now I know my .h file /header file is correct, he gave us VERY strict guidelines and I wrote the .h turned it in, he said it was perfect (well he had to change one lil thing) so that part is written. but Im not sure where to go now. since he never really went over parsers and made it be due TUESDAY!
    it's crazy. but Im pleading for yalls help, it's all this parsing thats whats confusing

  2. #2
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    Quote Originally Posted by MercFh View Post
    now I know my .h file /header file is correct, he gave us VERY strict guidelines and I wrote the .h turned it in, he said it was perfect (well he had to change one lil thing) so that part is written. but Im not sure where to go now. since he never really went over parsers and made it be due TUESDAY!
    it's crazy. but Im pleading for yalls help, it's all this parsing thats whats confusing
    Since he didn't go over parsers, that's probably why he wrote the parser himself. (See the function named "parse"? Notice how you didn't write any of it?) (I'm not saying you shouldn't try to understand it, you should try and hopefully succeed, but you don't have to do it right this instant.) Your job is to write the fifteen functions (yes, I counted) that have prototypes in your header file. Most of them (all but one or two) appear to be tree traversal-type things or bookkeeping (construct, delete, add to the tree, etc.) You will have to process the tree that is created, so you should understand what kind of thing gets built by the "driver".

    As to your code that you've written, it looks pretty much ok so far. Your destructor does not know what "thisroot" is.

  3. #3
    Registered User
    Join Date
    Dec 2007
    Posts
    20

    Aight

    Ok i've written quite alot
    tell me what you think
    Code:
    //Matt Smith
    //Cs 215 Section 2
    //Program 5
    #include "CalcTree.h"
    
    
    CalcTree::CalcTree()
    {
    root = NULL;
    }
    
    CalcTree::~CalcTree()
    {
     destHelper(root); 
    }
    
    
    
    CalcTree::CalcTree(CalcTree& otherTree) //copy constructor
    {
    root = copyHelper(otherTree.root);                      
    }
    
    CTNode* copyHelper(CTNode* thatroot)
    {
    if(thatroot==NULL) return NULL;
    
    
    CTNode *pwned;
    pwned = new CTNode;
    pwned->operand = thatroot->operand; 
    pwned->left=NULL; pwned->right=NULL; 
    
    if(( thatroot->left != NULL ) || ( thatroot->right != NULL ))
        {     
        if( thatroot->left != NULL ) 
            pwned->left = copyHelper(thatroot->left); 
        if( thatroot->right != NULL ) 
            pwned->right = copyHelper(thatroot->right); 
    }
    return pwned;
    }
    
    
    
    
    
    
    
    
    
    
    void CalcTree::destHelper( CTNode *thisroot )
    {     
    	if  ( thisroot != NULL )    
           {     
    	destHelper( thisroot->left );
    	destHelper( thisroot->right );
    	delete  thisroot ;
    
           }
    }
    
    
    
    void CalcTree::setRoot(NodeType type_, int operand_)
    {
    
    
    
    
    }
    
    
    
    
    
    
    void CalcTree::setLeft(CalcTree &otherTree)
    {
    // delete the old branch first
    destHelper(root->left);
    
    // copy the new tree as left branch
    root->left= copyHelper(otherTree.root);
    }
    
    
    void CalcTree::setRight(CalcTree &otherTree)
    {
    // delete the old branch first
    destHelper(root->right);
    
    // copy the new tree as left branch
    root->right= copyHelper(otherTree.root);
    }
    
    
    
    
    void CalcTree::printPOST()
    {
    cout<<"Tree Contents: \n";
    printPOSThelper(root);
    cout<<endl;      
    }
    
    
    void printPOSThelper(CTNode* thisroot)
    {
    if(thisroot!=NULL)
        {
        if(thisroot->left!=NULL) printPOSThelper(thisroot->left);
        if(thisroot->right!=NULL) printPOSThelper(thisroot->right);
        cout<<" "<<thisroot->operand<<" ";
        }          
    }
    
    void CalcTree::printIN()
    {
    cout<<"Tree Contents: \n";
    printINhelper(root);
    cout<<endl;      
    }
    
    
    void printINhelper(CTNode* thisroot)
    {
    if(thisroot!=NULL)
        {
        if(thisroot->left!=NULL) printINhelper(thisroot->left);
        cout<<" "<<thisroot->operand<<" ";
        if(thisroot->right!=NULL) printINhelper(thisroot->right);
        }     
    }
    rmemeber this is jsut the implmentation file

    BUT
    i dont know what to make the set root function, and the evaluation function, thats the two main ones i have left....
    i hope my other code is ok tho?

    thx all

  4. #4
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    Quote Originally Posted by MercFh View Post
    Ok i've written quite alot
    tell me what you think
    Code:
    CTNode* copyHelper(CTNode* thatroot)
    {
    if(thatroot==NULL) return NULL;
    
    
    CTNode *pwned;
    pwned = new CTNode;
    pwned->operand = thatroot->operand; 
    pwned->left=NULL; pwned->right=NULL; 
    
    if(( thatroot->left != NULL ) || ( thatroot->right != NULL ))
        {     
        if( thatroot->left != NULL ) 
            pwned->left = copyHelper(thatroot->left); 
        if( thatroot->right != NULL ) 
            pwned->right = copyHelper(thatroot->right); 
    }
    return pwned;
    }
    The Department of Redundancy Department wants to speak with you. (This will work, but you're checking against NULL twice for no good reason that I can see.) And you should be setting type when you set everything else.

    The basic idea behind printing is ok, but you need to get the type involved there, too.

    Quote Originally Posted by MercFh View Post
    BUT
    i dont know what to make the set root function, and the evaluation function, thats the two main ones i have left....
    i hope my other code is ok tho?

    thx all
    Well, you have to create a root for the tree at some point, right? You need the data that goes into the node to do so, right? So to set root, you need to make the root point at a node that has the data in it.

    In order to do the evaluation, I ask (what I hinted at earlier): do you know what this expression tree that you're building is? If I gave you (7-(3*5)), what tree would get built? (Note: If you don't know, you could look here for guidance.) Once you know that, the idea behind evaluation should be clearer.
    Last edited by tabstop; 12-02-2007 at 08:12 PM. Reason: found a better link

  5. #5
    Registered User
    Join Date
    Dec 2007
    Posts
    20

    ok I think i got it...sorta

    Ok I changed everything around, everything should be working BUT im getting 3 linker errors, i dunno wtf why though, is there anything else u seen stunningly wrong with it?

    Code:
    //Matt Smith
    //Cs 215 Section 2
    //Program 5
    #include "CalcTree.h"
    
    
    CalcTree::CalcTree()
    {
    root = NULL;
    }
    
    CalcTree::~CalcTree()
    {
    destHelper(root); 
    }
    
    
    CalcTree::CalcTree(CalcTree& otherTree) //copy constructor
    {
    root = copyHelper(otherTree.root);                      
    }
    
    CTNode* copyHelper(CTNode* thatroot)
    {
    if(thatroot==NULL) return NULL;
    
    
    CTNode *pwned;
    pwned = new CTNode;
    pwned->operand = thatroot->operand; 
    pwned->left=NULL; pwned->right=NULL; 
    
    if(( thatroot->left != NULL ) || ( thatroot->right != NULL ))
        {     
        if( thatroot->left != NULL ) 
            pwned->left = copyHelper(thatroot->left); 
        if( thatroot->right != NULL ) 
            pwned->right = copyHelper(thatroot->right); 
    }
    return pwned;
    }
    
    
    void CalcTree::destHelper( CTNode *thisroot )
    {     
    	if(root==NULL) return;
    
    
    if(( thisroot->left != NULL ) || ( thisroot->right != NULL ))
        {     
        if( thisroot->left != NULL ) 
            {destHelper(thisroot->left); 
             thisroot->left=NULL;} 
        if( thisroot->right != NULL ) 
            {destHelper(thisroot->right); 
             thisroot->right=NULL;} 
        }
    
    
    delete thisroot; 
    }
    
    
    
    void CalcTree::setRoot(NodeType type_, int operand_)
    {
    destHelper (root);  
    CTNode *temp = NULL;
    temp= new CTNode;
    temp-> type=type_;
    temp-> operand=operand_;
    
    temp->left =root->left;
    temp->right =root->right;
    root->left = NULL;
    root->right = NULL;
    delete root;
    root->right=NULL;
    root->left=NULL;
    
    
    
    
    }
    
    
    
    
    void CalcTree::setLeft(CalcTree &otherTree)
    {
    // delete the old branch first
    destHelper(root->left);
    
    // copy the new tree as left branch
    root->left= copyHelper(otherTree.root);
    }
    
    
    void CalcTree::setRight(CalcTree &otherTree)
    {
    // delete the old branch first
    destHelper(root->right);
    
    // copy the new tree as left branch
    root->right= copyHelper(otherTree.root);
    }
    
    
    
    
    void CalcTree::printIN()
    {
    
    printINhelper(root);
       
    }
    
    
    void printINhelper(CTNode* thisroot)
    {
    if (thisroot == NULL)
            return;
    
        else if (thisroot->type == OPR)        
            cout << thisroot->operand;    
           
        
        else {
            cout << "( ";                    
            printINhelper (thisroot->left);        
            switch (thisroot->type){            
                case ADD: cout << " + ";
                    break;
                case SUB: cout << " - ";
                    break;
                case MUT: cout << " * ";
                    break;
                case DIV: cout << " / ";
                    break;
            }
            printINhelper (thisroot->right);    
            cout << " )";                    
        }
    }  
    
    
    
    void CalcTree::printPOST( )
    {
        cout << "(";
        printPOSThelper(root);
        cout << ")";
       
    }
    void CalcTree::printPOSThelper(CTNode *thisroot){
    
        
        if (thisroot->type == OPR)        
            cout << thisroot->operand;    
           
     
        else {
           
            printPOSThelper (thisroot->left);       
            printPOSThelper (thisroot->right);    
            switch (thisroot->type){            
                case ADD: cout << " + ";
                    break;
                case SUB: cout << " - ";
                    break;
                case MUT: cout << " * ";
                    break;
                case DIV: cout << " / ";
                    break;
            }       
        }
    }
    
    
    float CalcTree::evaluate( ){
    
        return evalHelper(root);
    }
    
    float CalcTree::evalHelper( CTNode *thisroot ){
       
        if (thisroot == NULL)
        return 0;
       
        
        if (thisroot->type == OPR)
            return (float (thisroot->operand));
    
        
        else {
            switch (thisroot->type){                // choose the correct operation
                case ADD: return (float (evalHelper(thisroot->left) + evalHelper(thisroot->right)));
                case SUB: return (float (evalHelper(thisroot->left)- evalHelper(thisroot->right)));
                case MUT: return (float (evalHelper(thisroot->left) * evalHelper(thisroot->right)));
                case DIV:return (float (evalHelper(thisroot->left)/ evalHelper(thisroot->right)));
                default: return 0;
            }
        }
    }

  6. #6
    Registered User
    Join Date
    Dec 2007
    Posts
    20
    Ok i got it all running and everythigns compiled. but when i go to do an expression it gives me a error......and just doesnt do anything. I dunno what the problem is

    it just halts for a sec, then a window pops up and is like "progrtam5.exe has a problem blah blah, send error report)


    .....so i dunno, someone help Im so CLOSE!!!!!!!!!



    Code:
    //Matt Smith
    //Cs 215 Section 2
    //Program 5
    #include "CalcTree.h"
    
    
    CalcTree::CalcTree()
    {
    root = NULL;
    }
    
    CalcTree::~CalcTree()
    {
    destHelper(root); 
    }
    
    
    CalcTree::CalcTree(CalcTree& otherTree) //copy constructor
    {
    root = copyHelper(otherTree.root);                      
    }
    
    CTNode* CalcTree::copyHelper(CTNode *thatroot)
    {
    if(thatroot==NULL) return NULL;
    
    
    CTNode *pwned;
    pwned = new CTNode;
    pwned->operand = thatroot->operand; 
    pwned->left=NULL; pwned->right=NULL; 
    
    if(( thatroot->left != NULL ) || ( thatroot->right != NULL ))
        {     
        if( thatroot->left != NULL ) 
            pwned->left = copyHelper(thatroot->left); 
        if( thatroot->right != NULL ) 
            pwned->right = copyHelper(thatroot->right); 
    }
    return pwned;
    }
    
    
    void CalcTree::destHelper( CTNode *thisroot )
    {     
    	if(root==NULL) return;
    
    
    if(( thisroot->left != NULL ) || ( thisroot->right != NULL ))
        {     
        if( thisroot->left != NULL ) 
            {destHelper(thisroot->left); 
             thisroot->left=NULL;} 
        if( thisroot->right != NULL ) 
            {destHelper(thisroot->right); 
             thisroot->right=NULL;} 
        }
    
    
    delete thisroot; 
    }
    
    
    
    void CalcTree::setRoot(NodeType type_, int operand_)
    {
    destHelper (root);  
    CTNode *temp = NULL;
    temp= new CTNode;
    temp-> type=type_;
    temp-> operand=operand_;
    
    temp->left =root->left;
    temp->right =root->right;
    root->left = NULL;
    root->right = NULL;
    delete root;
    root->right=NULL;
    root->left=NULL;
    
    
    
    
    }
    
    
    
    
    void CalcTree::setLeft(CalcTree &otherTree)
    {
    // delete the old branch first
    destHelper(root->left);
    
    // copy the new tree as left branch
    root->left= copyHelper(otherTree.root);
    }
    
    
    void CalcTree::setRight(CalcTree &otherTree)
    {
    // delete the old branch first
    destHelper(root->right);
    
    // copy the new tree as left branch
    root->right= copyHelper(otherTree.root);
    }
    
    
    
    
    void CalcTree::printIN()
    {
    
    printINhelper(root);
       
    }
    
    
    void CalcTree::printINhelper(CTNode* thisroot)
    {
    if (thisroot == NULL)
            return;
    
        else if (thisroot->type == OPR)        
            cout << thisroot->operand;    
           
        
        else {
            cout << "( ";                    
            printINhelper (thisroot->left);        
            switch (thisroot->type){            
                case ADD: cout << " + ";
                    break;
                case SUB: cout << " - ";
                    break;
                case MUT: cout << " * ";
                    break;
                case DIV: cout << " / ";
                    break;
            }
            printINhelper (thisroot->right);    
            cout << " )";                    
        }
    }  
    
    
    
    void CalcTree::printPOST( )
    {
        cout << "(";
        printPOSThelper(root);
        cout << ")";
       
    }
    void CalcTree::printPOSThelper(CTNode *thisroot){
    
        
        if (thisroot->type == OPR)        
            cout << thisroot->operand;    
           
     
        else {
           
            printPOSThelper (thisroot->left);       
            printPOSThelper (thisroot->right);    
            switch (thisroot->type){            
                case ADD: cout << " + ";
                    break;
                case SUB: cout << " - ";
                    break;
                case MUT: cout << " * ";
                    break;
                case DIV: cout << " / ";
                    break;
            }       
        }
    }
    
    
    float CalcTree::evaluate( ){
    
        return evalHelper(root);
    }
    
    float CalcTree::evalHelper( CTNode *thisroot ){
       
        if (thisroot == NULL)
        return 0;
       
        
        if (thisroot->type == OPR)
            return (float (thisroot->operand));
    
        
        else {
            switch (thisroot->type){                // choose the correct operation
                case ADD: return (float (evalHelper(thisroot->left) + evalHelper(thisroot->right)));
                case SUB: return (float (evalHelper(thisroot->left)- evalHelper(thisroot->right)));
                case MUT: return (float (evalHelper(thisroot->left) * evalHelper(thisroot->right)));
                case DIV:return (float (evalHelper(thisroot->left)/ evalHelper(thisroot->right)));
                default: return 0;
            }
        }
    }

  7. #7
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    The Department of Redundancy Department loves your SetRoot function. Again, it works (I think), but it's not very clean or clear.

    If you're getting linker errors, then everything compiles, which is good. I don't know your build process (I'm assuming you're using some IDE with "project" or "solution" capabilities), and you very carefully didn't tell me what the linker errors are, so I don't know. You could try "rebuild" or "build all" or something similar, just in case, to force everything (including your professor's code to get recompiled).

  8. #8
    Registered User
    Join Date
    Dec 2007
    Posts
    20
    no i got the linker errors fixed, that all works, i just called a function wrong

    but now when i go to do a number i try (5*3)
    it just says program5.exre must now close.

    I DID go to the debugger and went to the break point, and it pointed at
    temp->left =root->left;

    in my setroot function?

  9. #9
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    Yes! Now, what was the last thing we did to root before this line is executed?

  10. #10
    Registered User
    Join Date
    Dec 2007
    Posts
    20
    So basically my setroot function is f'd up for some reason

  11. #11
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    Once root is freed, you can't reference it to get root->left and root->right. On the other hand, if you're creating a root, you already know what you want root->left and root->right to be (or more specifically, what you want temp->left and temp->right to be when you're creating the node).
    Last edited by tabstop; 12-02-2007 at 09:14 PM. Reason: not finished typing yet

  12. #12
    Registered User
    Join Date
    Dec 2007
    Posts
    20
    So......what? what do that mean what u just said I dont understand lol?
    Do i need to delete something or change......im confussled?

  13. #13
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    I was referring to where your program blew up. Remember the debugger? The line with the problem? (Well, the first line with a problem.) At that point, root doesn't exist anymore -- you killed it first thing. So you can't use it, later, since it doesn't exist anymore; which is why temp->left = root->left breaks.

    But, since we're creating a root (and nothing else, no children), we know what temp->left and temp->right are supposed to be. So just assign them.

  14. #14
    Registered User
    Join Date
    Dec 2007
    Posts
    20
    so something like this?
    destHelper (root);
    CTNode *temp = NULL;
    temp= new CTNode;
    temp-> type=type_;
    temp-> operand=operand_;
    temp->left=NULL;
    temp->right=NULL;
    root=temp;
    delete temp;

  15. #15
    Registered User
    Join Date
    Dec 2007
    Posts
    20
    but when i do that next is points to
    if(( thisroot->left != NULL ) || ( thisroot->right != NULL ))
    in the destHelper.

    man this program has alot of bugs

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Binary Tree Search
    By C++Newbie in forum C++ Programming
    Replies: 7
    Last Post: 04-05-2011, 01:17 AM
  2. Interpreter.c
    By moussa in forum C Programming
    Replies: 4
    Last Post: 05-28-2008, 05:59 PM
  3. 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
  4. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 10:33 AM
  5. BST/Red and Black Tree
    By ghettoman in forum C++ Programming
    Replies: 0
    Last Post: 10-24-2001, 10:45 PM