Hi all!
I'm currently trying to finish up an assignment that is due in a few hours. Here's my delimma, according to the text book and the professor the following algorithm to convert an infix to postfix is as follows:
1. Two stacks will be used in the conversion(expressionStack and operatorStack)
2. if an operand is encountered, push onto expressionStack
3. if an operator is encountered, including the "(" push onto the temporary stack
4. if a ")" is encountered, pop each operator off the temporaryStack and push it into the expressionStack until a "(" is encountered in the temporaryStack. Once a "(" is encountered, pop that off the temporaryStack.
Traverse through the infix expression until the end is reached then pop everything from the temporaryStack onto the expression stack.
Here's the code I wrote for it:
public String convertInfixToPostfix() throws PostfixConversionException {
//if there is an unbalace set of parenthesis, throw exception
if(!isBalance()) {
throw new PostfixConversionException("Unable to convert infix expression");
}
for(int i = 0; i < this.infixExpression.length(); i++) {
char ch = this.infixExpression.charAt(i);
//if ch is an operand, push onto stack
switch(ch) {
case '0':
case '1':
case '2':
case '3':
case '4':
case '5':
case '6':
case '7':
case '8':
case '9':
this.expressionStack.push("" + ch);
break;
//if ch is an operator or a '(', push onto temporaryOperator stack
case '+':
case '-':
case '*':
case '/':
case '%':
case '(':
this.temporaryOperator.push("" + ch);
break;
/*if ch is ')' push all operators from temporaryOperator stack onto expressionStack until
* until a matching '(' is encountered*/
case ')':
//while the top does not equal "(" pop everything off temporaryOperator stack and onto expression stack until a '(' is encountered
while(!"(".equals(this.temporaryOperator.top())) {
this.expressionStack.push(this.temporaryOperator.pop());
}
//removes one open matching '('
this.temporaryOperator.pop();
break;
default:
System.out.println("Unable to converted due to invalid characters entered");
break;
}
}
//while expressionStack is not empty, push everything into temporaryOperator stack
while(!this.expressionStack.isEmpty()) {
this.temporaryOperator.push(this.expressionStack.pop());
}
while(!this.temporaryOperator.isEmpty()) {
this.postfixExpression = this.postfixExpression + this.temporaryOperator.pop();
}
return this.postfixExpression;
}
The problem is, unless I did the code wrong (which I don't think i did), the method incorrectly converts the infix to the postfix expression. Meaning the algorithm provided by the text book and professor is incorrect. Are there other ways of converting an infix to postfix expression?