#include"conio.h"
#include"alloc.h"
#include"string.h"
#define MAX 50
struct stack
{
int top;
char data[MAX];
};
typedef struct stack stack;
void push(stack *,char);
char pop(stack *);
char *reverse(char *);
int prec_stack(char);
int prec(char);
void infix_prefix_par(char *,char *);
void main()
{
char i[20],p[20];
clrscr();
printf("Enter a infix string>");
gets(i);
infix_prefix_par(strcat(reverse(i),"("),p);
strcpy(p,reverse(p));
p[strlen(p)]='\0';
printf("\nPrefix is : %s",p);
getch();
exit(0);
}
void infix_prefix_par(char *i,char *p)
{
stack st;
char next,t,*in=i;
st.top=-1;
push(&st,')');
next=*in;
while(next!='\0')
{
while(prec(next)
t=pop(&st);
*p=t;
p++;
}
if(prec(next)!=prec_stack(st.data[st.top]))
push(&st,next);
else
pop(&st);
in++;
next=*in;
}
while(st.top>=0)
{ t=pop(&st);
*p=t;
p++;
}
p='\0';
}
void push(stack *st,char data)
{
if(st->top==MAX-1)
{
printf("\nList is Already FULL");
return;
}
st->data[++st->top]=data;
}
char pop(stack *st)
{
char res;
if(st->top==-1)
{
printf("\nList is Empty");
return NULL;
}
res=st->data[st->top];
st->top--;
return res;
}
int prec(char c)
{
if(c=='#' || c=='(')
return 0;
else if(c=='*' || c=='/')
return (4);
else if(c=='+' || c=='-')
return (2);
else if(c=='^')
return (5);
else if(c==')')
return(9);
else
return(8);
}
int prec_stack(char c)
{
if(c=='*' || c=='/')
return (3);
else if(c=='+' || c=='-')
return (1);
else if(c=='^')
return (6);
else if(c==')')
return(0);
else
return(7);
}
char *reverse(char *i)
{
char *t;
int l,j,c=0;
l=strlen(i);
for(j=l-1;j>=0;j--)
t[c++]=i[j];
t[c]='\0';
return t;
}
No comments:
Post a Comment