facebook like button

28 November, 2013

conversion of an infix expression to a prefix expression using stack.

THE CODE:
#include<stdio.h>
#include<ctype.h>
#define max 50
struct x{
char data[max];
int top;
};
typedef struct x stack;
void infix_prefix(char [],char []);
void infix_postfix(char [],char []);
void push(stack *,char );
char pop(stack *);
int precedence(char );
int main()
{
char infix[max],prefix[max];
printf("\nenter an infix expression\n");
gets(infix);
infix_prefix(infix,prefix);
printf("\n prefix:\n %s ",prefix);
return 0;
}
void infix_prefix(char infix[],char prefix[])
{
int i,j;
char a[max],temp;
for(j=strlen(infix)-1,i=0;j>=0;j--,i++)
a[i]=infix[j];
a[i]='\0';
for(i=0;a[i]!='\0';i++)
{
if(a[i]=='(')
a[i]=')';
else if(a[i]==')')
a[i]='(';
}
infix_postfix(a,prefix);
for(i=0,j=strlen(prefix)-1;i<j;i++,j--)
{
temp=prefix[j];
prefix[j]=prefix[i];
prefix[i]=temp;
}
}


void infix_postfix(char infix[],char postfix[])
{
int i,j;
stack s;
char x,token;
s.top=-1;
j=0;
for(i=0;infix[i]!='\0';i++)
{
token=infix[i];
if(isalnum(token)){
postfix[j]=token;
j++;
}
else if(token=='(')
push(&s,'(');
else if(token==')')
{
while((x=pop(&s))!='('){
postfix[j]=x;
j++;
}
}
else
{
while( s.top!=-1 && precedence(token)<=precedence(s.data[s.top]))
{
x=pop(&s);
postfix[j++]=x;
}
push(&s,token);
}

}
while(s.top!=-1)
{
x=pop(&s);
postfix[j]=x;
j++;
}
postfix[j]='\0';
}
int precedence(char x)
{
if(x=='(')
return 0;
else if(x=='+'||x=='-')
return 1;
else if(x=='*'||x=='/'||x=='%')
return 2;
else
return 3;
}
void push(stack *s,char x)
{
s->top=s->top+1;
s->data[s->top]=x;
}
char pop(stack *s)
{
int x;
x=s->data[s->top];
s->top=s->top-1;
return x;
}