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,807
    Rep Power
    10

    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,712
    Rep Power
    15

    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,807
    Rep Power
    10

    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,807
    Rep Power
    10

    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, 04: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
  •