Infix to Postfix Conversion: Algorithm and Example

In infix to postfix conversion we will use stack data structure. We have operator’s stack, output’s stack and one input string. Operator’s stack works as FILO(First In Last Out). Output’s stack works as FIFO (First In First Out).

Converting an infix expression to postfix is like changing the way we write math problems so computers can solve them easily. In infix, we write operations between numbers, like “3 + 4”. In postfix, the operation comes after the numbers, like “3 4 +”.

Algorithm to Convert Infix to Postfix

1. Initialize an empty stack for holding operators and an empty list (or string) for the output postfix expression.
2. Iterate through each character in the infix expression:
   • If the character is an operand, add it directly to the postfix expression.
   • If the character is an opening parenthesis ‘(‘, push it onto the stack.
   • If the character is a closing parenthesis ‘)’, repeatedly pop from the stack and add to the postfix expression until an opening parenthesis ‘(‘ is encountered on the stack. Pop and discard the opening parenthesis from the stack.
   • If the character is an operator (e.g., +, -, *, /):
     • While the stack is not empty, and the top of the stack has an operator with greater or equal precedence than the current operator, pop the stack and add the operator to the postfix expression.
     • Push the current operator onto the stack.
3. After reading the infix expression, pop any remaining operators from the stack and add them to the postfix expression.
4. Return the postfix expression.

Operator Precedence and Associativity

Operator precedence determines how operators are prioritized in expressions. For example, multiplication (*) and division (/) have higher precedence than addition (+) and subtraction (-). Associativity (usually left-to-right for most operators) determines the order of operations when two operators share the same precedence.

Example of Infix to Postfix Conversion

Example 1:

Infix Expression : A+(B*C+D)/E

Input Token	Stack	Postfix Expression	Action
A		A	Add A into expression string
+	+	A	Push ‘+’ into stack
(	+(	A	Push ( into stack
B	+(	AB	Add B into expression string
*	+(*	AB	Push ‘*’ into stack
C	+(*	ABC	Add C into expression string
+	+(+	ABC*	‘+’ operator has less precedence than ‘*’, so pop * and add to expression string
D	+(+	ABC*D	Add D into expression string
)	+	ABC*D+	) has come so pop + and add it to expression string
/	+/	ABC*D+	/ has higher precedence than + so push / into stack
E	+/	ABC*D+E/+	Add E into expression string and pop all operators one by one from stack and add it to expression string

Example 2:

Infix Expression: A+(BC+D)/E+FG

Initial Setup

• Infix Expression: “A+(BC+D)/E+FG”
• Stack: Empty
• Postfix Expression: Empty

Conversion Steps

1. Read ‘A’ (operand): Add ‘A’ to the postfix expression.
   • Postfix: A
   • Stack: Empty
2. Read ‘+’ (operator): Push ‘+’ onto the stack.
   • Postfix: A
   • Stack: +
3. Read ‘(‘ (opening parenthesis): Push ‘(‘ onto the stack.
   • Postfix: A
   • Stack: +, (
4. Read ‘B’ (operand): Add ‘B’ to the postfix expression.
   • Postfix: AB
   • Stack: +, (
5. Read ‘*’ (operator): Push ‘*’ onto the stack. It has higher precedence.
   • Postfix: AB
   • Stack: +, (, *
6. Read ‘C’ (operand): Add ‘C’ to the postfix expression.
   • Postfix: ABC
   • Stack: +, (, *
7. Read ‘+’ (operator): Since ‘+’ has lower precedence than ‘‘, pop ‘‘ and add it to postfix. Then, push ‘+’ onto the stack.
   • Postfix: ABC*
   • Stack: +, (, +
8. Read ‘D’ (operand): Add ‘D’ to the postfix expression.
   • Postfix: ABC*D
   • Stack: +, (, +
9. Read ‘)’ (closing parenthesis): Pop and add operators to the postfix until ‘(‘ is found. Pop ‘(‘ without adding it to postfix.
   • Postfix: ABC*D+
   • Stack: +
10. Read ‘/’ (operator): Push ‘/’ onto the stack. It has the same precedence as ‘+’, but ‘+’ is not directly on top due to ‘(‘ precedence rules.
    • Postfix: ABC*D+
    • Stack: +, /
11. Read ‘E’ (operand): Add ‘E’ to the postfix expression.
    • Postfix: ABC*D+E
    • Stack: +, /
12. Read ‘+’ (operator): Pop ‘/’ and ‘+’ from the stack and add to postfix, then push the new ‘+’.
    • Postfix: ABC*D+E/+
    • Stack: +
13. Read ‘F’ (operand): Add ‘F’ to the postfix expression.
    • Postfix: ABC*D+E/+F
    • Stack: +
14. Read ‘*’ (operator): Push ‘*’ onto the stack. It has higher precedence than ‘+’.
    • Postfix: ABC*D+E/+F
    • Stack: +, *
15. Read ‘G’ (operand): Add ‘G’ to the postfix expression.
    • Postfix: ABC*D+E/+FG
    • Stack: +, *
16. End of Expression: Pop remaining operators from the stack and add to postfix.
    • Postfix: ABCD+E/+FG+
    • Stack: Empty

The final postfix expression for “A+(BC+D)/E+FG” is “ABCD+E/+FG+”. This postfix expression maintains the order of operations from the infix expression without needing parentheses, making it easier for machines to evaluate.