Wednesday, March 24, 2010

ds - infix (paranthesized) to prefix conversion

#include"stdio.h"
#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