CC-10 : Convert Postfix expression to Infix expression.

Description:

Given a Postfix expression, convert it to an Infix expression.

Test cases and expected outputs:

Input Parameters	Expected outputs
Postfix: abc/-ad/e-*	InFix: ((a-(b/c))*((a/d)-e))
Postfix: ab+cd+*	InFix: ((a+b)*(c+d))

Pseudocode:

Initialize a stack for processing purposes.

For each character in input String:

If current character is not an operator, add it to the stack.

Else:

Remove first character from top of stack and name it operand1.

Remove first character from top of stack and name it operand2.

Create a String by appending following characters : “(“ , operand1, current character, operand2.

Add above String to Stack.

The top most entry in the stack is the post Fix expression, return it from the method.

Code:

public class StackPostfixToInfix {
	
private Deque<String> stack=null;	

public String postfixToInfix(String str) throws Exception{
	stack=new LinkedList<String>();	
	char[] chr=str.toCharArray();
	String operator="+-*/^"; 	
	char c; String oper1, oper2;
	for (int idx=0;idx < chr.length; idx++) {
		c=chr[idx];
		if (operator.indexOf(c)==-1) {
			stack.offerFirst(""+c);
		}else {
			oper1=stack.peekFirst();
			stack.pollFirst();
			oper2=stack.peekFirst();
			stack.pollFirst();
			stack.offerFirst("("+ oper2 + c + oper1 + ")"); 
		}		
	}
	return stack.peekFirst();
}
}

Click here to download and run code and test cases !

Below fully running code can be copied and run on Eclipse or other Java IDEs. Refer the classname in code below. If the class name below is "A", save the code below to a file named A.java before running it. Be sure to try your own test cases to enhance your understanding ! You can also tweak the code to optimize or add enhancements and custom features.

import java.util.Deque;
import java.util.LinkedList;

public class StackPostfixToInfix {
	
private Deque<String> stack=null;	

public String postfixToInfix(String str) throws Exception{
	stack=new LinkedList<String>();	
	char[] chr=str.toCharArray();
	String operator="+-*/^"; 	
	char c; String oper1, oper2;
	for (int idx=0;idx < chr.length; idx++) {
		c=chr[idx];
		if (operator.indexOf(c)==-1) {
			stack.offerFirst(""+c);
		}else {
			oper1=stack.peekFirst();
			stack.pollFirst();
			oper2=stack.peekFirst();
			stack.pollFirst();
			stack.offerFirst("("+ oper2 + c + oper1 + ")"); 
		}		
	}
	return stack.peekFirst();
}
 	
public static void main(String[] args) {
	/**************************
	 Test cases given below:
	 **************************/
	try {
	StackPostfixToInfix convert=new StackPostfixToInfix();
	String retVal;
	System.out.println("\n\nPostfix: "+"abc/-ad/e-*");
	retVal=convert.postfixToInfix("abc/-ad/e-*");
	System.out.print("InFix: "+ retVal);
	
	System.out.println("\n\nPostfix: "+"ab+cd+*");
	retVal=convert.postfixToInfix("ab+cd+*");
	System.out.print("InFix: "+ retVal);
	
	
	}catch (Exception exception) {
		System.out.print("Exception: "+ exception);
		exception.printStackTrace();
	}
	
}
	
}