Stack Operations using C Language
Implement stack as an abstract data type (ADT) using linked list.
Use this ADT for
- infix to prefix conversion
- infix to post fix conversion
- evaluation of post fix expression
Stack Operations using C Language Code
1 2 |
#include <br/> #include <br/> #include <br/> #include <br/> #include <br/> typedef struct stack <br/> { <br/> char data; <br/> struct stack * link; <br/> }stack; <br/> typedef struct eval <br/> { <br/> float data; <br/> struct eval * link; <br/> }eval; <br/> typedef struct val <br/> { <br/> char data; <br/> float value; <br/> struct val * link; <br/> }val; <br/> int pinppost(char); <br/> int pstppost(char); <br/> int pinppre(char); <br/> int pstppre(char); <br/> float posteval(char []); <br/> float preeval(char []); <br/> void create(char []); <br/> void postfix(char [],char []); <br/> void prefix(char [],char []); <br/> void display(char []); <br/> void main() <br/> { <br/> int ch; <br/> float j; <br/> char str[50],str1[50],str2[50]; <br/> float dummy; <br/> &dummy; <br/> str[0]=NULL; <br/> str1[0]=NULL; <br/> str2[0]=NULL; <br/> clrscr(); <br/> do <br/> { <br/> clrscr(); <br/> printf("\n\t\tOPERATION ON STACK\n\t\t1.INFIX EXPRESSION\n\t\t2.INFIX TO PREFIX\n\t\t3.INFIX TO POSTFIX\n\t\t4.EVALUATION FOR PREFIX\n\t\t5.EVALUATION FOR POSTFIX\n\t\t6.EXIT"); <br/> printf("\n\t\tENTER UR CHOICE"); <br/> flushall(); <br/> scanf("%d",&ch); <br/> switch(ch) <br/> { <br/> case 1: <br/> printf("\n\t\tINFIX EXPRESSION:"); <br/> create(str); <br/> display(str); <br/> break; <br/> case 2: <br/> if(str[0]==NULL) <br/> printf("enter input first"); <br/> else <br/> { <br/> printf("\n\t\tINFIX TO PREFIX :"); <br/> prefix(str,str2); <br/> printf("\nINFIX EXPRESSION IS:"); <br/> display(str); <br/> printf("\nPREFIX EXPRESSION IS:"); <br/> display(str2); <br/> } <br/> getch(); <br/> break; <br/> case 3: if(str[0]==NULL) <br/> printf("enter input first"); <br/> else <br/> { <br/> printf("\n\t\tINFIX TO POSTFIX EXPRESSION"); <br/> postfix(str,str1); <br/> printf("\nINFIX EXPRESSION IS:"); <br/> display(str); <br/> printf("\nPOSTFIX EXPRESSION IS:"); <br/> display(str1); <br/> } <br/> getch(); <br/> break; <br/> case 4: if(str[0]==NULL||str2[0]==NULL) <br/> printf("either you havnt given input or you havnt done conversion,first do that part "); <br/> else <br/> { <br/> printf("\n\t\tEVALUATION ON PREFIX EXPRESSION"); <br/> j=preeval(str2); <br/> printf("\nVALUE EVALUATED IS:%f",j); <br/> } <br/> getch(); <br/> break; <br/> case 5: if(str[0]==NULL||str1[0]==NULL) <br/> printf("either you havnt given input or you havnt done conversion,first do that part "); <br/> else <br/> { <br/> printf("\n\t\tEVALUATION ON POSTFIX EXPRESSION"); <br/> j=posteval(str1); <br/> printf("\nVALUE EVALUATED IS:%f",j); <br/> } <br/> getch(); <br/> break; <br/> case 6: <br/> printf("\n\t\tEXIT"); <br/> break; <br/> } <br/> }while(ch!=6); <br/> } <br/> void create(char str[]) <br/> { <br/> int rank=0,i=0,j=0,k,m,l; <br/> while(1) <br/> { <br/> str[i]=getche(); <br/> i++; <br/> if(str[i-1]=='\r') <br/> { <br/> if(rank!=1||j!=0||i<=2) <br/> { <br/> printf("\ninvalid exprexion,enter from starting"); <br/> j=0; <br/> rank=0; <br/> i=0; <br/> } <br/> else <br/> break; <br/> } <br/> else if(str[i-1]=='(') <br/> if(rank==1) <br/> { <br/> printf("\ninvalid exprexion,enter from starting"); <br/> i=0; <br/> j=0; <br/> rank=0; <br/> } <br/> else <br/> j++; <br/> else if(str[i-1]==')') <br/> if(rank==0) <br/> { <br/> printf("\ninvalid exprexion,enter from starting"); <br/> i=0; <br/> j=0; <br/> rank=0; <br/> } <br/> else <br/> j--; <br/> else if(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 if(str[i-1]!=')'&&str[i-1]!='(') <br/> { <br/> printf("\ninvalid entry,enter from starting"); <br/> i=0; <br/> j=0; <br/> rank=0; <br/> } <br/> if((rank!=1&&rank!=0)||j<0) <br/> { <br/> printf("\ninvalid exprexion,enter from starting"); <br/> i=0; <br/> j=0; <br/> rank=0; <br/> } <br/> } <br/> str[i]=NULL; <br/> } <br/> void display(char str[]) <br/> { <br/> int i=0; <br/> while(str[i]!=NULL) <br/> { <br/> printf("%c",str[i]); <br/> i++; <br/> } <br/> getch(); <br/> } <br/> void prefix(char str[],char str2[]) <br/> { <br/> int i,l,j; <br/> stack *nw,*top,*top1=NULL; <br/> l=strlen(str); <br/> i=l-1; <br/> for(j=l;j>0;j--) <br/> str[j]=str[j-1]; <br/> str[j]='#'; <br/> nw=(stack *)malloc(sizeof(stack)); <br/> nw->data='#'; <br/> top=nw; <br/> while(1) <br/> { <br/> while(pinppre(str[i])<pstppre(top->data)) <br/> { <br/> nw=(stack *)malloc(sizeof(stack)); <br/> nw->data=top->data; <br/> nw->link=top1; <br/> top1=nw; <br/> nw=top; <br/> top=top->link; <br/> free(nw); <br/> } <br/> if(pinppre(str[i])==pstppre(top->data)) <br/> { <br/> if(top->data=='#') <br/> break; <br/> nw=top; <br/> top=top->link; <br/> free(nw); <br/> i--; <br/> } <br/> else <br/> { <br/> nw=(stack *)malloc(sizeof(stack)); <br/> nw->data=str[i--]; <br/> nw->link=top; <br/> top=nw; <br/> } <br/> } <br/> for(j=0;j<l;j++) <br=""> { <br/> str[j]=str[j+1]; <br/> } <br/> str[l]=NULL; <br/> j=0; <br/> while(top1!=NULL) <br/> { <br/> str2[j]=top1->data; <br/> nw=top1; <br/> top1=top1->link; <br/> free(nw); <br/> j++; <br/> } <br/> str2[j]=NULL; <br/> } <br/> void postfix(char str[],char str1[]) <br/> { <br/> int l,i,j; <br/> stack *nw,*top; <br/> i=j=0; <br/> l=strlen(str); <br/> str[l-1]='#'; <br/> nw=(stack *)malloc(sizeof(stack)); <br/> nw->data='#'; <br/> top=nw; <br/> while(1) <br/> { <br/> while(pinppost(str[i])<pstppost(top->data)) <br/> { <br/> str1[j++]=top->data; <br/> nw=top; <br/> top=top->link; <br/> free(nw); <br/> } <br/> if(pinppost(str[i])==pstppost(top->data)) <br/> { <br/> if(top->data=='#') <br/> break; <br/> nw=top; <br/> top=top->link; <br/> free(nw); <br/> i++; <br/> } <br/> else <br/> { <br/> nw=(stack *)malloc(sizeof(stack)); <br/> nw->data=str[i++]; <br/> nw->link=top; <br/> top=nw; <br/> } <br/> } <br/> str[l-1]=NULL; <br/> str1[j]=NULL; <br/> } <br/> int pinppost(char c) <br/> { <br/> switch(c) <br/> { <br/> case '#': return(-1); <br/> case '*': <br/> case '/': return(3); <br/> case '+': <br/> case '-': return(1); <br/> case '^': return(6); <br/> case '(': return(8); <br/> case ')': return(0); <br/> } <br/> return(7); <br/> } <br/> int pstppost(char c) <br/> { <br/> switch(c) <br/> { <br/> case '#': return(-1); <br/> case '*': <br/> case '/': return(4); <br/> case '+': <br/> case '-': return(2); <br/> case '^': return(5); <br/> case '(': return(0); <br/> } <br/> return(7); <br/> } <br/> int pinppre(char c) <br/> { <br/> switch(c) <br/> { <br/> case '#': return(-1); <br/> case '*': <br/> case '/': return(4); <br/> case '+': <br/> case '-': return(2); <br/> case '^': return(5); <br/> case '(': return(0); <br/> case ')': return(8); <br/> } <br/> return(7); <br/> } <br/> int pstppre(char c) <br/> { <br/> switch(c) <br/> { <br/> case '#': return(-1); <br/> case '*': <br/> case '/': return(3); <br/> case '+': <br/> case '-': return(1); <br/> case '^': return(6); <br/> case ')': return(0); <br/> } <br/> return(7); <br/> } <br/> float posteval(char str1[]) <br/> { <br/> val *nw,*t,*top=NULL; <br/> eval *nw1,*top1=NULL; <br/> int i; <br/> float opr1; <br/> char op; <br/> i=0; <br/> for(i=0;str1[i]!=NULL;i++) <br/> { <br/> if(str1[i]!='+'&&str1[i]!='-'&&str1[i]!='*'&& str1[i]!='^'&&str1[i]!='/') <br/> { <br/> nw=top; <br/> while(nw!=NULL) <br/> { <br/> if(str1[i]==nw->data) <br/> break; <br/> nw=nw->link; <br/> } <br/> if(nw==NULL) <br/> { <br/> nw=(val *)malloc(sizeof(val)); <br/> nw->data=str1[i]; <br/> printf("ENTER THE VALUE OF %c:",str1[i]); <br/> scanf("%f",&(nw->value)); <br/> nw->link=top; <br/> top=nw; <br/> } <br/> nw1=(eval *)malloc(sizeof(eval)); <br/> nw1->data=nw->value; <br/> nw1->link=top1; <br/> top1=nw1; <br/> } <br/> else <br/> { <br/> op=str1[i]; <br/> opr1=top1->data; <br/> nw1=top1; <br/> top1=top1->link; <br/> free(nw1); <br/> switch(op) <br/> { <br/> case '*':opr1=top1->data*opr1; <br/> break; <br/> case '/':opr1=top1->data/opr1; <br/> break; <br/> case '+':opr1=top1->data+opr1; <br/> break; <br/> case '-':opr1=top1->data-opr1; <br/> break; <br/> case '^':opr1=pow(top1->data,opr1); <br/> break; <br/> } <br/> top1->data=opr1; <br/> } <br/> } <br/> opr1=top1->data; <br/> free(top1); <br/> return(opr1); <br/> } <br/> float preeval(char str[]) <br/> { <br/> val *nw,*t,*top=NULL; <br/> eval *nw1,*top1=NULL; <br/> int i,n; <br/> float opr1,opr2; <br/> char op; <br/> i=0; <br/> for(i=0;str[i]!=NULL;i++) <br/> { <br/> if(str[i]!='+'&&str[i]!='-'&&str[i]!='*'&& str[i]!='^'&&str[i]!='/') <br/> { <br/> nw=top; <br/> while(nw!=NULL) <br/> { <br/> if(str[i]==nw->data) <br/> break; <br/> nw=nw->link; <br/> } <br/> if(nw==NULL) <br/> { <br/> nw=(val *)malloc(sizeof(val)); <br/> nw->data=str[i]; <br/> printf("ENTER THE VALUE OF %c:",str[i]); <br/> scanf("%f",&(nw->value)); <br/> nw->link=top; <br/> top=nw; <br/> } <br/> opr1=nw->value; <br/> while(1) <br/> { <br/> if(top1==NULL||top1->data=='+'||top1->data=='-'||top1->data=='*'||top1->data=='/'||top1->data=='^') <br/> break; <br/> opr2=top1->data; <br/> nw1=top1; <br/> top1=top1->link; <br/> free(nw1); <br/> op=(char)top1->data; <br/> nw1=top1; <br/> top1=top1->link; <br/> free(nw1); <br/> switch(op) <br/> { <br/> case '*':opr1=opr2*opr1; <br/> break; <br/> case '/':opr1=opr2/opr1; <br/> break; <br/> case '+':opr1=opr2+opr1; <br/> break; <br/> case '-':opr1=opr2-opr1; <br/> break; <br/> case '^':opr1=pow(opr2,opr1); <br/> break; <br/> } <br/> } <br/> nw1=(eval*)malloc(sizeof(eval)); <br/> nw1->data=opr1; <br/> nw1->link=top1; <br/> top1=nw1; <br/> } <br/> else <br/> { <br/> nw1=(eval*)malloc(sizeof(eval)); <br/> nw1->data=(float)str[i]; <br/> nw1->link=top1; <br/> top1=nw1; <br/> } <br/> } <br/> opr1=top1->data; <br/> free(top1); <br/> return(opr1); <br/> } |
Source projectgeek.com