Results 1 to 8 of 8
  1. #1
    mustachio is offline Member
    Join Date
    Jun 2011
    Posts
    6
    Rep Power
    0

    Default Trouble with converting infix to postfix

    So I have this program that's supposed to convert an infix expression into a postfix expression. Unfortunately, it doesn't work.
    Java Code:
    import java.util.*;
    import java.lang.*;
    
    public class PostfixConversion
    {
    	private static int precedenceLevel (char op)//Determines the precedence value of an operator
    	{
    		switch (op){
    			case '+':
    			case '-':
    				return 0;
    			case '*':
    			case '/':
    				return 1;
    			default:
    				throw new IllegalArgumentException ("Operator unknown: " + op);
    		}
    	}
    
    	private static boolean precedence (char first, char second)//Determines the
    	{
    		boolean precedent = false;
    		int char1 = precedenceLevel(first);
    		int char2 = precedenceLevel(second);
    		if (char1 >= char2)
    			precedent = true;
    		else
    			precedent = false;
    		return precedent;
    	}
    
    	public static String convertToPostfix(String infixExp)
    	{
    		Stack<Character> stack = new Stack<Character>();
    		String postfix = "";
    		for (int i = 0; i < infixExp.length(); i++)
    		{
    			char chValue = infixExp.charAt(i);
    			if (chValue == '(');
    				stack.push('(');
    			if (chValue == ')'){
    				Character oper = stack.peek();
    				while (!(oper.equals('(')) && !(stack.isEmpty()))
    				{
    					postfix += oper.charValue();
    					stack.pop();
    					oper = stack.peek();
    				}
    				if (stack.isEmpty() && !oper.equals('('))
    					return postfix = "There is no matching left parenthesis.";
    				stack.pop();
    			}
    			if (chValue == '*' || chValue == '/' || chValue == '+' || chValue == '-')
    			{
    				Character oper = stack.peek();
    				if(stack.isEmpty())
    					stack.push(chValue);
    				else {
    					boolean operator = precedence(oper, chValue);
    					if (operator == false)
    						stack.push(chValue);
    					else{
    						while (operator == true){
    							stack.pop();
    							Character operation = stack.peek();
    							operator = precedence(oper, chValue);
    						}
    						stack.push(chValue);
    					}
    				}
    			}
    			else
    				postfix += chValue;
    		}
    
    		while (!stack.isEmpty())
    		{
    			Character oper = stack.peek();
    			if (!oper.equals(new Character('(')))
    			{
    				stack.pop();
    				postfix += oper.charValue();
    			}
    			if (oper.equals(new Character('(')))
    				return postfix = "There is no matching right parenthesis.";
    		}
    
    		return postfix;
    	}
    }
    
    import java.io.*;
    
    public class Assignment9
     {
      public static void main (String[] args) throws IOException
       {
           char input1;
           String inputInfo;
           String line = new String();
    
           printMenu();
    
           InputStreamReader isr = new InputStreamReader(System.in);
           BufferedReader stdin = new BufferedReader(isr);
    
           do  // will ask for user input
            {
             System.out.println("What action would you like to perform?");
             line = stdin.readLine();
             input1 = line.charAt(0);
             input1 = Character.toUpperCase(input1);
    
             if (line.length() == 1)
              {
               // matches one of the case statements
               switch (input1)
                {
                 case 'E':   //Enter String
                   System.out.print("Please enter a string.\n");
                   inputInfo = stdin.readLine().trim();
                   System.out.println(PostfixConversion.convertToPostfix(inputInfo));
                   break;
                 case 'Q':   //Quit
                   break;
                 case '?':   //Display Menu
                   printMenu();
                   break;
                 default:
                   System.out.print("Unknown action\n");
                   break;
                }
              }
             else
              {
               System.out.print("Unknown action\n");
              }
            } while (input1 != 'Q' || line.length() != 1);
       }
    
    
      /** The method printMenu displays the menu to a user**/
      public static void printMenu()
       {
         System.out.print("Choice\t\tAction\n" +
                            "------\t\t------\n" +
                            "E\t\tEnter String\n" +
                            "Q\t\tQuit\n" +
                            "?\t\tDisplay Help\n\n");
      }
    }
    When I put in an expression that includes an operator, it throws the illegal argument exception, when I enter just ), it returns it normally, and when I enter anything else, it returns the "there is no right parenthesis" message. So what am I doing wrong? Any help would be greatly appreciated

  2. #2
    Junky's Avatar
    Junky is offline Grand Poobah
    Join Date
    Jan 2011
    Location
    Dystopia
    Posts
    3,789
    Rep Power
    7

    Default

    Java Code:
    if (chValue == '*' || chValue == '/' || chValue == '+' || chValue == '-') {
            Character oper = stack.peek();
            if(stack.isEmpty())
    One thing I noticed is that if your algorithm is correct then it should be impossible for the stack to be empty at this point (unless you have provided a malformed infix expression). If it was empty then the previous line will throw an exception.

    But that has nothing to do with your problem.

  3. #3
    mustachio is offline Member
    Join Date
    Jun 2011
    Posts
    6
    Rep Power
    0

    Default

    It would be empty if it was the first operator to go through. Example: A+B. 'A' goes straight to the postfix string, '+' goes into the stack, 'B' goes into the string, and then the stack would be emptied and '+' would be added to the end, making AB+. Of course, I'm saying this based off how I had hoped to write it.

  4. #4
    pbrockway2 is offline Moderator
    Join Date
    Feb 2009
    Location
    New Zealand
    Posts
    4,565
    Rep Power
    12

    Default

    When I put in an expression that includes an operator, it throws the illegal argument exception
    It might be good to describe precisely what happens in this case.

    Here's the output that I see

    Java Code:
    What action would you like to perform?
    e
    Please enter a string.
    1+2
    Exception in thread "main" java.lang.IllegalArgumentException: Operator unknown: (
    	at PostfixConversion.precedenceLevel(PostfixConversion.java:15)
    	at PostfixConversion.precedence(PostfixConversion.java:22)
    	at PostfixConversion.convertToPostfix(PostfixConversion.java:58)
    	at Assignment9.main(Assignment9.java:33)
    The runtime stack trace is very useful. It point us towards line 58 of PostfixConversion.java. This is the line that says "boolean operator = precedence(oper, chValue);" which leads, eventually to the exception because the first argument - oper - is "bad". I know it's the first argument that's giving rise to the problem because the stack trace mentions line 22 which is "int char1 = precedenceLevel(first);".

    OK, so I add some debugging code:

    Java Code:
    if (chValue == '*' || chValue == '/' || chValue == '+' || chValue == '-')
    {
        Character oper = stack.peek();
        if(stack.isEmpty())
            stack.push(chValue);
        else {
            [color=green]System.err.printf("oper=%c chValue=%c%n", oper, chValue);[/color]
            boolean operator = precedence(oper, chValue);
            // etc
    Now I see

    Java Code:
    What action would you like to perform?
    e
    Please enter a string.
    1+2
    oper=( chValue=+
    Exception in thread "main" java.lang.IllegalArgumentException: Operator unknown: (
    	at PostfixConversion.precedenceLevel(PostfixConversion.java:15)
    	at PostfixConversion.precedence(PostfixConversion.java:22)
    	at PostfixConversion.convertToPostfix(PostfixConversion.java:59)
    	at Assignment9.main(Assignment9.java:33)
    What! "oper=(", but I didn't enter a left paren. What's going on; what does stack contain?

    Java Code:
    if (chValue == '*' || chValue == '/' || chValue == '+' || chValue == '-')
    {
        Character oper = stack.peek();
        if(stack.isEmpty())
            stack.push(chValue);
        else {
            [color=green]System.err.printf("oper=%c chValue=%c%n", oper, chValue);
            System.err.printf("stack=%s%n", stack);[/color]
            boolean operator = precedence(oper, chValue);
            // etc
    
    
    What action would you like to perform?
    e
    Please enter a string.
    1+2
    oper=( chValue=+
    stack=[(, (]
    Exception in thread "main" java.lang.IllegalArgumentException: Operator unknown: (
    	at PostfixConversion.precedenceLevel(PostfixConversion.java:15)
    	at PostfixConversion.precedence(PostfixConversion.java:22)
    	at PostfixConversion.convertToPostfix(PostfixConversion.java:60)
    	at Assignment9.main(Assignment9.java:33)
    So it seems the stack is getting left parens pushed into it when I have typed digits. So I look for all the push() calls in that method. Most of them are inside the if block where chValue is an operator. Only one is left - to reason Sherlock Holmes style - as the villian:

    Java Code:
    public static String convertToPostfix(String infixExp)
    {
        Stack<Character> stack = new Stack<Character>();
        String postfix = "";
        for (int i = 0; i < infixExp.length(); i++)
        {
            char chValue = infixExp.charAt(i);
            if (chValue == '(');
                stack.push('(');
    There is an error in those last pair of lines.

    -----

    You will be much less prone to this error if you use braces with every if statement. And you should change your code accordingly. [Edit] Rereading your code I see that you are a bit inconsistent about brace placement as well. Perhaps it is not too late for you to see the light and put left braces where Nature intended them to go: at the end of the line opening containing the if/for/while. That way every line beginning "if" will end "right paren, space, left brace" and semicolons will be consistently banished.

    -----

    The stack trace is *really* important and should be posted in its entirity as part of a precise description of the problem. (Along with other output). Use lots of debugging code to see what is happening. Or a debugger if you are familiar with them: but System.out.println() will do.
    Last edited by pbrockway2; 07-21-2011 at 03:06 AM.

  5. #5
    Junky's Avatar
    Junky is offline Grand Poobah
    Join Date
    Jan 2011
    Location
    Dystopia
    Posts
    3,789
    Rep Power
    7

    Default

    Aha!

    I tried running your code and couldn't work out why the stack was not empty.
    Java Code:
    if (chValue == '(');
        stack.push('(');
    Look very carefully at the if statement.

  6. #6
    Junky's Avatar
    Junky is offline Grand Poobah
    Join Date
    Jan 2011
    Location
    Dystopia
    Posts
    3,789
    Rep Power
    7

    Default

    There are several other problems.

    As mentioned above you will have the stack empty exception thrown when you do the peek.
    Java Code:
    while (operator == true){
        stack.pop();
        Character operation = stack.peek();
        operator = precedence(oper, chValue);
    }
    What is the point of the peek if you do nothing with it?

    If your infix expression is 72+12 the postfix expression will be 7212+. Is that (7 + 212) or (72 +12) or (721 + 2)?

  7. #7
    mustachio is offline Member
    Join Date
    Jun 2011
    Posts
    6
    Rep Power
    0

    Default

    Thanks Junky, it's these stupid mistakes that kill me. I got rid of the semi-colon from the if statement, I fixed the operator to equal precedence(operation, chValue), as well as caught another one here:
    Java Code:
    if (chValue == '*' || chValue == '/' || chValue == '+' || chValue == '-')
    			{
    				Character oper = stack.peek();
    				if(stack.isEmpty())
    					stack.push(chValue);
    				else {
    so now the Character oper = stack.peek(); occurs within the else statement, where it was supposed to. Also, the expression only takes in variables, not exact values, which is why I didn't do anything about that (sorry for not mentioning that earlier). The program now works mostly, except I just realized that the parentheses aren't supposed to be included in the postfix expression, so I have to go back and fix that. But for sure, thank you.

  8. #8
    mustachio is offline Member
    Join Date
    Jun 2011
    Posts
    6
    Rep Power
    0

    Default

    And to pbrockway2, thanks for narrowing it down. Saving lives, sir.

Similar Threads

  1. trouble converting unsigned int to byte array
    By zsefv in forum New To Java
    Replies: 9
    Last Post: 05-06-2011, 09:17 AM
  2. Infix to Prefix
    By Sasarai in forum Advanced Java
    Replies: 4
    Last Post: 12-08-2010, 03:57 PM
  3. Infix to Postfix using array
    By Franneldort in forum New To Java
    Replies: 0
    Last Post: 10-11-2010, 05:57 PM
  4. Replies: 1
    Last Post: 07-05-2008, 03:08 PM
  5. Replies: 0
    Last Post: 04-15-2008, 07:36 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
  •