Data Structure Prefix to Postfix Conversion

Prefix to Postfix Conversion

Prefix: As the name suggests if the operator placed before the operands called the prefix expression.  The form of prefix expression is (operator, operand1, operand2).

Example:  *+EF-GH (Infix: (E+F) * (F-H))

Postfix: In postfix expression, the operator placed after the operands and the form of postfix expression is (operand1, operand2, operator).

Example: EF+GH-* (Infix: (E+F * (G-H))

Algorithm:

• Firstly, we read input or prefix expression from right to left or we can say in reverse order.
• If we encounter an operand, then we push it into the stack.
• If we encounter an operator, then we pop two operands from the stack.
• Then we are required to make a string which concatenate the two operands and the operator after them.
• String = operand1 + operand2 + operator
• Then we push the output or resultant string back to the stack.
• We need to repeat above steps until the end of prefix expression.

Examples: 

Prefix:  * + E F – G H

Postfix: E F + G H - *

Explanation: Prefix to Infix: (E + F) * (G – H)

             Infix to Postfix:  E F + G H - *

Prefix:  * - E / F G - / E K L

Postfix: E F G / - E K / L - *

Explanation: Prefix to Infix: (E - ( F / G ) ) * ( ( E / K ) – L )

    Infix to Postfix :  E F G / - E K / L - * 

C- Program to covert prefix expression to postfix expression:

 #include<stdio.h>
 #include<string.h>
 #include<math.h>
 #include<stdlib.h>
 #define BLANK ' '
 #define TAB '\t'
 #define MAX 50
 char *pop();
 char prefix[MAX];
 char stack[MAX][MAX];
 void push(char *str);
 int isempty();
 int white_space(char element);
 void prefix_to_postfix();
 int top;
 int main()
 {
         top  =  -1;
         printf(" Enter Prefix Expression :  ");
         gets(prefix);
         prefix_to_postfix();
 }
 /* End of main() */
 void prefix_to_postfix()
 {
         int i;
         char operand1[MAX], operand2[MAX];
         char element;
         char temp[2];
         char strin[MAX];
         for(i = strlen(prefix)-1; i >= 0; i--)
         {
                 element = prefix[i];
                 temp[0] = element;
                 temp[1] = '\0';
                 if(!white_space(element))
                 {
                         switch(element)
                         {
                         case '+':
                         case '-':
                         case '*':
                         case '/':
                         case '%':
                         case '^':
                                 strcpy(operand1,pop());
                                 strcpy(operand2,pop());
                                 strcpy(strin,operand1);
                                 strcat(strin,operand2);
                                 strcat(strin,temp);            
                                 push(strin);
                                 break;
                         default:
 /* if an operand comes */
                              push(temp);
                         }
                 }
         }
         printf("\nPostfix Expression :: ");
         puts(stack[0]);
 }
 /* End of prefix_to_postfix()  */
 void push(char *str)
 {
         if(top  >  MAX)
         {
                 printf("\nStack overflow\n");
                 exit(1);
         }
         else
         {
                 top = top+1;
                 strcpy( stack[top], str);
         }
 }
 /* End of push() */
 char *pop()
 {
         if(top  ==  -1 )
         {
                 printf("\n Stack underflow \n");
                 exit(2);
         }
         else
                 return (stack[top--]);
 }
 /*  End of pop()  */
 int isempty()
 {
         if(top==-1)
                 return 1;
         else
                 return 0;
 }
 int white_space(char element)
 {
         if(element == BLANK || element == TAB || element == '\0')
                 return 1;
         else
                 return 0;
 } 

Output: -

Time Complexity:  -  

The time complexity to convert prefix expression to postfix expression is O(n) and space complexity is also O(n).