Infix -> RPN Bug
Hello! I wrote this small class to convert infix to RPN, but I'm having a small bug in my output. When presented with:
3+4*5+6-7
My output should be:
3 4 5 * + 6 + 7 -
Instead, I get:
3 4 5 * 6 7 - +
I was wondering if anyone had any suggestions for my rules:
publicstaticvoid convert(String input){
// First tokenize input
Tokenizer t =new Tokenizer();
tokenizedInput =new ArrayList();
t.tokenize(input, tokenizedInput);
t.printOut(tokenizedInput);
// Now let's create a precedence hash table
precedence =new HashMap <String, Integer>();
precedence.put("^",new Integer(3));
precedence.put("*",new Integer(2));
precedence.put("/",new Integer(2));
precedence.put("+",new Integer(1));
precedence.put("-",new Integer(1));
precedence.put("#",new Integer(0));
String stackOp, operation;
for (int i=0; i < tokenizedInput.size(); i++){
Object current = tokenizedInput.get(i);
operation = current.toString();
if (tokenizedInput.get(i).equals("+") || tokenizedInput.get(i).equals("-") ||
tokenizedInput.get(i).equals("/") || tokenizedInput.get(i).equals("*") ||
tokenizedInput.get(i).equals("^")){
int infixPrecedence = precedence.get(operation);
System.out.println("Precedence: " + infixPrecedence);
if (stack.isEmpty()){
stack.push(tokenizedInput.get(i));
System.out.println("Pushed " + tokenizedInput.get(i));
}
else{
stackOp = stack.pop().toString();
System.out.println("stackOp: " + stackOp);
int stackPrecedence = precedence.get(stackOp);
if (stackPrecedence > infixPrecedence){
postfixOutput.add(stackOp);
System.out.println("Added " + stackOp +" to postfixOutput");
}
else{
stack.push(stackOp);
stack.push(operation);
System.out.println("Pushed " + stackOp +" and " + operation);
}
}
}
elseif (operation.equals("#")){
while (!stack.isEmpty()){
stackOp = stack.pop().toString();
postfixOutput.add(stackOp);
}
}
else{
postfixOutput.add(operation);
System.out.println("Added " + operation +" to postfixOutput");
}
}
while (!stack.isEmpty()){
System.out.println("Popping Remaining " + stack.view());
postfixOutput.add(stack.pop().toString());
}
for (int i=0; i<postfixOutput.size(); i++)
System.out.println(postfixOutput.get(i));
}
>
