CS 200, Spring 2015
P2: Converting infix expressions to postfix expressions using a stack and a queue

Due and late dates and times

Overview

The object of this assignment is to convert infix expressions to postfix expressions. In P1, the tokens on the input line were conveniently separated by blanks. This is not the case in P2. For example: " (1+2) * 3 " is a valid input line. This means that you need to build a iterator TokenIter, that scans the input line character by character and produces nextToken Strings (nextToken is a instance variable in TokenIter that is supposed to give you the next token). In the above example, the Strings produced by TokenIter should be: "(", "1", "+", ")", "*", and "3".

You will be using a Stack to manipulate operator Strings, and a Queue to cretae the postfix expression. Therefore, you need to implement a Stack of Strings and a Queue of Strings. The Stack and Queue operations are declared in the provided interfaces StackIF and QueueIF. Also two classes StackException and QueueException are provided. The TestDriver reads input file in line by line and exercises your In2Post code. Copy the following starter codes and input file, and put them in an Eclipse project:

You need to work on the following codes.

TokenIter

The provided TokenIter code does not compile, because it does not have the required methods for an iterator. Use eclipse to create the required methods hasNext(), and next(). The remove method has been provided. Don't change it. The provided main method exercises your TokenIter.

A regular definition is a 

  name = regular expression
where name can be used in in other regular definitions.

Valid tokens are numbers and operators, defined by the following regular definitions: 

   digit    =  [0-9]
   number   =  (digit)+
   operator =  "+" | "-" | "*" | "/" | "(" | ")"
The main method exercises TokenIter; it prints every next token surrounded by square brackets, to check for the lack of white space in the tokens, and produces the following output: 
line: [   15*(26+37) - 489/5*61 - (723-8456789)   ]
next token: [15]
next token: [*]
next token: [(]
next token: [26]
next token: [+]
next token: [37]
next token: [)]
next token: [-]
next token: [489]
next token: [/]
next token: [5]
next token: [*]
next token: [61]
next token: [-]
next token: [(]
next token: [723]
next token: [-]
next token: [8456789]
next token: [)]

Stack

The provided Stack code does not compile, because it does not have the required methods defined in StackIF. Use eclipse to define the required methods, see the StackIF for the description of these methods. Also, have the constructor initialize the relevant instance variables.

Queue

The provided Queue code does not compile, because it does not have the required methods defined in QueueIF. Use eclipse to create the required methods, see the QueueIF for the description of these methods. Also, have the constructor initialize the relevant instance variables.

In2Post

In2Post converts an valid infix expression to the corresponding postfix expression. It uses TokenIter to turn the input line into a sequence of tokens. On an empty line, a line without tokens, but maybe white space, it produces an empty result. The working of In2Post is described in the Lecture notes (L4 Queues), and in Prichard 7.4.

Testing and submitting your code

Use the Checkin webserver to exercise and submit your code. Submit your a P2.jar file containing Stack.java, Queue.java, and In2Post.java, and TokenIter.java**ONLY**.

Make sure you put ***java** files in your jar (not class files). The TAs can help you creating a proper jar file.