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).