Results 1 to 3 of 3
  1. #1
    David M. is offline Member
    Join Date
    Apr 2011
    Location
    Kansas
    Posts
    26
    Rep Power
    0

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

  2. #2
    KevinWorkman's Avatar
    KevinWorkman is offline Crazy Cat Lady
    Join Date
    Oct 2010
    Location
    Washington, DC
    Posts
    3,839
    Rep Power
    8

    Default 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.
    How to Ask Questions the Smart Way
    Static Void Games - Play indie games, learn from game tutorials and source code, upload your own games!

  3. #3
    David M. is offline Member
    Join Date
    Apr 2011
    Location
    Kansas
    Posts
    26
    Rep Power
    0

    Default 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;
             }
         postfixEquation.add(stack.pop());
         }
     }
    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.

Similar Threads

  1. Infix to postfix using queue
    By bdl1127 in forum New To Java
    Replies: 2
    Last Post: 10-19-2012, 02:46 AM
  2. need help converting from infix to postfix notation
    By miatech in forum New To Java
    Replies: 1
    Last Post: 06-27-2012, 09:10 PM
  3. Trouble with converting infix to postfix
    By mustachio in forum New To Java
    Replies: 7
    Last Post: 07-21-2011, 03:48 AM
  4. Infix to Postfix using array
    By Franneldort in forum New To Java
    Replies: 0
    Last Post: 10-11-2010, 05:57 PM
  5. Replies: 1
    Last Post: 07-05-2008, 03:08 PM

Posting Permissions

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