Expression Tree in C

Write a program to implement Expression Tree using C Language with the following features :

• Recursive Traverse
• Iterative Traverse

 
 #include  
 #include  
 #include  
 typedef struct tree  
 {  
 char data;  
 struct tree *lc;  
 struct tree *rc;  
 }tree;  
 typedef struct stack1  
 {  
 int flag;  
 struct tree * addr;  
 struct stack1 *link;  
 }stack1;  
 tree * freeall(tree *);  
 void prefix(char []);  
 void postfix(char []);  
 void display(char []);  
 tree *ptprefix(char [],int *);  
 tree *ptpostfix(char [],int *);  
 tree *alloc(char);  
 void recin(tree *);  
 void recpost(tree *);  
 void recpre(tree *);  
 void itin(tree *);  
 void itpre(tree *);  
 void itpost(tree *);  
 void main()  
 {  
 int ch,ch1,i;  
 char str[50];  
 tree *f=NULL;  
 clrscr();  
 do  
 {  
 clrscr();  
 printf("\n\t\t1.INPUT\n\t\t2.RECURSIVE TRAVERSE\n\t\t3.ITERATIVE TRAVERSE\n\t\t4.EXIT");  
 scanf("%d",&ch);  
 switch(ch)  
 {  
 case 1:  
 printf("\n\t\tINPUT MENU\n\t\t1.PREFIX EXPRESSION\n\t\t2.POSTFIX EXPRESSION\n\t\t3.EXIT");  
 scanf("%d",&ch1);  
 switch(ch1)  
 {  
 case 1:  
 if(f!=NULL)  
 f=freeall(f);  
 printf("\n\t\tPREFIX EXPRESSION");  
 prefix(str);  
 i=0;  
 f=ptprefix(str,&i);  
 break;  
 case 2:  
 if(f!=NULL)  
 f=freeall(f);  
 printf("\n\t\tPOSTFIX EXPRESSION");  
 postfix(str);  
 i=strlen(str)-1;  
 f=ptpostfix(str,&i);  
 break;  
 case 3:  
 break;  
 default:  
 printf("\n\t\tINVALID CHOICE");  
 }  
 break;  
 case 2:  
 if(f==NULL)  
 printf("\n\t\tENTER INPUT FIRST");  
 else  
 do  
 {  
 clrscr();  
 printf("\n\t\tRECURSIVE TRAVERSE MENU\n\t\t1.INORDER\n\t\t2.POSTORDER\n\t\t3.PREORDER\n\t\t4.EXIT");  
 scanf("%d",&ch1);  
 switch(ch1)  
 {  
 case 1:  
 printf("\n\t\tINORDER");  
 recin(f);  
 break;  
 case 2:  
 printf("\n\t\tPOSTORDER");  
 recpost(f);  
 break;  
 case 3:  
 printf("\n\t\tPREORDER");  
 recpre(f);  
 break;  
 case 4:  
 break;  
 default:  
 printf("\n\t\tINVALID CHOICE");  
 }  
 getch();  
 }while(ch1!=4);  
 getch();  
 break;  
 case 3:  
 if(f==NULL)  
 printf("\n\t\tENTER INPUT FIRST");  
 else  
 do  
 {  
 clrscr();  
 printf("\n\t\tITERATIVE TRAVERSE MENU\n\t\t1.INORDER\n\t\t2.POSTORDER\n\t\t3.PREORDER\n\t\t4.EXIT");  
 scanf("%d",&ch1);  
 switch(ch1)  
 {  
 case 1:  
 printf("\n\t\tINORDER");  
 itin(f);  
 break;  
 case 2:  
 printf("\n\t\tPOSTORDER");  
 itpost(f);  
 break;  
 case 3:  
 printf("\n\t\tPREORDER");  
 itpre(f);  
 break;  
 case 4:  
 break;  
 default:  
 printf("\n\t\tINVALID CHOICE");  
 }  
 }while(ch1!=4);  
 getch();  
 break;  
 case 4:  
 break;  
 default:  
 printf("\n\t\tINVALID CHOICE");  
 }  
 }while(ch!=4);  
 }  
 void prefix(char str[])  
 {  
 int i=0,rank=0;  
 while(1)  
 {  
 str[i++]=getche();  
 if(str[i-1]=='\r'&&i>2&&rank==1)  
 break;  
 else if(rank!=1&&(str[i-1]=='+'||str[i-1]=='-'||str[i-1]=='*'|| str[i-1]=='^'||str[i-1]=='/'))  
 rank=rank-1;  
 else if(((str[i-1]>=48&&str[i-1]<=57)||(str[i-1]>=65&&str[i-1]<=90)||(str[i-1]>=97&&str[i-1]<=122)))  
 rank=rank+1;  
 else  
 {  
 printf("\nINVALID ENTRY");  
 i=0;  
 rank=0;  
 }  
 if(rank>1)  
 {  
 printf("\nINVALID ENTRY");  
 i=0;  
 rank=0;  
 }  
 }  
 str[i-1]=NULL;  
 }  
 void postfix(char str[])  
 {  
 int i=0,rank=0;  
 while(1)  
 {  
 str[i++]=getche();  
 if(str[i-1]=='\r'&&i>2&&rank==1)  
 break;  
 if(i>1&&(str[i-1]=='+'||str[i-1]=='-'||str[i-1]=='*'|| str[i-1]=='^'||str[i-1]=='/'))  
 rank=rank-1;  
 else if((str[i-1]>=48&&str[i-1]<=57)||(str[i-1]>=65&&str[i-1]<=90)||(str[i-1]>=97&&str[i-1]<=122))  
 rank=rank+1;  
 else  
 {  
 printf("\nINVALID ENTRY");  
 i=0;  
 rank=0;  
 }  
 if(rank<1)  
 {  
 printf("\nINVALID ENTRY");  
 i=0;  
 rank=0;  
 }  
 }  
 str[i-1]=NULL;  
 }  
 tree *ptprefix(char str[],int *i)  
 {  
 tree *nw;  
 nw=alloc(str[(*i)]);  
 if(str[(*i)]=='+'||str[(*i)]=='-'||str[(*i)]=='*'|| str[(*i)]=='^'||str[(*i)]=='/')  
 {  
 ++*i;  
 nw->lc=ptprefix(str,i);  
 ++*i;  
 nw->rc=ptprefix(str,i);  
 }  
 return nw;  
 }  
 tree * alloc(char c)  
 {  
 tree *nw;  
 nw=(tree *)malloc(sizeof(tree));  
 nw->data=c;  
 nw->lc=NULL;  
 nw->rc=NULL;  
 return nw;  
 }  
 tree *ptpostfix(char str[],int *i)  
 {  
 tree *nw;  
 char c;  
 nw=alloc(str[(*i)]);  
 if(str[(*i)]=='+'||str[(*i)]=='-'||str[(*i)]=='*'|| str[(*i)]=='^'||str[(*i)]=='/')  
 {  
 --*i;  
 nw->rc=ptpostfix(str,i);  
 --*i;  
 nw->lc=ptpostfix(str,i);  
 }  
 return nw;  
 }  
 void recin(tree *root)  
 {  
 if(root!=NULL)  
 {  
 if(root->lc!=NULL)  
 printf("(");  
 recin(root->lc);  
 printf("%c",root->data);  
 recin(root->rc);  
 if(root->rc!=NULL)  
 printf(")");  
 }  
 }  
 void recpost(tree *root)  
 {  
 if(root!=NULL)  
 {  
 recpost(root->lc);  
 recpost(root->rc);  
 printf("%c",root->data);  
 }  
 }  
 void recpre(tree *root)  
 {  
 if(root!=NULL)  
 {  
 printf("%c",root->data);  
 recpre(root->lc);  
 recpre(root->rc);  
 }  
 }  
 void itpre(tree *root)  
 {  
 tree *t;  
 tree *st[30];  
 int top=-1;  
 t=root;  
 while(t!=NULL||top!=-1)  
 {  
 if(t!=NULL)  
 {  
 printf("%c",t->data);  
 st[++top]=t;  
 t=t->lc;  
 }  
 else  
 {  
 t=st[top--];  
 t=t->rc;  
 }  
 }  
 getch();  
 }  
 void itpost(tree *root)  
 {  
 tree *t;  
 stack1 *top,*nw;  
 top=NULL;  
 t=root;  
 while(t!=NULL||top!=NULL)  
 {  
 if(t!=NULL)  
 {  
 nw=(stack1 *)malloc(sizeof(stack1));  
 nw->addr=t;  
 nw->link=top;  
 nw->flag=0;  
 top=nw;  
 t=t->lc;  
 }  
 else  
 {  
 t=top->addr;  
 if(top->flag==0)  
 {  
 top->flag=1;  
 t=t->rc;  
 }  
 else  
 {  
 printf("%c",t->data);  
 nw=top;  
 top=top->link;  
 free(nw);  
 t=NULL;  
 }  
 }  
 }  
 getch();  
 }  
 tree * freeall(tree *t)  
 {  
 tree * q;  
 q=t;  
 if(t!=NULL)  
 {  
 t=freeall(t->lc);  
 t=freeall(q->rc);  
 free(q);  
 }  
 return NULL;  
 }  
 void itin(tree *root)  
 {  
 tree *t;  
 stack1 *top,*nw;  
 top=NULL;  
 t=root;  
 while(t!=NULL||top!=NULL)  
 {  
 if(t!=NULL)  
 {  
 if(t->lc!=NULL)  
 printf("(");  
 nw=(stack1 *)malloc(sizeof(stack1));  
 nw->addr=t;  
 nw->link=top;  
 nw->flag=0;  
 top=nw;  
 t=t->lc;  
 }  
 else  
 {  
 t=top->addr;  
 if(top->flag==0)  
 {  
 top->flag=1;  
 printf("%c",t->data);  
 t=t->rc;  
 }  
 else  
 {  
 nw=top;  
 top=top->link;  
 t=nw->addr;  
 free(nw);  
 if(t->rc!=NULL)  
 printf(")");  
 t=NULL;  
 }  
 }  
 }  
 getch();  
 }