PROGRAM TO MAKE AN EXPRESSION TREE.

#include<iostream.h>#include<string.h>
#include<ctype.h>
#include<process.h>

#define SIZE 25

struct tree
{
char data;
tree *left,*right;
};

class stack
{
public:
tree *arr[SIZE];
int top;
void push(tree*);
int findtop();
tree* pop();
bool isempty();
void display();
char gettop();
stack()
{
top=-1;
}
};

int stack::findtop()
{
return(top);
}

bool stack::isempty()
{
return(top==-1);
}

void stack::push(tree* ptr)
{
arr[++top]=ptr;
}

tree *stack::pop()
{
if(isempty())
return(NULL);
return(arr[top--]);
}

void stack::display()
{
cout<<endl;
if(isempty())
return;
for(int i=0;i<=top;i++)
cout<<arr[i]->data;
}

char stack::gettop()
{
if(isempty())
return('?');
return(arr[top]->data);
}

void makenode(tree **garb,int num)
{
(*garb)->data=num;
(*garb)->left=NULL;
(*garb)->right=NULL;
}

tree * maketree(tree *left,tree *right,tree **base)
{
(*base)->left=left;
(*base)->right=right;
return *base;
}

void preorder(tree *node)
{
cout<<" "<<node->data;
if(node->left!=NULL)
preorder(node->left);
if(node->right!=NULL)
preorder(node->right);
}
void inorder(tree *node)
{
if(node->left!=NULL)
inorder(node->left);
cout<<" "<<node->data;
if(node->right!=NULL)
inorder(node->right);
}

void postorder(tree *node)
{
if(node->left!=NULL)
postorder(node->left);
if(node->right!=NULL)
postorder(node->right);
cout<<" "<<node->data;
}

main()
{
char infix[SIZE];
int i;
stack pfix,oper;
tree *garb;
cout<<"\n ENTER THE INFIX EXPRESSION ::\n";
cin.getline(infix,SIZE);
int len=strlen(infix);
for(i=0;i<len;i++)
{
garb=new tree;
switch(infix[i])
{
case ' ': pfix.display();
break;
case '(':
case '$': makenode(&garb,infix[i]);
oper.push(garb);
break;
case '/':
case '*':
case '%': while((oper.gettop()=='$')||(oper.gettop()=='/')||(oper.gettop()=='*')||(oper.gettop()=='%')&&(oper.gettop()!='?'))
pfix.push(oper.pop());
makenode(&garb,infix[i]);
oper.push(garb);
break;
case '+':
case '-': while(oper.gettop()!='('&&oper.gettop()!='?')
pfix.push(oper.pop());
makenode(&garb,infix[i]);
oper.push(garb);
break;
case ')': while(oper.gettop()!='('&&!oper.isempty())
pfix.push(oper.pop());
oper.pop();
break;
default:  if(!isalnum(infix[i]))
{
cout<<"\n UNDEFINED SYMBOL "<<infix[i]<<endl;
exit(0);
}
else
{
makenode(&garb,infix[i]);
pfix.push(garb);
}
}
}
while(oper.gettop()!='?'&&!oper.isempty())
pfix.push(oper.pop());

stack mytree;
tree * root;
int n=pfix.findtop();
for(i=0;i<=n;i++)
{
if(isalnum(pfix.arr[i]->data))
mytree.push(pfix.arr[i]);
else
mytree.push(maketree(mytree.pop(),mytree.pop(),&pfix.arr[i]));
}
root=mytree.arr[0];
cout<<"\n PREORDER TRAVERSAL :\n";
preorder(root);
cout<<"\n INORDER TRAVERSAL :\n";
inorder(root);
cout<<"\n POSTORDER TRAVERSAL :\n";
postorder(root);
cout<<endl;
}

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s