COMP 2100 Lab Exercise 6: Stack-Based Postfix-to-Infix Converter
(10 points)
Turn in before the next lab period

We are accustomed to writing arithmetic expressions using infix notation. This means that operators requiring two operands are written with the operator in the middle, e.g. 12 + 27 for addition. In expressions involving multiple operations, we sometimes need to use parentheses to override operator precedence. For example: 2 + 3 * 4 always yields 14 instead of 20 because multiplication takes precedence over addition. To get the result 20, we need to write it as ( 2 + 3 ) * 4.

The need for parentheses is eliminated if we write the expression using either prefix or postfix notation. In prefix notation, an operator precedes both its operands, e.g. + 12 27 and in postfix notation, an operator follows both its operands, e.g. 12 27 +. In this exercise we will focus on postfix notation.

Using postfix notation, 2 + 3 * 4 would be written as 2 3 4 * + and ( 2 + 3 ) * 4 would be written as 2 3 + 4 *. They are distinct and no parentheses are needed.

An infix expression can be converted to postfix using a stack. Similarly, a postfix expression can be converted to infix using a stack. For the latter, parentheses need to be introduced to the expression instead of removed from it. A pseudocode algorithm for postfix-to-infix conversion is described below.

Create a stack called symbolStack
For each token in a left-to-right scan of the expression {
	if (current token is an operator) {
		pop an operand from the symbolStack
		pop an operand from the symbolStack
		form an infix expression from the operator and operands
		parenthesize the infix expression
		push the infix expression on the symbolStack
	} else {  // token is an operand
		push the token onto the symbolStack
	}
}
pop the expression from the symbolStack

Your assignment is to write a postfix-to-infix converter based on the algorithm described above. The zip file ex6.zip contains three Java files: PostfixToInfixConverter.java (the class you will work with), PostfixToInfixConverterTest.java (a driver class for testing), and Operators.java (a handy utility described below). All your work will be in PostfixToInfixConverter.java.

Implementation Notes

1. Your code will be added to the PostfixToInfixConverter method called postFixToInfix(String postfix), which is basically a stub. Its parameter is the postfix expression. Its return value is the corresponding infix expression as a String.
2. Notice that the algorithm is within a loop that iterates once "for each token in a left-to-right scan of the expression". The expression is in a string, and each token (item) in the string is separated by spaces. This is the same technique you used for the Polynomial one-parameter constructor in Project 2 Implementation Note 7. An alternative technique is to invoke the string's split() method with postfix.split("\\s+"); This will return an array of String, where each array element contains a token. Then use a "foreach" loop to iterate over the array.
3. Use the java.util.Stack class for the stack. You will create and use a stack of String.
4. I've also written a handy little class providing services to work with arithmetic operators (+, -, *, /). It is called Operators (click for API), and it has two methods, isOperator() and getPrecedence(). The postfixToInfix() stub has an Operators object called operators. If, for example, the String variable token contains a token from the expression, then operators.isOperator(token) will return true if the token is an arithmetic operator and false otherwise.
5. The test program will ignore spaces when comparing the actual to the expected result. The expected results are given with spaces between each symbol.
6. For full credit, you will have to handle malformed postfix expressions. This will occur if either (a) there are less than two items on the stack when an operator is encountered, or (b) there is more than one item on the stack at completion of the expression scan. If either occurs, throw an IllegalArgumentException.

Scoring

Maximum 8 points without exception handling (Implementation Note 6), 10 points with exception handling.

To Turn In