CSC220 Lab Number 4
Due: 10:59AM, Tuesday, September 28

The goal of this lab is develop a code for converting infix expressions to postfix expressions where input expressions may contain parentheses.

Here is a sample program (a jar file) that does the job. To run the program execute "java -jar PostFixConversion.jar".

Download the following file:

1. PostFixMini.java

This is a program that converts infix expressions to postfix expression where input sting does not contain parentheses. Note also that operands (that is, numbers) appearing in the input expression are simply appended to the output in the order they appear. So the question that the conversion method (convert()) deals with is only where to place the operators in the series of operands. Note that the method uses two integers, which are the most recent operators whose positions in the postfix expression are yet to be determined. Call these operators operator1 and operator2. The following rules apply:

1. If operator1 is undefined then operator2 is undefined, too.
2. If operator1 is either "*" or "/" then
   • operator2 is undefined,
   • the next token is an operand, and
   • upon receiving the token, operator1 must be output and then reset to undefined.
3. If operator1 is either "+" or "-" and if operator2 is undefined,
• receiving an operand doesn't trigger change on either operator1 or operator2,
• on receiving either "+" or "-", operator1 should be output and the value of opeartor1 must become the operator has just been received,
• on receiving either "*" or "/", the value of operator2 should become the operator that just has been received.
4. If operator1 is either "+" or "-" and if operator2 is either "*" or "/",
   • if the new operator is either "+" or "-", then operator2 and then operator1 must be appened immediately,
   • if the new operator is either "*" or "/", operator2 must be appended and then the new operator must become operator2.

We will deal with parentheses using multiple levels of processing, beginning at the bottom level of processing, as follows:

1. When an open parenthesis has arrived, we will save operator1 and operator2 of the current process and move to a new level of processing.
2. When a close parenthesis has arrived, we will conclude the current level as if the end of input has been reached at that level, and then move back to the previous level. The output generated during at that level is viewed as an operand in the lower level.<;i>

To accomplish the goal, we do the following.

1. The tokenize() method has already been constructed so that it deals with all possible open and close parentheses.
2. We add a method for checking whether a given String is an open parenthesis or not and another method for checking whether a given String is a close parenthesis.
3. We modify the convert method as follows:
   • If an open parenthesis is encountered, then operator1 and operator2 are pushed into stacks and the value is set to undefined for both operator1 and operator2.
   • If a close parenthesis is encountered, then operator1 and operator2 are processed as if it the end of input were encountered, and then the values are poppoed from the stacks.