Design, Develop and Implement a Program in C for converting an Infix Expression to Postfix Expression

ABOUT THE EXPERIMENT: Infix: Operators are written in-between their operands.

Ex: X + Y

Prefix: Operators are written before their operands.

Ex: +X Y

postfix: Operators are written after their operands. Ex: XY+

Algorithm to convert Infix To Postfix

Let, X is an arithmetic expression  in infix form. This algorithm finds the equivalent postfix expression Y.

  1. Scan X from left to right and repeat Step 3 to 6 for each element of X until the Stack is empty.
  2. If an operand is encountered, add it to Y.
  3. If a left parenthesis is encountered, push it onto Stack.
  4. If an operator is encountered ,then:
    1. Repeatedly pop from Stack and add to Y each operator (on the top of Stack) which has the same precedence as or higher precedence than operator.
    2. Add operator to Stack. [End of If]
  5. If a right parenthesis is encountered ,then:
    1. Repeatedly pop from Stack and add to Y each operator (on the top of Stack) until a left parenthesis is encountered.
    2. Remove the left Parenthesis. [End of If] [End of If]
  6. END
				
					#include<stdio.h> 
#include<string.h> 
#include<conio.h> 
int F(char symbol) 
{ 
switch(symbol) 
{ 
case '+' case '-': return 2; 
case ‘*’: case ‘/’: return 4; 
case '^': case '$': return 5; 
case '(': return 0; case '#': return -1; 
default: return 8; 
} 
} 
int G(char symbol) 
{ 
switch(symbol) 
{ 
case '+' case '-': return 1; 
case ‘*’: case ‘/’: return 3; 
case '^': case '$': return 6; 
case '(': return 9; case ')': return 0; 
default: return 7; 
} 
} 
void infix_postfix(char infix[], char postfix[]) 
{ 
int top, j, i; 
char s[30], symbol; 
top = -1; 
s[++top] = '#'; 
j = 0; 
for(i=0; i < strlen(infix); i++) 
{ 
symbol = infix[i]; 
while(F(s[top]) > G(symbol)) 
{ 
postfix[j] = s[top--]; j++; 
} 
if(F(s[top]) != G(symbol)) s[++top] = symbol; 
else 
top--; 
} 
while(s[top] != '#') 
{ 
postfix[j++] = s[top--]; 
} 
postfix[j] = '\0'; 
} 
void main() 
{ 
char infix[20], postfix[20]; 
clrscr(); 
printf("\nEnter a valid infix expression\n"); 
flushall(); 
gets(infix); 
infix_postfix(infix,postfix); 
printf("\nThe infix expression is:\n"); 
printf ("%s",infix); 
printf("\nThe postfix expression is:\n"); 
printf ("%s",postfix); 
getch(); 
}
				
			
output: 

Enter a valid infix expression (a+(b-c)*d) 

The infix expression is: (a+(b-c)*d) 

The postfix expression is: abc-d*+

Leave a Reply