Java Code House

Today in this article I will tell you how to convert an infix expression to postfix expression using stack. This is an important application of stack. Most of the codes that you will find dont take into considerations the exponent and parenthesis. Here in our example we will consider everything and it will be able to convert any infix expression to postfix containing exponent(^) and parenthesis("(",")"). In our example we have also shown the current symbol processed, stack status and current postfix expression. We have solved it in the following way

• First push a sentinel element # to denote end of stack
• Scan each symbol of input infix expression
• If symbol is operator then check precedence with operator on stack top and take necessary action
• If left parenthesis then push it, and if right parenthesis then pop continously from stack till a left parenthesis is found
• If all symbols are scanned then pop all elements from stack and ad to postfix till # found.

import java.util.Scanner;
import java.util.Stack;

public class InfixToPostfix {

 /**
  * 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;
 }
 
 /**
  * Checks if c2 has same or higher precedence than c1
  * @param c1 first operator
  * @param c2 second operator
  * @return true if c2 has same or higher precedence
  */
 private boolean checkPrecedence(char c1, char c2){
  if((c2 == '+' || c2 == '-') && (c1 == '+' || c1 == '-'))
   return true;
  else if((c2 == '*' || c2 == '/') && (c1 == '+' || c1 == '-' || c1 == '*' || c1 == '/'))
   return true;
  else if((c2 == '^') && (c1 == '+' || c1 == '-' || c1 == '*' || c1 == '/'))
   return true;
  else
   return false;
 }
 
 /**
  * Converts infix expression to postfix
  * @param infix infix expression to be converted
  * @return postfix expression
  */
 public String convert(String infix){
  System.out.printf("%-8s%-10s%-15s\n", "Input","Stack","Postfix");
  String postfix = "";  //equivalent postfix is empty initially
  Stack<Character> s = new Stack<>();  //stack to hold symbols
  s.push('#');  //symbol to denote end of stack

  System.out.printf("%-8s%-10s%-15s\n", "",format(s.toString()),postfix);  

  for(int i = 0; i < infix.length(); i++){
   char inputSymbol = infix.charAt(i);  //symbol to be processed
   if(isOperator(inputSymbol)){  //if a operator
    //repeatedly pops if stack top has same or higher precedence
    while(checkPrecedence(inputSymbol, s.peek()))
     postfix += s.pop();
    s.push(inputSymbol);
   }
   else if(inputSymbol == '(')
    s.push(inputSymbol);  //push if left parenthesis
   else if(inputSymbol == ')'){
    //repeatedly pops if right parenthesis until left parenthesis is found
    while(s.peek() != '(') 
     postfix += s.pop();
    s.pop();
   }
   else
    postfix += inputSymbol;
   System.out.printf("%-8s%-10s%-15s\n", ""+inputSymbol,format(s.toString()),postfix);  
  }

  //pops all elements of stack left
  while(s.peek() != '#'){
   postfix += s.pop();
   System.out.printf("%-8s%-10s%-15s\n", "",format(s.toString()),postfix);  

  }
  
  return postfix;
 }
 
 /**
  * Formats the input  stack string
  * @param s It is a stack converted to string
  * @return formatted input
  */
 private String format(String s){
  s = s.replaceAll(",","");  //removes all , in stack string
  s = s.replaceAll(" ","");  //removes all spaces in stack string
  s = s.substring(1, s.length()-1);  //removes [] from stack string
  
  return s;
 }
 
 public static void main(String[] args) {
  InfixToPostfix obj = new InfixToPostfix();
  Scanner sc = new Scanner(System.in);
  System.out.print("Infix : \t");
  String infix = sc.next();
  System.out.print("Postfix : \t"+obj.convert(infix));
 }
}

-------------------------------------------------------------------------------------------------------------------------
-------------------------------------------------------------------------------------------------------------------------

Infix :         A+(B*C-(D/E^F)*G)*H
Input   Stack     Postfix
        #
A       #         A
+       #+        A
(       #+(       A
B       #+(       AB
*       #+(*      AB
C       #+(*      ABC
-       #+(-      ABC*
(       #+(-(     ABC*
D       #+(-(     ABC*D
/       #+(-(/    ABC*D
E       #+(-(/    ABC*DE
^       #+(-(/^   ABC*DE
F       #+(-(/^   ABC*DEF
)       #+(-      ABC*DEF^/
*       #+(-*     ABC*DEF^/
G       #+(-*     ABC*DEF^/G
)       #+        ABC*DEF^/G*-
*       #+*       ABC*DEF^/G*-
H       #+*       ABC*DEF^/G*-H
        #+        ABC*DEF^/G*-H*
        #         ABC*DEF^/G*-H*+
Postfix :       ABC*DEF^/G*-H*+

-------------------------------------------------------------------------------------------------------------------------
-------------------------------------------------------------------------------------------------------------------------
DOWNLOAD the source from Mediafire
DOWNLOAD the source from 4shared