Write an algorithm to convert Infix expression to Postfix expression and evaluate the converted expression.


Q.) Write an algorithm to convert Infix expression to Postfix expression and evaluate the converted expression.

Subject: Data Structures

Infix expressions are the expressions that we normally use, e.g. (A+B). On the other hand, postfix expressions are harder to read because they don't have parenthesis to dictate the order of operations, e.g. AB+.

The algorithm to convert an infix expression to a postfix expression is as follows:

  1. Initialize an empty stack and start scanning the infix expression from left to right.
  2. If the scanned character is an operand, add it to the postfix expression.
  3. If the scanned character is an operator and if the stack is empty, push the character to stack.
  4. If the scanned character is an operator and the stack is not empty, and the top element of the stack has the same or higher precedence than the scanned operator, then pop the stack and add to the postfix expression. Repeat this step as long as the stack is not empty and top element has equal or higher precedence. After that, push the scanned operator to the stack. (If the scanned operator has higher precedence than the top operator in the stack, then push the scanned operator to the stack.)
  5. If the scanned character is an '(', push it to the stack.
  6. If the scanned character is a ')', pop the stack and add to the postfix expression until a '(' is encountered. Discard both the parenthesis.
  7. Repeat steps 2-6 until infix expression is scanned.
  8. Pop all the remaining elements of the stack and add them to the postfix expression.

Example: Let's convert the infix expression A+B*(C^D-E) to postfix:

Infix Expression Stack Postfix Expression
A+B*(C^D-E)
B*(C^D-E) A A
*(C^D-E) A+B A
(C^D-E) A+B* A
C^D-E) A+B*( A
^D-E) A+B*(C A
D-E) A+B*(C^ A
-E) A+B*(C^D A
E) A+B*(C^D- A
) A+B*(C^D-E A
A+B* A
A+ A
A A
A

So, the postfix expression is ABCD^E-*+.

To evaluate the postfix expression, use the following algorithm:

  1. Initialize an empty stack.
  2. Start scanning the postfix expression from left to right.
  3. If the scanned character is an operand, push it to the stack.
  4. If the scanned character is an operator, pop two elements from the stack, apply the operator, and push the result back to the stack.
  5. Repeat steps 2-4 until the postfix expression is scanned.
  6. The final result is stored at the top of the stack.

Example: Let's evaluate the postfix expression ABCD^E-*+:

Postfix Expression Stack Result
ABCD^E-*+
BCD^E-*+ A
CD^E-*+ AB
D^E-*+ ABC
^E-*+ ABCD
E-*+ ABCD^
-*+ ABCD^E
*+ ABCD^E-
+ ABCD^E-*
ABCD^E-*+

So, the result of the postfix expression ABCD^E-*+ is the value at the top of the stack.