CONVERTING FROM INFIX TO POSTFIX

THIS COUNTS FOR TWO LABS!

In this lab, you will work with a project to convert from infix notation to postfix notation. Before you start, make sure you review the relevant section from Chapter 8 of the text, especially the material on tokens.

Also, a considerable effort will be expended on input editing. For example, it is illegal to have a left parenthesis immediately followed by an operator.

Description of the Project

• a Token class to handle the tokens. Some of the methods are getToken, which retrieves the next token from the infix string, and checkPrevious, which compares the current token to the previous token to see if they are incompatible.

• a Compiler class to handle the overall task of converting from infix to postfix. This class has three methods: convertOrReject, returnPostfixOrError, and applyTransMatrix

• an Error class, to handle errors and error messages

• the Stack class to handle operatorStack, a stack of tokens representing operators.

• the Queue class for the postfix container . Tokens will be inserted at the tail of postfix during the conversion from infix.

• the ArrayList class for the symbol table. As a simplification, each symbol-table entry will consist of an identifier token's referent: the substring, of the infix string, that contains the identifier referred to by the token.

The overall strategy is this: In the processInput method of the InfixToPostfix class, an infix string is read in and sent to the convertToPostfix method. Repeatedly in convertToPostfix, the next token is obtained from the infix string and, if no errors are found, the token is processed by applyTransMatrix. This method uses the infix token and the stack token (initially, empty) as indexes into the transition matrix, which determines the action to be taken. For example, if the infix token's category is MULT_OP and the category of operatorStack's top token is LEFT_PAR, then the action to be taken is PUSH, so the infix token will be pushed onto operatorStack.

After the entire infix string has been tokenized and processed, either the de-tokenized postfix Queue or an error message is printed. As an example of de-tokenizing, if the token's category is IDENTIFIER, the symbol table for that token contains the substring of the infix string that was used to create that token to begin with. That substring, which constitutes the identifier, is printed. If instead, the token were printed, that would not be helpful to a reader. In fact, in a real compiler, nothing gets printed, and the token is processed by the next part of the compiler: the semantic analyzer, which determines the meaning -- in terms of machine language instructions -- of the token.