Data Structure Infix to Postfix Conversion
Infix to Postfix Conversion
The infix expression is easy to read and write by humans. In present time, we use the infix expression in our daily life but the computers are not able to understand this format because they need to keep some rules and they can’t differentiate between operators and parenthesis easily. The Prefix and Postfix expressions are quite understandable for the computers. For the infix to postfix conversion, we use stack data structure because
it works on Last in First out principle.
Algorithm: -
Step 1: Firstly, we push “(“ into the stack and also we add “)” to the end of the given input expression.
Step 2: Then we scan the input expression from left to right and we repeat step 3 to 6 for each element of the input expression until the stack is empty.
Step 3: If we encounter an operand then we just add it to output expression.
Step 4: If we encounter the left or opening parenthesis the we push it into the stack.
Step 5: If we encounter an operator, then:
a. We repeatedly check the precedence of incoming operator with the top of stack if the precedence of it is higher than the top of the stack then we simply add it into the stack else we pop the top of stack and add it into the output expression then again check the incoming operator precedence with the new of the top of stack.
b. If the precedence of both operators (incoming operator and the top of the stack) are same then use associativity rule.
Step 6: If we encounter the right or closing parenthesis, then:
a. We repeatedly pop the operator from the stack and add it to the output expression until the left parenthesis is encountered.
b. Then remove the left parenthesis from the stack.
Example: -
The Input / Infix Expression: A + ( ( B + C ) + ( D + E ) * F ) / G )
| Infix Expression | Stack | Postfix Expression |
| A | ( | A |
| + | ( + | A |
| ( | ( + ( | A |
| ( | ( + ( ( | A |
| B | ( + ( ( | A B |
| + | ( + ( ( + | A B |
| C | ( + ( ( + | A B C |
| ) | ( + ( | A B C + |
| + | ( + ( + | A B C+ |
| ( | ( + ( + ( | A B C + |
| D | ( + ( + ( | A B C + D |
| + | ( + ( + ( + | A B C + D |
| E | ( + ( + ( + | A B C + D E |
| ) | ( + ( + | A B C + D E + |
| * | ( + ( + * | A B C + D E + |
| F | ( + ( + * | A B C + D E + F |
| ) | ( + | A B C + D E + F * + |
| / | ( + / | A B C + D E + F * + |
| G | ( + / | A B C + D E + F * + G |
| ) | EMPTY | A B C + D E + F * + G / + |
The Output / Postfix Expression: A B C + D E + F * + G / +
C- Program to covert infix expression to postfix expression:
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<stdlib.h>
#define BLANK ' '
#define TAB '\t'
#define MAX 50
void push(long int element);
long int pop();
void infix_to_postfix();
long int postfixEval();
int precedence(char element);
int isEmpty();
int whiteSpace( char );
char infix[ MAX ], postfix[ MAX ];
long int stack[MAX];
int top;
int main()
{
long int value;
top = -1;
printf("Enter infix : ");
gets( infix );
infix_to_postfix();
printf("Postfix : %s\n",postfix);
value = postfixEval();
printf("Value of expression : %ld\n",value);
return 0;
}/*End of main()*/
void infix_to_postfix()
{
unsigned int i, p = 0;
char next;
char element;
for(i = 0; i<strlen(infix); i++)
{
element = infix[i];
if(!whiteSpace(element))
{
switch(element)
{
case '(':
push(element);
break;
case ')':
while((next = pop()) != '(' )
postfix[p++] = next;
break;
case '+':
case '-':
case '*':
case '/':
case '%':
case '^':
while( !isEmpty( ) && precedence(stack[top] ) >= precedence( element ) )
postfix[p++] = pop();
push( element );
break;
default: /* if an operand comes */
postfix[p++] = element;
}
}
}
while( !isEmpty( ) )
postfix[p++] = pop();
postfix[p] = '\0'; /* End postfix with'\0' to make it a string */
}/*End of infix_to_postfix()*/
/* This function returns the precedence of the operator */
int precedence(char element)
{
switch(element)
{
case '(':
return 0;
case '+':
case '-':
return 1;
case '*':
case '/':
case '%':
return 2;
case '^':
return 3;
default :
return 0;
}
}
/* End of precedence() */
void push(long int element)
{
if( top > MAX )
{
printf("Stack overflow\n");
exit(1);
}
stack[ ++top ] = element;
}
/* End of push() */
long int pop()
{
if( isEmpty() )
{
printf(" Stack underflow\n ");
exit(1);
}
return (stack[ top-- ]);
}
/* End of pop() */
int isEmpty()
{
if(top == -1)
return 1;
else
return 0;
}
/* End of isEmpty() */
int whiteSpace(char element)
{
if( element == BLANK || element == TAB )
return 1;
else
return 0;
}
/* End of whiteSpace() */
long int postfixEval()
{
long int a, b, temp, result;
unsigned int i;
for( i = 0; i<strlen(postfix); i++ )
{
if( postfix[i] <= '9' && postfix[i] >= '0' )
push( postfix[i]-'0' );
else
{
a = pop();
b = pop();
switch( postfix[i] )
{
case '+':
temp = b+a;
break;
case '-':
temp = b-a;
break;
case '*':
temp = b*a;
break;
case '/':
temp = b/a;
break;
case '%':
temp = b%a;
break;
case '^':
temp = pow( b, a );
}
push( temp );
}
}
result = pop();
return result;
}
Output: -
Time Complexity: -
The time complexity of infix to postfix operation is O(n^2) and the space complexity is O(n).