In this tutorial We have explored an algorithm to convert a given Postfix expression to Infix expression using Stack.
Algorithm For Postfix to Infix Conversion
Iterate the given expression from left to right, one character at a time
Step 1 : If a character is operand, push it to stack.
Step 2: If a character is an operator,
if there are fewer than 2 values on the stack
give error "insufficient values in expression" goto Step 4
else
pop 2 operands from stack
create a new string and by putting the operator between operands.
push this string into stack
Repeat Steps 1 and 2
Step 3: At last there will be only one value or one string in the stack which will be our infix expression
Step 4: 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.
Example to Convert Postfix to Infix
Postfix Expression : abc-+de-+
| Token | Stack | Action |
| a | a | push a in stack |
| b | a, b | push b in stack |
| c | a, b, c | push c in stack |
| – | a , b – c | pop b and c from stack and put – in between and push into stack |
| + | a + b – c | pop a and b-c from stack and put + in between and push into stack |
| d | a + b – c, d | push d in stack |
| e | a + b – c, d , e | push e in stack |
| – | a + b – c, d – e | pop d and e from stack and put – in between and push into stack |
| + | a + b – c + d – e | pop a + b – c and d – e from stack and put + in between and push into stack |
Solution for Postfix expression
postfix expression: 752+*415-/-
| Token | Stack | Action |
| 7 | 7 | push 7 in stack |
| 5 | 7, 5 | push 5 in stack |
| 2 | 7 , 5, 2 | push 2 in stack |
| + | 7, 7 | pop 2 and 5 from stack, sum it and then again push it |
| * | 49 | pop 7 and 7 from stack and multiply it and then push it again |
| 4 | 49, 4 | push 4 in stack |
| 1 | 49, 4, 1 | push 1 in stack |
| 5 | 49, 4, 1, 5 | push 5 in stack |
| – | 49, 4, -4 | pop 5 and 1 from stack |
| / | 49, -1 | pop 4 and 4 from stack |
| – | 50 | pop 1 and 49 from stack |
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.
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.