A C program to convert an Infix to a Postfix expression.
Infix Expression: Any expression in the standard form like "2*3-4/5" is an Infix (Inorder) expression.
Postfix Expression: In the postfix notation the operators are written after the operands. The Postfix (Postorder) form of the above expression is "23*45/-".
Infix to Postfix Conversion:
Using infix notation one cannot tell the order in which operators should be applied by only looking at expression. Whenever an infix expression consists of more than one operators, the precedence rules(BODMAS) should be applied to decide that which operator (and operands associated with that operator) are evaluated first. As compared to postfix notation, which is much more easy to work with or evaluate. In a postfix expression operands appear before the operators, there is no need for operator precedence and other rules. As soon as an operator appears in the postfix expression during scanning of postfix expression the topmost operands are popped off and are calculated applying the encountered operator.
Suppose Q is an arithmetic expression written in infix notation, this algorithm finds the equivalent postfix expression.
Step1: Push "(" onto STACK, and add ")" to the end of Q.
Step2: Scan Q from left to right and repeat steps 3 to 6 for each element of Q until the stack is empty.
Step 3: If an operand is encountered add it to P.
Step 4: If a left parenthesis is encountered push it onto the stack
Step 5: If an operator is encountered, then
(a) Repeatedly pop from STACK and add to P each operator (on top of the STACK) which has same precedence as or
higher precedence than the operator encountered
(b) Add the encountered operator to the stack.
[End of IF structure]
Step6: If a right parenthesis is encountered, then
(a) repeatedly pop from the stack and add to P each operator (on top of the STACK) until a left parenthesis is encountered.
(b) Remove the left parenthesis. [do not add left parenthesis to P]
[End of IF structure]
[End of step 2 loop]
#define add 1
#define sub 1
#define mul 2
#define div 2
#define exp 3
int top =0;
printf("Enter the Infix expression: ");
printf("nThe Postfix expression is: ");
int get_type(char symbol)
int get_precedence(char symbol)
void i2p(char infix)
void push(char stack,char data)
char pop(char stack)
Enter the Infix expression: 7-(2*3+5)*(8-4/2)
The Postfix expression is: 723*5+842/-*-
Enter the infix expression: A*(B+D)/E-F*(G+H/K)
The Postfix expression is: ABD+*E/FGHK/+*-
• It is advantageous to use postfix notation. As operands appear before the operators, there is no need for operator precedence and other rules.
• Here the stack is implemented using array. As the size of array is declared before the start of the operation, it is not too efficient with respect to memory utilization.
• The same program can be done using linked list which is more efficient than array in terms of memory utilization.