Expression Tree in C
Write a program to implement Expression Tree using C Language with the following features :
- Recursive Traverse
- Iterative Traverse
Also Implement post fix and prefix Operations by both ways.
Expression Tree using C Language Code
|
1 2 |
<br/> #include <br/> #include <br/> #include <br/> typedef struct tree <br/> { <br/> char data; <br/> struct tree *lc; <br/> struct tree *rc; <br/> }tree; <br/> typedef struct stack1 <br/> { <br/> int flag; <br/> struct tree * addr; <br/> struct stack1 *link; <br/> }stack1; <br/> tree * freeall(tree *); <br/> void prefix(char []); <br/> void postfix(char []); <br/> void display(char []); <br/> tree *ptprefix(char [],int *); <br/> tree *ptpostfix(char [],int *); <br/> tree *alloc(char); <br/> void recin(tree *); <br/> void recpost(tree *); <br/> void recpre(tree *); <br/> void itin(tree *); <br/> void itpre(tree *); <br/> void itpost(tree *); <br/> void main() <br/> { <br/> int ch,ch1,i; <br/> char str[50]; <br/> tree *f=NULL; <br/> clrscr(); <br/> do <br/> { <br/> clrscr(); <br/> printf("\n\t\t1.INPUT\n\t\t2.RECURSIVE TRAVERSE\n\t\t3.ITERATIVE TRAVERSE\n\t\t4.EXIT"); <br/> scanf("%d",&ch); <br/> switch(ch) <br/> { <br/> case 1: <br/> printf("\n\t\tINPUT MENU\n\t\t1.PREFIX EXPRESSION\n\t\t2.POSTFIX EXPRESSION\n\t\t3.EXIT"); <br/> scanf("%d",&ch1); <br/> switch(ch1) <br/> { <br/> case 1: <br/> if(f!=NULL) <br/> f=freeall(f); <br/> printf("\n\t\tPREFIX EXPRESSION"); <br/> prefix(str); <br/> i=0; <br/> f=ptprefix(str,&i); <br/> break; <br/> case 2: <br/> if(f!=NULL) <br/> f=freeall(f); <br/> printf("\n\t\tPOSTFIX EXPRESSION"); <br/> postfix(str); <br/> i=strlen(str)-1; <br/> f=ptpostfix(str,&i); <br/> break; <br/> case 3: <br/> break; <br/> default: <br/> printf("\n\t\tINVALID CHOICE"); <br/> } <br/> break; <br/> case 2: <br/> if(f==NULL) <br/> printf("\n\t\tENTER INPUT FIRST"); <br/> else <br/> do <br/> { <br/> clrscr(); <br/> printf("\n\t\tRECURSIVE TRAVERSE MENU\n\t\t1.INORDER\n\t\t2.POSTORDER\n\t\t3.PREORDER\n\t\t4.EXIT"); <br/> scanf("%d",&ch1); <br/> switch(ch1) <br/> { <br/> case 1: <br/> printf("\n\t\tINORDER"); <br/> recin(f); <br/> break; <br/> case 2: <br/> printf("\n\t\tPOSTORDER"); <br/> recpost(f); <br/> break; <br/> case 3: <br/> printf("\n\t\tPREORDER"); <br/> recpre(f); <br/> break; <br/> case 4: <br/> break; <br/> default: <br/> printf("\n\t\tINVALID CHOICE"); <br/> } <br/> getch(); <br/> }while(ch1!=4); <br/> getch(); <br/> break; <br/> case 3: <br/> if(f==NULL) <br/> printf("\n\t\tENTER INPUT FIRST"); <br/> else <br/> do <br/> { <br/> clrscr(); <br/> printf("\n\t\tITERATIVE TRAVERSE MENU\n\t\t1.INORDER\n\t\t2.POSTORDER\n\t\t3.PREORDER\n\t\t4.EXIT"); <br/> scanf("%d",&ch1); <br/> switch(ch1) <br/> { <br/> case 1: <br/> printf("\n\t\tINORDER"); <br/> itin(f); <br/> break; <br/> case 2: <br/> printf("\n\t\tPOSTORDER"); <br/> itpost(f); <br/> break; <br/> case 3: <br/> printf("\n\t\tPREORDER"); <br/> itpre(f); <br/> break; <br/> case 4: <br/> break; <br/> default: <br/> printf("\n\t\tINVALID CHOICE"); <br/> } <br/> }while(ch1!=4); <br/> getch(); <br/> break; <br/> case 4: <br/> break; <br/> default: <br/> printf("\n\t\tINVALID CHOICE"); <br/> } <br/> }while(ch!=4); <br/> } <br/> void prefix(char str[]) <br/> { <br/> int i=0,rank=0; <br/> while(1) <br/> { <br/> str[i++]=getche(); <br/> if(str[i-1]=='\r'&&i>2&&rank==1) <br/> break; <br/> else if(rank!=1&&(str[i-1]=='+'||str[i-1]=='-'||str[i-1]=='*'|| str[i-1]=='^'||str[i-1]=='/')) <br/> rank=rank-1; <br/> 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))) <br/> rank=rank+1; <br/> else <br/> { <br/> printf("\nINVALID ENTRY"); <br/> i=0; <br/> rank=0; <br/> } <br/> if(rank>1) <br/> { <br/> printf("\nINVALID ENTRY"); <br/> i=0; <br/> rank=0; <br/> } <br/> } <br/> str[i-1]=NULL; <br/> } <br/> void postfix(char str[]) <br/> { <br/> int i=0,rank=0; <br/> while(1) <br/> { <br/> str[i++]=getche(); <br/> if(str[i-1]=='\r'&&i>2&&rank==1) <br/> break; <br/> if(i>1&&(str[i-1]=='+'||str[i-1]=='-'||str[i-1]=='*'|| str[i-1]=='^'||str[i-1]=='/')) <br/> rank=rank-1; <br/> 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)) <br/> rank=rank+1; <br/> else <br/> { <br/> printf("\nINVALID ENTRY"); <br/> i=0; <br/> rank=0; <br/> } <br/> if(rank<1) <br/> { <br/> printf("\nINVALID ENTRY"); <br/> i=0; <br/> rank=0; <br/> } <br/> } <br/> str[i-1]=NULL; <br/> } <br/> tree *ptprefix(char str[],int *i) <br/> { <br/> tree *nw; <br/> nw=alloc(str[(*i)]); <br/> if(str[(*i)]=='+'||str[(*i)]=='-'||str[(*i)]=='*'|| str[(*i)]=='^'||str[(*i)]=='/') <br/> { <br/> ++*i; <br/> nw->lc=ptprefix(str,i); <br/> ++*i; <br/> nw->rc=ptprefix(str,i); <br/> } <br/> return nw; <br/> } <br/> tree * alloc(char c) <br/> { <br/> tree *nw; <br/> nw=(tree *)malloc(sizeof(tree)); <br/> nw->data=c; <br/> nw->lc=NULL; <br/> nw->rc=NULL; <br/> return nw; <br/> } <br/> tree *ptpostfix(char str[],int *i) <br/> { <br/> tree *nw; <br/> char c; <br/> nw=alloc(str[(*i)]); <br/> if(str[(*i)]=='+'||str[(*i)]=='-'||str[(*i)]=='*'|| str[(*i)]=='^'||str[(*i)]=='/') <br/> { <br/> --*i; <br/> nw->rc=ptpostfix(str,i); <br/> --*i; <br/> nw->lc=ptpostfix(str,i); <br/> } <br/> return nw; <br/> } <br/> void recin(tree *root) <br/> { <br/> if(root!=NULL) <br/> { <br/> if(root->lc!=NULL) <br/> printf("("); <br/> recin(root->lc); <br/> printf("%c",root->data); <br/> recin(root->rc); <br/> if(root->rc!=NULL) <br/> printf(")"); <br/> } <br/> } <br/> void recpost(tree *root) <br/> { <br/> if(root!=NULL) <br/> { <br/> recpost(root->lc); <br/> recpost(root->rc); <br/> printf("%c",root->data); <br/> } <br/> } <br/> void recpre(tree *root) <br/> { <br/> if(root!=NULL) <br/> { <br/> printf("%c",root->data); <br/> recpre(root->lc); <br/> recpre(root->rc); <br/> } <br/> } <br/> void itpre(tree *root) <br/> { <br/> tree *t; <br/> tree *st[30]; <br/> int top=-1; <br/> t=root; <br/> while(t!=NULL||top!=-1) <br/> { <br/> if(t!=NULL) <br/> { <br/> printf("%c",t->data); <br/> st[++top]=t; <br/> t=t->lc; <br/> } <br/> else <br/> { <br/> t=st[top--]; <br/> t=t->rc; <br/> } <br/> } <br/> getch(); <br/> } <br/> void itpost(tree *root) <br/> { <br/> tree *t; <br/> stack1 *top,*nw; <br/> top=NULL; <br/> t=root; <br/> while(t!=NULL||top!=NULL) <br/> { <br/> if(t!=NULL) <br/> { <br/> nw=(stack1 *)malloc(sizeof(stack1)); <br/> nw->addr=t; <br/> nw->link=top; <br/> nw->flag=0; <br/> top=nw; <br/> t=t->lc; <br/> } <br/> else <br/> { <br/> t=top->addr; <br/> if(top->flag==0) <br/> { <br/> top->flag=1; <br/> t=t->rc; <br/> } <br/> else <br/> { <br/> printf("%c",t->data); <br/> nw=top; <br/> top=top->link; <br/> free(nw); <br/> t=NULL; <br/> } <br/> } <br/> } <br/> getch(); <br/> } <br/> tree * freeall(tree *t) <br/> { <br/> tree * q; <br/> q=t; <br/> if(t!=NULL) <br/> { <br/> t=freeall(t->lc); <br/> t=freeall(q->rc); <br/> free(q); <br/> } <br/> return NULL; <br/> } <br/> void itin(tree *root) <br/> { <br/> tree *t; <br/> stack1 *top,*nw; <br/> top=NULL; <br/> t=root; <br/> while(t!=NULL||top!=NULL) <b r/> { <br/> if(t!=NULL) <br/> { <br/> if(t->lc!=NULL) <br/> printf("("); <br/> nw=(stack1 *)malloc(sizeof(stack1)); <br/> nw->addr=t; <br/> nw->link=top; <br/> nw->flag=0; <br/> top=nw; <br/> t=t->lc; <br/> } <br/> else <br/> { <br/> t=top->addr; <br/> if(top->flag==0) <br/> { <br/> top->flag=1; <br/> printf("%c",t->data); <br/> t=t->rc; <br/> } <br/> else <br/> { <br/> nw=top; <br/> top=top->link; <br/> t=nw->addr; <br/> free(nw); <br/> if(t->rc!=NULL) <br/> printf(")"); <br/> t=NULL; <br/> } <br/> } <br/> } <br/> getch(); <br/> } |
Source projectgeek.com
