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

6 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
  6. thanks for posting this code. It was very helpfull for my project. very simple to understand.

    ReplyDelete

Total Pageviews

Followers


Labels

Popular Posts

free counters