Tuesday, July 22, 2014

Today I am going to show how to convert a postfix expression to an infix expression using stack in Java. In an earlier post here we ahve shown how to convert an infix expression to postfix using stack. Here we will just try to do the reverse. Here in our example we will be able to convert any postfix expression to infix irrespective of the operators. A number of parenthesis may be generated extra which were not there in original infix expression. The parenthesis that may be generated extra will have no impact on actual expression, they are just for better understanding. The process of postfix to infix conversion is summarised below -


1.  Create an empty stack that can hold string values.
2.  Scan the postfix expression from left to right
     2a. If operand then push into stack
     2b. If operator then
           1.  Pop first two elements
           2.  Now make a string with "(" + operand2 + operator + operand1 + ")"
           3.  Push the new string onto stack
3. Pop the element on stack.
------------------------------------------------------------------------------------------------------
Java Source Code
------------------------------------------------------------------------------------------------------
import java.util.Scanner;
import java.util.Stack;

public class PostfixToInfix {
 
 /**
  * Checks if the input is operator or not
  * @param c input to be checked
  * @return true if operator
  */
 private boolean isOperator(char c){
  if(c == '+' || c == '-' || c == '*' || c =='/' || c == '^')
   return true;
  return false;
 }
 
 /**
  * Converts any postfix to infix
  * @param postfix String expression to be converted
  * @return String infix expression produced
  */
 public String convert(String postfix){
  Stack<String> s = new Stack<>();
  
  for(int i = 0; i < postfix.length(); i++){
   char c = postfix.charAt(i);
   if(isOperator(c)){
    String b = s.pop();
    String a = s.pop();
    s.push("("+a+c+b+")");
   }
   else
    s.push(""+c);
  }
  
  return s.pop();
 }
 
 public static void main(String[] args) {
  PostfixToInfix obj = new PostfixToInfix();
  Scanner sc =new Scanner(System.in);
  System.out.print("Postfix : ");
  String postfix = sc.next();
  System.out.println("Infix : "+obj.convert(postfix));
 }
}
------------------------------------------------------------------------------------------------------
Output
------------------------------------------------------------------------------------------------------
Postfix : ABC^^
Infix : (A^(B^C))
------------------------------------------------------------------------------------------------------
Download Links
------------------------------------------------------------------------------------------------------
DOWNLOAD the source from Mediafire
DOWNLOAD the source from 4shared

5 comments:

  1. How will you convert a postfix to infix with expression tree?

    ReplyDelete
  2. This code does not produce the right results. If the postfix expression was 359+-23*/, your code produces ((3-(5+9))/(2*3)), when it should be (3-5+9)/(2*3).

    ReplyDelete
  3. In regards to K.O., both those answers produce the same answer, the difference is simply the amount of parentheses. The problem with wanting to eliminate parentheses is that it would destroy the result of the program if say a higher order operator were where the subtraction symbol is.

    ReplyDelete
  4. Why are you creating a PostfixToInfix object with no constructor?

    ReplyDelete
  5. In regards to K.O., you are right - they certainly do NOT produce the same answer.

    ReplyDelete

Total Pageviews

Subscribe via Email

Followers


Popular Posts

About Me

My photo

I am a student of BTech Computer Science Engineering from RCCIIT,Kolkata. I am a crazy lover of Java and wants to settle as a Java developer. I have a seven years Java experience with an application developer experience for 2 years. Recently from March 2012 I am a registered S40 app developer for Nokia and has corrected an app of them. I am currently writing blogs to encourage and grow interest in all those who don't know or learning Java.