Code for implementing Infix to Prefix Conversion.
This code is designed for converting an infix equation(expression) into prefix equation(expression) means Infix to Prefix. In this code you have to pass an equation or expression in infix form as string (character array) format, the code will convert the infix expression into prefix expression. In this code precedence of the operator is also considered. This is the easiest way to implement infix to prefix conversion concept in C. For converting Infix to Prefix you need to follow several steps.
Step 1: Reverse the Infix Expression.
Step 2: Exchange the parenthesis with the alternat one to get a proper expression or equation.
Step 3: Perform Postfix conversion operation with the modified expression or equation.
Step 4: After reversing the last result you are going to get the Prefix Expression.
For Such more codes click here and for video tutorial click here.
//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;
}
}
