Recognizing Parenthesis in an Infix to Postfix Conversion

[macintoshgeek]

Here is a java class I had to make for my data structures class. I know that this is far from the best way to do the conversion, but it is off of the pseudo code he gave in class and is therefor what he is looking for. The only thing he left for us to figure out on our own was for how the algorithm recognizes parenthesis. The program runs just fine when I input an expression without them, but the minute I add parenthesis the program won't run, specifically, through some debugging, I found that the close parenthesis does this ")". I marked with comments where the actual parenthesis part of the method is. Thanks for the help!


public class InToPost {
private Stack theStack;

private String infix;

private String postfix = "";

public InToPost(String in) {
infix = in;
int stackSize = infix.length();
theStack = new Stack(stackSize);
}

public String convert(){
for (int i = 0; i < infix.length(); i++) {
char ch = infix.charAt(i);
if (Character.isDigit(ch)){
postfix = postfix + ch;
}



//Check for right parenthesis and empty stack until left parenthesis is read
else if ((ch == ')') && (!theStack.isEmpty())){
while (theStack.topStk() != '('){

char topSymb = theStack.pop();
if (topSymb != '(') {
postfix = postfix + topSymb;
}
}

if (!theStack.isEmpty()) {
theStack.pop();
}
}




else{
while ((!theStack.isEmpty())&&(prcd(theStack.topStk(),ch) == true)){
char topSymb = theStack.pop();
postfix = postfix + topSymb;
}
theStack.push(ch);
}
}
while(theStack.isEmpty() == false){
char topSymb = theStack.pop();
postfix = postfix + topSymb;
}
return postfix;
}

public boolean prcd(char one, char two) {
return (charToPrcd(one) >= charToPrcd(two));
}
private int charToPrcd(char ch) {
switch (ch) {
case '+' : case '-' : return 1;
case '*' : case '/' : return 2;
case '$' : return 3;
case '(' : return 4;
default : return 0;
}
}

public static void main(String[] args){
String input = "(2+3)*4";
String output;
InToPost theTrans = new InToPost(input);
output = theTrans.convert();
System.out.println("Postfix is " + output + '\n');

}


}

[macintoshgeek]

Also, here is the error I get:

Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: -1
at Stack.topStk(Stack.java:18)
at InToPost.convert(InToPost.java:23)
at InToPost.main(InToPost.java:66)

[keang]

Please use code tags when posting code.

Your problem is you are removing the open bracket from the stack in your final else clause, ie here:

while ((!theStack.isEmpty())&&(prcd(theStack.topStk(),ch) == true)){
    char topSymb = theStack.pop();
    postfix = postfix + topSymb;
}