Creating expression tree with class instead of struct. differences?
CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 2 of 2

Thread: Creating expression tree with class instead of struct. differences?

  1. #1
    Join Date
    Feb 2012
    Posts
    68

    Creating expression tree with class instead of struct. differences?

    I have a struct version, but dont know what needs to be changed in the createexpressiontree function of the class version. i was told it was very similar to the struct version, so I was thinking i could just copy and paste that version into my new version and just change names around to make it work, but am not sure which things in the class tree are equivalent to struct treenode version.


    Code:
     
    
    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;
    
    
    class arithmetic_expression
    {
    public:
    
        int inputRPN(std::string inputString);
        int inputInfix(std::string inputString);
        void printExpressionTree();
        void printRPN();
        void printInfix();
        int evaluate_Expression();
    
    private:
    
        TreeNodePtr topPtr;
        int char_is_operator(std::string check);
        std::vector<std::string> parse_string(std::string inString);
        void createExpressionTree(std::vector<std::string> expression);
        TreeNodePtr createTreeNode(std::string Op);
    
        void printTreeAsArithmeticExpression(TreeNodePtr treePtr, int indent);
        void postOrderArithmeticExpressionPrint(TreeNodePtr rootPtr);
        void inOrderArithmeticExpressionPrint(TreeNodePtr rootPtr);
        int evaluateTree(TreeNodePtr rootPtr);
        TreeNodePtr createNewTreeNode(std::string newNodeData);
        std::vector<std::string> Infix2RPN(std::vector<std::string> infix);
        int p(std::string check);
    
    };
    
    //here is the function to create the tree
    
    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;
            }
    
        }
    
    
    }
    
    //and the helper function to make nodes
    
    
    
    TreeNodePtr arithmetic_expression::createNewTreeNode(std::string newNodeData)
    {
    
        TreeNodePtr newNodePtr =  new(TreeNode);
    
        if (newNodePtr != NULL)
        {
            newNodePtr->leftPtr = NULL;
            newNodePtr->Op = newNodeData;
            newNodePtr->rightPtr = NULL;
        }
    
        return newNodePtr;
    }
    okay now here is the new version that uses class tree instead of struct treenode

    Code:
     
    
    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;
    
      };
    
    
    #endif
    
    
    // another header file i think may need to be used in my tree creating function :
    
    class RPNstring
    {
    public:
        RPNstring(std::string inString){ expression = inString; };
        std::string getString(){return(expression);}
    
    private:
        std::string expression;
    };
    
    class Infixstring
    {
    public:
        Infixstring(std::string inString){ expression = inString; };
        std::string getString(){return(expression);};
    private:
        std::string expression;
    };
    
    
    
    
    class arithmetic_expression
    {
    public:
        arithmetic_expression(RPNstring inString);
        arithmetic_expression(Infixstring inString);
        arithmetic_expression(const arithmetic_expression &inExpression);  //Copy constructor
        ~arithmetic_expression();  //Destructor
        arithmetic_expression & operator=(const arithmetic_expression &inExpression); //assignment operator
        void printRPN();
        void printInfix();
        int evaluate_Expression(std::map< std::string, int > ipmap);
    
    
    
    private:
        Tree *tree;  //pointer to root of expression tree
    
        void createExpressionTree(std::vector<std::string> expression); //create expression tree from RPN expression vector
        std::vector<std::string> parse_string(std::string inString); //supplied helper function to parse string and create expression vector.
        int char_is_operator(std::string check); //supplied helper function
    
       
    };
    
    
    // And now the function that is supposed to be very close to the struct version but i need help with the conversion :
    
    void arithmetic_expression::createExpressionTree(std::vector<std::string> expression){
    
    }

  2. #2
    Join Date
    Apr 1999
    Posts
    27,423

    Re: Creating expression tree with class instead of struct. differences?

    Quote Originally Posted by chucker View Post
    I have a struct version, but dont know what needs to be changed in the createexpressiontree function of the class version.
    You are using terminology incorrectly.

    There is no difference in C++ between a class and a struct, except that

    1) A struct has public members by default, while a class has private members by default.

    2) When deriving from a struct, the default is public inheritance, while deriving from a class, the default is private inheritance.

    That's it. There is no other difference between a struct and a class. So calling one version a "struct" version and the other a "class" version is not correct.

    You have two totally different versions, much more than using the struct or class keyword.

    Secondly, learn to pass items such as vectors, maps, and strings by reference, not by value. Here is an example of your code.
    Code:
    void createExpressionTree(std::vector<std::string> expression);
    You are passing "expression" by value. This means that after createExpressionTree() returns, the vector has not changed, regardless of how much work createExpressionTree() did to the vector. The reason is that passing by value creates a temporary copy of the parameter, and the function works on that copy. That copy is destroyed as soon as the function returns, leaving the original alone.
    Code:
    void createExpressionTree(std::vector<std::string>& expression);
    This makes much more sense. Here, the original vector is passed as a reference, therefore the createExpressionTree function is working on the original vector.
    i was told it was very similar to the struct version, so I was thinking i could just copy and paste that version into my new version and just change names around to make it work, but am not sure which things in the class tree are equivalent to struct treenode version.
    C++ is not a language where you can just copy and paste things and not know what you're doing. It isn't a Word document.

    If you don't know what you're doing when you alter functions, move declarations around, change code, then I suggest you don't do it until you learn the language properly.

    Regards,

    Paul McKenzie

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  


Azure Activities Information Page

Windows Mobile Development Center


Click Here to Expand Forum to Full Width

This is a CodeGuru survey question.


Featured


HTML5 Development Center