# Infix to Postfix Conversion

• 01-02-2013, 09:32 PM
David M.
Infix to Postfix Conversion
I'm trying to convert a given infix expression into postfix. Right now I'm trying to get a simple test case working. So far it just accepts integer inputs, then converts the expression into postfix notation and stores it in an ArrayList for simplifying later. I have the simplification working but my conversion does something weird. If I take the expression 4*(2+3), it should come out "4 2 3 + *" but my converter is throwing the left (opening) parenthesis into the equation so it looks like "4 2 3 + ( *" and I can't figure out why. Here's the code I'm using:

Code:

```import java.util.ArrayList; import java.util.Scanner; import java.util.Stack; public class Converter {         public static void main(String[ ] args)         {                 Scanner in = new Scanner(System.in);                 System.out.println("Enter an infix expression");                 String input = in.nextLine();                                 ArrayList<String> postfixEquation = new ArrayList<String>();                 Stack<String> stack = new Stack<String>();                                 String curNum = "";                 String curToken = "";                 int curTokenPrecedence = 0;                                 for(int i = 0; i < input.length(); i++)                 {                         curToken = input.substring(i, i+1);                         if(isInteger(curToken))                //If the current token is a number                                 curNum += curToken;                //Add it to the curNumber string                         else                                                //Not a number                         {                                 if(curNum != "")                                        //If there is a number in curNum                                 {                                         postfixEquation.add(curNum);        //Add the current number to the postfix string                                         curNum = "";                                        //Reset curNum                                 }                                                                 curTokenPrecedence = getPrecedence(curToken);        //Get the current token's precedence                                                                 //If there is no number on the stack or the token's operator is greater than the first operator on the stack                                 if(stack.empty() || curTokenPrecedence > getPrecedence(stack.peek()) || curToken.equals("("))                                         stack.push(curToken);                                 else        //Current token's precedence less than token on the stack                                 {                                         //Until there is no operator on the stack or an operator with lower precedence                                         while(!stack.empty() && curTokenPrecedence <= getPrecedence(stack.peek()))                                                 postfixEquation.add(stack.pop());        //Pop operators off the stack                                                                                         stack.push(curToken);                                 }                         }                                                 if(curToken.equals(")"))                         {                                 stack.pop();        //Discard the right parenthesis                                                                 while(!stack.empty())                                 {                                         if(stack.peek().equals("("))                                         {                                                 stack.pop();                                                 break;                                         }                                         postfixEquation.add(stack.pop());                                 }                         }                 }                                 if(curNum != "")                         postfixEquation.add(curNum);                                 //Pop remaining operators off the stack                 while(!stack.empty())                         postfixEquation.add(stack.pop());                                 for(int i = 0; i < postfixEquation.size(); i++)                         System.out.println(postfixEquation.get(i));                                         in.close();         }                 //Returns whether the given string is an integer or an operator         public static boolean isInteger(String num)         {                 try                 {                         Integer.parseInt(num);                         return true;                        //Number                 }                 catch(NumberFormatException e)                 {                         return false;                        //Operator                 }         }                 //Returns precedence for the given operator         public static int getPrecedence(String operator)         {                 int precedence = 0;                 switch(operator)                 {                 case "!":                         precedence = 4;                 case "^":                         precedence = 3;                         break;                 case "*":                 case "/":                         precedence = 2;                         break;                 case "+":                 case "-":                         precedence = 1;                         break;                 case "(":                         precedence = 0;                         break;                 }                                 return precedence;         } }```
• 01-02-2013, 09:39 PM
KevinWorkman
Re: Infix to Postfix Conversion
Have you stepped through this with a debugger, or at least added some print statements, to figure out what's going on? Debugging your code is an important lesson that every programmer has to learn.

Hint: Don't use == or != with Strings. Do a search on this forum or on google for an explanation of what to use instead, and why.
• 01-03-2013, 12:09 AM
David M.
Re: Infix to Postfix Conversion
I had been running through this section of code:
Code:

```if(curToken.equals(")")) {     stack.pop();    //Discard the right parenthesis                     while(!stack.empty())     {         if(stack.peek().equals("("))         {             stack.pop();             break;         }     postfixEquation.add(stack.pop());     }  }```
I just ran through everything and found the problem was in this comparison:
Code:

```while(!stack.empty() && curTokenPrecedence <= getPrecedence(stack.peek()))     postfixEquation.add(stack.pop());  //Pop operators off the stack```
Since I hadn't assigned a precedence to ')' it got the default 0. This was <= everything on the stack so the stack was emptied. I fixed it by assigning ')' to a precedence higher than anything else.