Class Tree vs Structure TreeNode

Question

I have two separate programs, both dealing with evaluating expression trees with infix and postfix. One is based on structures while the other is based on classes. Now I am stuck on the part of my assignment(for the class version) that says to:

"Finish the implementation of the createExpressionTree() method"

and that

"Its very similar to your previous implementation, except that you will be using instances of the "class Tree" instead of instances of the "structure TreeNode"."

There is more to the both than what is below, but I think you can get the gist of things, so what I am asking is: How similar is the class implementation to the structure one? And can I just copy and paste the old code in that is shown below and make minor adjustments? I have been trying but am have issues with accessing private members and such.

So here is the class tree and my new version of createExpressionTree that is supposed to go with it

#ifndef TREE_H
#define TREE_H

#include <vector>
#include <stack>
#include <sstream>
#include <map>
# define TYPE_NUMBER 0
# define TYPE_VARIABLE 1
# define TYPE_OPERATOR 2



class Tree
{
public:
Tree(std::string input,Tree *leftSubTree=NULL,Tree *rightSubTree=NULL);
Tree(const Tree &inTree);   //COPY CONSTRUCTOR
~Tree(); //DESTRUCTOR

int evaluate(std::map< std::string, int > ipMap); //EVALUATE THE EXPRESSION
void postOrderPrint();
void inOrderPrint();

private:
Tree *leftPtr;
std::string Op;
Tree *rightPtr;
int NodeType;

};

code associated with tree class

Tree::Tree(std::string input,Tree *leftSubTree,Tree *rightSubTree){
Op = input;
leftPtr = leftSubTree;
rightPtr = rightSubTree;
int num;
if (input == "+"|input == "-"|input == "*"|input == "/")
            NodeType = TYPE_OPERATOR;
else if(std::istringstream(Op)>>num)
    NodeType = TYPE_NUMBER;
else
    NodeType = TYPE_VARIABLE;
}
// copy constructor

Tree::Tree(const Tree &inTree){
Op = inTree.Op;
NodeType = inTree.NodeType;

if (inTree.leftPtr == NULL){
   leftPtr = NULL;
}
else {
   leftPtr =  new Tree(*(inTree.leftPtr));
}
if (inTree.rightPtr == NULL){
   rightPtr = NULL;
}
else {
   rightPtr =  new Tree(*(inTree.rightPtr));
}
}


// tree destructor

Tree::~Tree(){
std::cout << "Tree destructor called" << std::endl;

if (leftPtr != NULL) {
    delete(leftPtr);
    leftPtr = NULL;
}
if (rightPtr != NULL) {
    delete(rightPtr);
    rightPtr = NULL;
}

}

#endif

New createExpressionTree that I would love some help with:

void arithmetic_expression::createExpressionTree(std::vector<std::string> expression)
{
std::stack <Tree> localStack;
std::string Op;
//Very similar to old implementation 
}

And here is the previous implementation of the structure treeNode and the previous createExpressionTree that is completed

struct treeNode {
treeNode *leftPtr;     /* pointer to left subtree */
std::string Op;                     /* integer data value */
treeNode *rightPtr;    /* pointer to right subtree */
};
typedef struct treeNode TreeNode;
typedef TreeNode * TreeNodePtr;

previous createExpressionTree

void arithmetic_expression::createExpressionTree(std::vector<std::string> expression)
{
std::stack <TreeNodePtr> localStack;
std::string Op;
TreeNodePtr ptr;

for(int i=0; i<expression.size();i++)
{

    Op = expression[i];

    ptr = createNewTreeNode(Op);

    if(char_is_operator(Op))
    {

        // adding element to right tree
        if (localStack.empty())
        {
            std::cout<< "Invalid expression: tree not created  " << std::endl;
            topPtr = NULL;
            return;
        }
        else
        {
            ptr->rightPtr = localStack.top();
            localStack.pop();
        }

        // adding element to left tree
        if (localStack.empty()) {
            std::cout<< "Invalid expression: tree not created  " << std::endl;
            topPtr = NULL;
            return;
        }
        else
        {
            ptr->leftPtr = localStack.top();
            localStack.pop();
        }

    }
    // pushing element to stack
    localStack.push(ptr);
}

if (localStack.empty()) {
    std::cout<< "Invalid expression: tree not created  " << std::endl;
    topPtr = NULL;
}
else
{
    topPtr = localStack.top();
    localStack.pop();
    if (!localStack.empty()) {
        std::cout<< "Invalid expression: tree not created  " << std::endl;
        topPtr = NULL;
    }

}


}

I dont have access to leftPtr/rightPtr like i did in the structure version. So what do i do instead for the class version? Maybe that is a more specific question i should ask — user1325578
If you want to access private member fields there are two ways of going about it. First way is to create an accessor method in the Tree class which returns the private variable. Second method is to declare friend void arithmetic_expression::createExpressionTree(std::vector<std::string> expression) in your tree class so that it can access private fields. I believe that in general you want to do the first method because using friends is considered hackish. Both will allow you to access the private fields and should allow you to reuse your createExpressionTree. — Jason Zhu

Unknown Unknown · Accepted Answer · 2012-05-05T02:34:10

I don't think there would be any difference between the class and structure version(the only difference between structs and classes is that classes have data private by default).

If he only wants you to change the word "struct" to "class", then you can access leftPtr/rightPtr by using the access modifier "public"

Example:

struct blah
{
  int boringNumbers;
  string boringStrings;
};

Is the same as:

class blah2
{
public:
  int boringNumbers;
  string boringStrings;
};

However, he might also want you to design your application to move more code into the class.

That would at the very least include moving functions such as char_is_operator into the class.

I doubt it, but he/she might also want you to create a hierarchy of nodes so you don't need to store data as generic strings.

Class Tree vs Structure TreeNode

1 Answers