//Infix to Prefix conversion
#include<stdio.h>
#include<stdlib.h>
#define max 50
typedef struct stack
{
char ar[max];
int top;
} st;
void push(st *,char);
char pop(st *);
char peek(st);
int isfull(st);
int isempty(st);
void intopost(char [],char []);
int getpriority(char);
char getmatch(char);
void reverse(char []);
void changeparenthesis(char []);
int main()
{
char expr[max],res[max];
printf("\nEnter the expression : ");
scanf("%s",expr);
reverse(expr);
printf("\n\nStep 1 : Reverse the Expression : %s",expr);
changeparenthesis(expr);
printf("\n\nStep 2 : Exchange the parentesis with it's alterante one : %s",expr);
printf("\n\nStep 3 : Perform the postix conversion on the last modified expression");
intopost(expr,res);
reverse(res);
printf("\n\nStep 4 : Reverse the Postfix expression to get the Prefix Expression : %s",res);
}
void reverse(char str[])
{
int i,len;
char temp;
for(len=0; str[len]; len++);
len--;
for(i=0; i<len/2; i++)
{
temp=str[i];
str[i]=str[len-i];
str[len-i]=temp;
}
}
void changeparenthesis(char str[])
{
int i;
for(i=0; str[i]; i++)
{
switch(str[i])
{
case '(':
str[i]=')';
break;
case ')':
str[i]='(';
break;
case '{':
str[i]='}';
break;
case '}':
str[i]='{';
break;
case '[':
str[i]=']';
break;
case ']':
str[i]='[';
break;
}
}
}
void intopost(char expr[],char res[])
{
st s;
char ch;
int i,j;
s.top=-1;
for(i=0,j=0; expr[i]!='\0'; i++)
{
if(expr[i]==' ')
continue;
else if(expr[i]=='(' || expr[i]=='{' || expr[i]=='[')
push(&s,expr[i]);
else if((expr[i]>=48 && expr[i]<=57) || (expr[i]>=65 && expr[i]<=90) || (expr[i]>=97 && expr[i]<=122))
res[j++]=expr[i];
else if(expr[i]=='+' || expr[i]=='-' || expr[i]=='*' || expr[i]=='/')
{
while(!isempty(s) && getpriority(expr[i])<=getpriority(peek(s)) && peek(s)!='(')
{
res[j++]=pop(&s);
}
push(&s,expr[i]);
}
else if(expr[i]==')' || expr[i]=='}' || expr[i]==']')
{
while(!isempty(s) && (ch=pop(&s))!='(')
{
res[j++]=ch;
}
}
else
{
//printf("Expression not ok");
break;
}
}
if(!isempty(s))
{
while(!isempty(s) && (ch=peek(s))!='(')
res[j++]=pop(&s);
}
res[j]='\0';
}
void push(st *s,char ch)
{
s->ar[++s->top]=ch;
}
char pop(st *s)
{
return s->ar[s->top--];
}
char peek(st s)
{
return s.ar[s.top];
}
int isempty(st s)
{
if(s.top==-1)
return 1;
else
return 0;
}
int isfull(st s)
{
if(s.top==max-1)
return 1;
else
return 0;
}
int getpriority(char ch)
{
switch(ch)
{
case '+':
return 2;
case '-':
return 1;
case '*':
return 3;
case '/':
return 4;
}
}
