Go4Expert

Go4Expert (http://www.go4expert.com/)
-   C++ (http://www.go4expert.com/forums/cpp/)
-   -   Binary Expression Tree for infix - postfix - (http://www.go4expert.com/forums/binary-expression-tree-infix-postfix-t7487/)

aladdin8_3 23Nov2007 21:54

Binary Expression Tree for infix - postfix -
 
hello all,

This is my first post in this forum. I would like to apologize ahead of time if I'm posting in the wrong place.

My Problem:
~We are given a class project involving Binary Expression Tree. Where I must take a Infix notation convert it to postfix and finally build a Binary Expression Tree from the postfix. I do not have to evaluate this unless I really want to.

My algorithm involves taking each element in the postfix and converting it to a binary expression tree. Which will be inserted into a stack and later Pop-d from the Stack to build a complete Tree.

I require help in passing the same pointer in Binary Expression Tree and in Stack. Below is my Code.


Following is the TreeNode class which will be passed as storage for elements.

Code: C++

class treeNode{
    //TreeNode is the class that I will pass into Binary Expression Tree and Stack
public:
    char element;
    treeNode * left;
    treeNode * right;

};


Following is Stack header file (Stack.h)
Code: C++

#include "treeNode.h"

class ListNode{

public:
     //char element;
    treeNode * element;
    ListNode *next;
};

class Stack{

public:

    Stack();
    ~Stack();
    bool isEmpty();
    treeNode * top(); //should display the last element in the stack
    void makeEmpty();
    void pop(); //should delete the last element in the stack
    void push(treeNode * e);//inserts a new element to the end
    treeNode * topAndPop();//displays the last element + removes it.



private:
    ListNode*head;
};


Following is Binary Expression Tree (BET) header file
Code: C++

#include "treeNode.h"

class BinaryNode {
public:
    treeNode *element;
    BinaryNode * right;
    BinaryNode * left;
};
class BET{

public:
    BET();
    ~BET();


    void insert(treeNode *e);
//  void remove(int i);
    void printSorted();

private:
    BinaryNode * root;
    BinaryNode * insert(BinaryNode * t, treeNode *e);//should work recursively

    void printSorted(BinaryNode * t);
};


Following is Stack.cpp File

Code: C++

#include "Stack.h"
#include <stdio.h>
#include <stdlib.h>


Stack::Stack(){
    head=NULL;
}


bool Stack::isEmpty()
{
    if(head==NULL)
        return true;
    return false;
}




treeNode * Stack::top()
{
    if(head!=NULL)
       
   
        return head->element;

    return NULL;
}



void Stack::push(treeNode * e)
{
    if(head==NULL)
    {
        ListNode*n= new ListNode;
        n->element=e;
        n->next=NULL;
        head=n;
        return;
    }


ListNode * n =new ListNode;
n->element=e;
n->next=head;
head=n;
return;
}


void Stack::pop()
{
    if(head==NULL)
        return;
    if(head->next==NULL)
    {
        delete head;
        head=NULL;
        return;
    }


    ListNode *t;
    t=head;
    head=head->next;
    delete t;
    return;
}



treeNode * Stack::topAndPop()
{
    treeNode *n =top();
    pop();
   
    return n;
}


void Stack::makeEmpty()
{
    while(!isEmpty())
    {
        pop();
    }
}


Following is BET.cpp

Code: C++

#include "BET.h"
#include <iostream>
//#include "treeNode.h"


using namespace std;

BET::BET()
{
    root = NULL;

}

void BET::insert(treeNode *i)
{
     root=insert(root, i);
}

BinaryNode * BET::insert(BinaryNode * t, treeNode *e)
{
//should work recursively here. 
            return t;
       
}
   

void BET::printSorted()
{

    printSorted(root);
}

void BET::printSorted(BinaryNode * t)
{
    if(t==NULL)
        cout<<"NuLL"<<endl;
        return;
    printSorted(t->left);
    cout<<t->element<<endl;
    printSorted(t->right);
}

I would like some assurance if I am doing this the right way. And plz feel free to ask me if my code seems confusing.

abbasi 9Jan2011 17:30

Re: Binary Expression Tree for infix - postfix -
 
Quote:

Originally Posted by aladdin8_3 (Post 20871)
hello all,

This is my first post in this forum. I would like to apologize ahead of time if I'm posting in the wrong place.

My Problem:
~We are given a class project involving Binary Expression Tree. Where I must take a Infix notation convert it to postfix and finally build a Binary Expression Tree from the postfix. I do not have to evaluate this unless I really want to.

My algorithm involves taking each element in the postfix and converting it to a binary expression tree. Which will be inserted into a stack and later Pop-d from the Stack to build a complete Tree.

I require help in passing the same pointer in Binary Expression Tree and in Stack. Below is my Code.


Following is the TreeNode class which will be passed as storage for elements.

Code: C++

class treeNode{
    //TreeNode is the class that I will pass into Binary Expression Tree and Stack
public:
    char element;
    treeNode * left;
    treeNode * right;

};


Following is Stack header file (Stack.h)
Code: C++

#include "treeNode.h"

class ListNode{

public:
     //char element;
    treeNode * element;
    ListNode *next;
};

class Stack{

public:

    Stack();
    ~Stack();
    bool isEmpty();
    treeNode * top(); //should display the last element in the stack
    void makeEmpty();
    void pop(); //should delete the last element in the stack
    void push(treeNode * e);//inserts a new element to the end
    treeNode * topAndPop();//displays the last element + removes it.



private:
    ListNode*head;
};


Following is Binary Expression Tree (BET) header file
Code: C++

#include "treeNode.h"

class BinaryNode {
public:
    treeNode *element;
    BinaryNode * right;
    BinaryNode * left;
};
class BET{

public:
    BET();
    ~BET();


    void insert(treeNode *e);
//  void remove(int i);
    void printSorted();

private:
    BinaryNode * root;
    BinaryNode * insert(BinaryNode * t, treeNode *e);//should work recursively

    void printSorted(BinaryNode * t);
};


Following is Stack.cpp File

Code: C++

#include "Stack.h"
#include <stdio.h>
#include <stdlib.h>


Stack::Stack(){
    head=NULL;
}


bool Stack::isEmpty()
{
    if(head==NULL)
        return true;
    return false;
}




treeNode * Stack::top()
{
    if(head!=NULL)
       
   
        return head->element;

    return NULL;
}



void Stack::push(treeNode * e)
{
    if(head==NULL)
    {
        ListNode*n= new ListNode;
        n->element=e;
        n->next=NULL;
        head=n;
        return;
    }


ListNode * n =new ListNode;
n->element=e;
n->next=head;
head=n;
return;
}


void Stack::pop()
{
    if(head==NULL)
        return;
    if(head->next==NULL)
    {
        delete head;
        head=NULL;
        return;
    }


    ListNode *t;
    t=head;
    head=head->next;
    delete t;
    return;
}



treeNode * Stack::topAndPop()
{
    treeNode *n =top();
    pop();
   
    return n;
}


void Stack::makeEmpty()
{
    while(!isEmpty())
    {
        pop();
    }
}


Following is BET.cpp

Code: C++

#include "BET.h"
#include <iostream>
//#include "treeNode.h"


using namespace std;

BET::BET()
{
    root = NULL;

}

void BET::insert(treeNode *i)
{
     root=insert(root, i);
}

BinaryNode * BET::insert(BinaryNode * t, treeNode *e)
{
//should work recursively here. 
            return t;
       
}
   

void BET::printSorted()
{

    printSorted(root);
}

void BET::printSorted(BinaryNode * t)
{
    if(t==NULL)
        cout<<"NuLL"<<endl;
        return;
    printSorted(t->left);
    cout<<t->element<<endl;
    printSorted(t->right);
}

I would like some assurance if I am doing this the right way. And plz feel free to ask me if my code seems confusing.

kindly post the "main()" of ur program

abbasi 9Jan2011 17:31

Re: Binary Expression Tree for infix - postfix -
 
kindly post the "main()" of ur code


All times are GMT +5.5. The time now is 07:52.