CS 200, Fall 2016
P2: Converting arithmetic 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. An input line will contain an infix expression, for example: " (1+12) * 3567 ". You need to build an iterator TokenIter, that scans the input line and produces nextToken Strings (nextToken is a instance variable in TokenIter that produces the next token). In the above example, the Strings produced by TokenIter should be: "(", "1", "+", "12", ")", "*", and "3567".

You will be using a Stack to manipulate operator Strings, and a Queue to create 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 an input file 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 iterator methods. 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, operators and parentheses, defined by the following regular definitions: 

   digit       =  [0-9]
   number      =  (digit)+
   operator    =  "+" | "-" | "*" | "/"
   parenthesis =  "(" | ")"
The main method exercises TokenIter; it prints every next token surrounded by square brackets, to show white space, 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. The operators "+", "-", "*", and "/" are all binary opertors. It uses TokenIter to turn a String (input line) into a sequence of Strings (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 (L3 Queues), and in Prichard 7.4.

Testing and submitting your code

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

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