Conversion of Infix, Postfix, Prefix Expressions Using Stack written by Nischal Lal Shrestha.
Image of Nischal who is author of the post.

By Nischal Lal Shrestha

On Fri 13 April 2018

Conversion of Infix, Postfix, Prefix Expressions Using Stack

Conversion of Infix Expression to Postfix

Let,
Operator_Stack be empty stack to keep operators. Postfix_Expression be output.
  • Scan the expression from left to right.
  • If the scanned character is:
    • an operand, append it to the end of Postfix_Expression.
    • a left parentheses, push it on the Operator_Stack.
    • a right parentheses, pop the Operator_Stack until the corresponding` left parentheses is removed. Push every popped character to the end of the Postfix_Expression.
    • an operators like, x / + ^, push it on the Operator_Stack. Before that you need to move any operators on Operator_Stack having precedence greater than or equal to scanned operator to Postfix_Expression.

Continue above steps until you get the final Postfix_Expression.

Conversion of Infix Expression to Prefix Expression

No matter what the complexity of the Infix Expression be, there is an Algorithmic way to convert infix expression to postfix expression. There is other Algorithmic way too but this one is easiest to remember.

The Algorithm to Convert Infix Expression to Postfix

  • Reverse the given infix expression. While reversing the string, you must change left parentheses to right and vice versa. This step will give rise to another string String_1.
  • Find the postfix expression of String_1. Let it be String_2(You can check above to convert to postfix.)
  • Reverse String_2 to get the prefix expression.
For Example::

String: (A - B / C) x (A / D - E)

Step 1: Reverse the given string and interchange the parentheses.
String_1 = (E – D / A) * (C / B – A)
Step 2: Find the postfix expression of String_1
String_2 = E D A / – C B / A – x
Step 3: Reverse String_2 to find the prefix expression.
x – A / B C – /A D E

Second Algorithm to Convert Infix to Postfix

Phase 1

  • Scan each character in the infix expression.
  • If the scanned character is operator push it into operator stack.
  • If the scanned character is operand push it into operator stack.
  • Ignore all the left parentheses until a right parantheses is encountered.

Phase 2

  • Pop operand from operand stack(Call it A) and a operator from operator stack.
  • Concatenate the operator(A) and operand.
  • Pop another operand from operand stack(Call it B) and concatenate it with the result obtained above.
  • Push the above result into operand stack.

Continue above step until a prefix expression is generated.

Comments