C program to convert an infix expression to a prefix expression

Complete C program to convert an infix expression to a prefix expression

#include <stdio.h>
#include <conio.h>
#include <string.h>
#include <ctype.h>
#define MAX 100
char st[MAX];
int top=–1;
void reverse(char str[]);
void push(char st[], char);
char pop(char st[]);
void InfixtoPostfix(char source[], char target[]);
int getPriority(char);
char infix[100], postfix[100], temp[100];
int main()
{
clrscr();
printf("\\n Enter any infix expression : ");
gets(infix);
reverse(infix);
strcpy(postfix, "");
InfixtoPostfix(temp, postfix);
printf("\n The corresponding postfix expression is : ");
puts(postfix);
strcpy(temp,"");
reverse(postfix);
printf("\n The prefix expression is : \n");
puts(temp);
getch();
return 0;
}
void reverse(char str[])
{
int len, i=0, j=0;
len=strlen(str);
j=len–1;
while(j>= 0)
{
if (str[j] == '(')
 temp[i] = ')';
else  if ( str[j] == ')')
 temp[i] = '(';
 else
    temp[i] = str[j];
i++,  j––;
}
temp[i] = '\0';
}
void InfixtoPostfix(char source[], char target[])
{
int i=0, j=0;
char temp;
strcpy(target, "");
while(source[i]!= '\0')
{
 if(source[i]=='(')
 {
 push(st, source[i]);
 i++;
 }
 else if(source[i] == ')')
 {
 while((top!=–1) && (st[top]!='('))
 {
target[j] = pop(st);
j++;
 }
 if(top==–1)
 {
 printf("\n INCORRECT EXPRESSION");
exit(1);
 }
 temp = pop(st); //remove left parentheses
 i++;
 }
 else if(isdigit(source[i]) || isalpha(source[i]))
 {
target[j] = source[i];
j++;
 i++;
 }
 else if( source[i] == '+' || source[i] == '–' || source[i] == '*' || 
source[i] == '/' || source[i] == '%')
 {
 while( (top!=–1) && (st[top]!= '(') && (getPriority(st[top])
> getPriority(source[i])))
 {
target[j] = pop(st);
j++;
 }
 push(st, source[i]);
 i++;
 }
 else
 {
 printf("\n INCORRECT ELEMENT IN EXPRESSION");
 exit(1);
 }
}
while((top!=–1) && (st[top]!='('))
{
target[j] = pop(st);
j++;
}
target[j]='\0';
}
int getPriority( char op)
{
if(op=='/' || op == '*' || op=='%')
 return 1;
else if(op=='+' || op=='–')
return 0;
}
void push(char st[], char val)
{
if(top==MAX–1)
 printf("\n STACK OVERFLOW");
else
{
 top++;
 st[top] = val;
}
 }
char pop(char st[])
{
char val=' ';
if(top==–1)
 printf("\n STACK UNDERFLOW");
else
{
 val=st[top];
 top––;
}
return val;
}

Output

Enter any infix expression : A+B–CD

The corresponding postfix expression is : AB+CD


The prefix expression is : –+AB*C

Leave a Comment