Infix to Postfix Expression conversion.

Infix expression: The expression of the form A op B. e.g. A + B .When the operator is in between the operands.

Postfix expression: The expression of the form A B op. e.g. A B + .When an operator if followed for every pair of operands.

Why postfix representation is useful for calculation ?

As humans we thought calculating infix expression is much easier and understandable .But for computer it is not easy or efficient to calculate infix expression. For calculating infix exp. computer will scan and calculate a pair of expressions again and again . So to avoid unnecessary scanning of the expression we convert infix — postfix.

infix: a+b*c+d

postfix: abc*+d+

Now in a single scan computer can easily calculate postfix exp. in an efficient time. The postfix exp. can be evaluated easily using a Stack.

Algorithm:

1. Scan the infix expression from left to right.
2. If we get an operand ,directly add it in the postfix exp.
3. If we get an ‘(‘ ,directly push it in the stack.
4. If we get an ‘)’ ,we pop elements from the stack until we get top element of the stack as ‘(‘ and append the popped elements to the postfix exp. And pop the ‘(‘ from stack.
5. If we get an operator and it is having higher precedence than the top of the stack ,we simply push it in the stack,
6. Else if stack is not empty and precedence is less than or equal to the top of the stack ,we will pop the element from stack append it to the postfix exp. until the above condition holds. And when the above condition is false we push that operator into the stack.
7. At the end we will pop all the characters present in the stack and added to the postfix exp. while popping if we get an ‘(‘ we will return “INVALID INFIX EXPRESSION “.

CODE:

Thanks !