# Thread: Infix to Postfix Conversion

1. Member
Join Date
Apr 2011
Location
Kansas
Posts
26
Rep Power
0

## 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:

Java 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;
}
}
}
}

if(curNum != "")

//Pop remaining operators off the stack
while(!stack.empty())

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;
}
}```

2. ## 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.

3. Member
Join Date
Apr 2011
Location
Kansas
Posts
26
Rep Power
0

## Re: Infix to Postfix Conversion

I had been running through this section of code:
Java Code:
```if(curToken.equals(")"))
{
stack.pop();    //Discard the right parenthesis

while(!stack.empty())
{
if(stack.peek().equals("("))
{
stack.pop();
break;
}
}
}```
I just ran through everything and found the problem was in this comparison:
Java 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.

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•