Postfix to Infix Conversion Algorithm, example and program

Postfix to Infix conversion is a method to change a postfix expression (where operators come after the operands) into an infix expression (where operators come between operands). In postfix expressions, we don’t need brackets to show the order of operations, but in infix expressions, brackets are often used to show which operations to do first.

This conversion is useful because computers often evaluate expressions in postfix form, but humans find infix expressions easier to read and understand. Using a stack, we can systematically take each operand and operator from the postfix expression and build the equivalent infix expression step by step.

Algorithm For Postfix to Infix Conversion

Iterate the given expression from left to right, one character at a time

1. Start: Take the given postfix expression and read it from left to right, one character at a time.
2. If the character is an operand:
   • Push it onto the stack.
3. If the character is an operator:
   • Check if there are at least 2 operands on the stack.
     • If not, display an error: "Insufficient values in expression" and go to Step 6.
   • If yes, pop the top 2 operands from the stack.
   • Create a new string by placing the operator between the two operands in the correct order.
   • Push this new string back onto the stack.
4. Repeat Steps 2 and 3 for all characters in the expression.
5. Final Step: After processing all characters, there should be exactly one string left in the stack.
   • This string is the equivalent infix expression.
6. Exit.

Some important terminology

Postfix Expression
In Postfix Expression operator appear after operand, this expression is known as Postfix operation.
Infix
If Infix Expression operator is in between of operands, this expression is known as Infix operation.

Steps to Convert Postfix to Infix

• Start Iterating the given Postfix Expression from Left to right
• If Character is operand then push it into the stack.
• If Character is operator then pop top 2 Characters which is operands from the stack.
• After poping create a string in which comming operator will be in between the operands.
• push this newly created string into stack.
• Above process will continue till expression have characters left
• At the end only one value will remain if there is integers in expressions. If there is character then one string will be in output as infix expression.

How the Stack Works in This Context

The stack is used to temporarily hold operands. When an operator is encountered, the two most recent operands are popped from the stack, combined with the operator in infix format, and the resulting string is pushed back onto the stack. This process continues until the entire expression is converted to infix notation. The use of a stack is crucial for correctly handling the order of operations and parentheses in the resulting infix expression.

Example to Convert Postfix to Infix

Postfix Expression : abc-+de-+

Solution for Postfix expression

postfix expression: 752+*415-/-

Java Program to Convert Infix to Postfix

import java.util.*;

public class Main {

    public static String convert(String exp) {
        int len = exp.length();
        Stack<String> stack = new Stack<>();
        for (int i = 0; i < len; i++) {
            char c = exp.charAt(i);

            if (c == '*' || c == '/' || c == '^' || c == '+' || c == '-') {
                String s1 = stack.pop();
                String s2 = stack.pop();
                String temp = "(" + s2 + c + s1 + ")";
                stack.push(temp);
            } else {
                stack.push(c + "");
            }
        }

        String result = stack.pop();
        return result;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.println("Please enter Postfix Expression: ");
        String exp = sc.nextLine();
        System.out.println("Infix Expression: " + Main.convert(exp));
    }
}

Output

Please enter Postfix Expression: 
abc-+de-+
Infix Expression: ((a+(b-c))+(d-e))

Explanations

The Java program provided is designed to convert expressions from postfix notation to infix notation using a stack. It leverages the Stack class from the Java util package to perform this operation. Here’s a breakdown of how the program works:

Import Statement

import java.util.*;

This line imports the Java utility package, which contains the Stack class used in this program.

The Main Class

The class named Main encapsulates the entire program.

The convert Method

for (int i = 0; i < len; i++) {
    char c = exp.charAt(i);

This is a static method that takes a single String parameter (exp) representing the postfix expression and returns a String that represents the converted infix expression.

Variables:

len: Stores the length of the postfix expression.

stack: A Stack<String> object used to hold parts of the expression during conversion.

The Conversion Loop:

for (int i = 0; i < len; i++) {
    char c = exp.charAt(i);

This loop iterates over each character in the postfix expression.Inside the loop, the program checks if the current character (c) is an operator (*, /, ^, +, -). If it is, the program performs the following steps:

Result Compilation:

String result = stack.pop();
return result;

return result; After the loop completes, the only element left on the stack is the fully converted infix expression. This is popped from the stack and returned.

The main Method

public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    System.out.println("Please enter Postfix Expression: ");
    String exp = sc.nextLine();
    System.out.println("Infix Expression: " + Main.convert(exp));
}

This is the entry point of the program. It prompts the user to input a postfix expression, reads the input using a Scanner object, and then calls the convert method to transform the input into infix notation. Finally, it prints the resulting infix expression.