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
#include
#include
#include
#include
#include
typedef struct stack
{
char data;
struct stack * link;
}stack;
typedef struct eval
{
float data;
struct eval * link;
}eval;
typedef struct val
{
char data;
float value;
struct val * link;
}val;
int pinppost(char);
int pstppost(char);
int pinppre(char);
int pstppre(char);
float posteval(char []);
float preeval(char []);
void create(char []);
void postfix(char [],char []);
void prefix(char [],char []);
void display(char []);
void main()
{
int ch;
float j;
char str[50],str1[50],str2[50];
float dummy;
&dummy;
str[0]=NULL;
str1[0]=NULL;
str2[0]=NULL;
clrscr();
do
{
clrscr();
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");
printf("\n\t\tENTER UR CHOICE");
flushall();
scanf("%d",&ch);
switch(ch)
{
case 1:
printf("\n\t\tINFIX EXPRESSION:");
create(str);
display(str);
break;
case 2:
if(str[0]==NULL)
printf("enter input first");
else
{
printf("\n\t\tINFIX TO PREFIX :");
prefix(str,str2);
printf("\nINFIX EXPRESSION IS:");
display(str);
printf("\nPREFIX EXPRESSION IS:");
display(str2);
}
getch();
break;
case 3: if(str[0]==NULL)
printf("enter input first");
else
{
printf("\n\t\tINFIX TO POSTFIX EXPRESSION");
postfix(str,str1);
printf("\nINFIX EXPRESSION IS:");
display(str);
printf("\nPOSTFIX EXPRESSION IS:");
display(str1);
}
getch();
break;
case 4: if(str[0]==NULL||str2[0]==NULL)
printf("either you havnt given input or you havnt done conversion,first do that part ");
else
{
printf("\n\t\tEVALUATION ON PREFIX EXPRESSION");
j=preeval(str2);
printf("\nVALUE EVALUATED IS:%f",j);
}
getch();
break;
case 5: if(str[0]==NULL||str1[0]==NULL)
printf("either you havnt given input or you havnt done conversion,first do that part ");
else
{
printf("\n\t\tEVALUATION ON POSTFIX EXPRESSION");
j=posteval(str1);
printf("\nVALUE EVALUATED IS:%f",j);
}
getch();
break;
case 6:
printf("\n\t\tEXIT");
break;
}
}while(ch!=6);
}
void create(char str[])
{
int rank=0,i=0,j=0,k,m,l;
while(1)
{
str[i]=getche();
i++;
if(str[i-1]=='\r')
{
if(rank!=1||j!=0||i<=2)
{
printf("\ninvalid exprexion,enter from starting");
j=0;
rank=0;
i=0;
}
else
break;
}
else if(str[i-1]=='(')
if(rank==1)
{
printf("\ninvalid exprexion,enter from starting");
i=0;
j=0;
rank=0;
}
else
j++;
else if(str[i-1]==')')
if(rank==0)
{
printf("\ninvalid exprexion,enter from starting");
i=0;
j=0;
rank=0;
}
else
j--;
else if(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 if(str[i-1]!=')'&&str[i-1]!='(')
{
printf("\ninvalid entry,enter from starting");
i=0;
j=0;
rank=0;
}
if((rank!=1&&rank!=0)||j<0)
{
printf("\ninvalid exprexion,enter from starting");
i=0;
j=0;
rank=0;
}
}
str[i]=NULL;
}
void display(char str[])
{
int i=0;
while(str[i]!=NULL)
{
printf("%c",str[i]);
i++;
}
getch();
}
void prefix(char str[],char str2[])
{
int i,l,j;
stack *nw,*top,*top1=NULL;
l=strlen(str);
i=l-1;
for(j=l;j>0;j--)
str[j]=str[j-1];
str[j]='#';
nw=(stack *)malloc(sizeof(stack));
nw->data='#';
top=nw;
while(1)
{
while(pinppre(str[i])<pstppre(top->data))
{
nw=(stack *)malloc(sizeof(stack));
nw->data=top->data;
nw->link=top1;
top1=nw;
nw=top;
top=top->link;
free(nw);
}
if(pinppre(str[i])==pstppre(top->data))
{
if(top->data=='#')
break;
nw=top;
top=top->link;
free(nw);
i--;
}
else
{
nw=(stack *)malloc(sizeof(stack));
nw->data=str[i--];
nw->link=top;
top=nw;
}
}
for(j=0;j<l;j++) <br=""> {
str[j]=str[j+1];
}
str[l]=NULL;
j=0;
while(top1!=NULL)
{
str2[j]=top1->data;
nw=top1;
top1=top1->link;
free(nw);
j++;
}
str2[j]=NULL;
}
void postfix(char str[],char str1[])
{
int l,i,j;
stack *nw,*top;
i=j=0;
l=strlen(str);
str[l-1]='#';
nw=(stack *)malloc(sizeof(stack));
nw->data='#';
top=nw;
while(1)
{
while(pinppost(str[i])<pstppost(top->data))
{
str1[j++]=top->data;
nw=top;
top=top->link;
free(nw);
}
if(pinppost(str[i])==pstppost(top->data))
{
if(top->data=='#')
break;
nw=top;
top=top->link;
free(nw);
i++;
}
else
{
nw=(stack *)malloc(sizeof(stack));
nw->data=str[i++];
nw->link=top;
top=nw;
}
}
str[l-1]=NULL;
str1[j]=NULL;
}
int pinppost(char c)
{
switch(c)
{
case '#': return(-1);
case '*':
case '/': return(3);
case '+':
case '-': return(1);
case '^': return(6);
case '(': return(8);
case ')': return(0);
}
return(7);
}
int pstppost(char c)
{
switch(c)
{
case '#': return(-1);
case '*':
case '/': return(4);
case '+':
case '-': return(2);
case '^': return(5);
case '(': return(0);
}
return(7);
}
int pinppre(char c)
{
switch(c)
{
case '#': return(-1);
case '*':
case '/': return(4);
case '+':
case '-': return(2);
case '^': return(5);
case '(': return(0);
case ')': return(8);
}
return(7);
}
int pstppre(char c)
{
switch(c)
{
case '#': return(-1);
case '*':
case '/': return(3);
case '+':
case '-': return(1);
case '^': return(6);
case ')': return(0);
}
return(7);
}
float posteval(char str1[])
{
val *nw,*t,*top=NULL;
eval *nw1,*top1=NULL;
int i;
float opr1;
char op;
i=0;
for(i=0;str1[i]!=NULL;i++)
{
if(str1[i]!='+'&&str1[i]!='-'&&str1[i]!='*'&& str1[i]!='^'&&str1[i]!='/')
{
nw=top;
while(nw!=NULL)
{
if(str1[i]==nw->data)
break;
nw=nw->link;
}
if(nw==NULL)
{
nw=(val *)malloc(sizeof(val));
nw->data=str1[i];
printf("ENTER THE VALUE OF %c:",str1[i]);
scanf("%f",&(nw->value));
nw->link=top;
top=nw;
}
nw1=(eval *)malloc(sizeof(eval));
nw1->data=nw->value;
nw1->link=top1;
top1=nw1;
}
else
{
op=str1[i];
opr1=top1->data;
nw1=top1;
top1=top1->link;
free(nw1);
switch(op)
{
case '*':opr1=top1->data*opr1;
break;
case '/':opr1=top1->data/opr1;
break;
case '+':opr1=top1->data+opr1;
break;
case '-':opr1=top1->data-opr1;
break;
case '^':opr1=pow(top1->data,opr1);
break;
}
top1->data=opr1;
}
}
opr1=top1->data;
free(top1);
return(opr1);
}
float preeval(char str[])
{
val *nw,*t,*top=NULL;
eval *nw1,*top1=NULL;
int i,n;
float opr1,opr2;
char op;
i=0;
for(i=0;str[i]!=NULL;i++)
{
if(str[i]!='+'&&str[i]!='-'&&str[i]!='*'&& str[i]!='^'&&str[i]!='/')
{
nw=top;
while(nw!=NULL)
{
if(str[i]==nw->data)
break;
nw=nw->link;
}
if(nw==NULL)
{
nw=(val *)malloc(sizeof(val));
nw->data=str[i];
printf("ENTER THE VALUE OF %c:",str[i]);
scanf("%f",&(nw->value));
nw->link=top;
top=nw;
}
opr1=nw->value;
while(1)
{
if(top1==NULL||top1->data=='+'||top1->data=='-'||top1->data=='*'||top1->data=='/'||top1->data=='^')
break;
opr2=top1->data;
nw1=top1;
top1=top1->link;
free(nw1);
op=(char)top1->data;
nw1=top1;
top1=top1->link;
free(nw1);
switch(op)
{
case '*':opr1=opr2*opr1;
break;
case '/':opr1=opr2/opr1;
break;
case '+':opr1=opr2+opr1;
break;
case '-':opr1=opr2-opr1;
break;
case '^':opr1=pow(opr2,opr1);
break;
}
}
nw1=(eval*)malloc(sizeof(eval));
nw1->data=opr1;
nw1->link=top1;
top1=nw1;
}
else
{
nw1=(eval*)malloc(sizeof(eval));
nw1->data=(float)str[i];
nw1->link=top1;
top1=nw1;
}
}
opr1=top1->data;
free(top1);
return(opr1);
}
