Construction of expression tree using Postfix Expression
Implementation of construction of expression tree using postfix
Expression.
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
typedef struct treenode
{
char data;
struct treenode
*left;
struct treenode
*right;
}treenode;
typedef struct stack
{
treenode *data[20];
int top;
}stack;
void init(stack *s)
{
s->top=-1;
}
treenode *pop(stack *s)
{
treenode *p;
p=s->data[s->top];
s->top=s->top-1;
return(p);
}
void push(stack
*s,treenode *p)
{
s->top=s->top+1;
s->data[s->top]=p;
}
int empty(stack *s)
{
if(s->top==-1)
return 1;
return 0;
}
int full(stack *s)
{
if(s->top==19)
return 1;
return 0;
}
treenode *create();
void inorder(treenode *);
void preorder(treenode *);
void postorder(treenode
*);
void main()
{
treenode *root=NULL,*p;
int x,op;
clrscr();
do
{
printf("\n\n1]Create\n2]Preoder\n3]Inorder\n4]Postorder\n5]Quit\n");
printf("Enter your choice\n");
scanf("%d",&op);
switch(op)
{
case
1: root=create();
break;
case
2: preorder(root);
break;
case
3: inorder(root);
break;
case
4: postorder(root);
break;
}
}while(op!=5);
}
treenode *create()
{
char a[50];
int i;
treenode *p,*q,*root;
stack s;
init(&s);
flushall();
printf("\nEnter a postfix expression\n");
gets(a);
for(i=0;a[i]!='\0';i++)
{
if(isalnum(a[i]))
{
p=(treenode*)malloc(sizeof(treenode));
p->left=p->right=NULL;
p->data=a[i];
push(&s,p);
}
else
{
q=pop(&s);
p=pop(&s);
root=(treenode*)malloc(sizeof(treenode));
root->left=p;
root->right=q;
root->data=a[i];
push(&s,root);
}
}
root=pop(&s);
return root;
}
void inorder(treenode *T)
{
if(T!=NULL)
{
inorder(T->left);
printf("%c",T->data);
inorder(T->right);
}
}
void preorder(treenode *T)
{
if(T!=NULL)
{
printf("%c",T->data);
preorder(T->left);
preorder(T->right);
}
}
void postorder(treenode
*T)
{
if(T!=NULL)
{
postorder(T->left);
postorder(T->right);
printf("%c",T->data);
}
}
Output:
Comments
Post a Comment