Trouble with converting infix to postfix

[mustachio]

So I have this program that's supposed to convert an infix expression into a postfix expression. Unfortunately, it doesn't work.

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

[Junky]

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.

[mustachio]

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.

[pbrockway2]

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

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:

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

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?

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:

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.

[Junky]

Aha!

I tried running your code and couldn't work out why the stack was not empty.

if (chValue == '(');
    stack.push('(');

Look very carefully at the if statement.

[Junky]

There are several other problems.

As mentioned above you will have the stack empty exception thrown when you do the peek.

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)?

[mustachio]

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:

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.

[mustachio]

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