CS 200, Spring 2017
P2: Converting infix expressions to postfix expressions, and evaluating postfix expressions

Due and late dates and times

Overview

The object of this assignment is to convert logical infix expressions to postfix expressions, and to evaluate these postfix expressions. Infix expressions occur on individual input lines in input files.

Copy the following starter codes and put them in an Eclipse project:

Debug

The Debug class provides an easy way to include debug prints without the need to remove these. Do not change this code. Debugging is turned on by having "-debug" as first parameter on the command line, and is initialized in a client main by 
         args = Debug.init(args)
which removes "-debug" and initiates debugging, if "-debug" is present as the first parameter in args. See DEBUG doc for more information.

Stack.java has example Debug code in it. When grading your codes, the testServer will not turn on debug.

You need to work on the following codes.

TokenIter

You need to build an iterator TokenIter, that scans an input line and produces Strings containing tokens. The variable nextToken is an instance variable in TokenIter that is supposed to contain the next token if there is one and null it there is none. Valid tokens are: 
  "true", "false", "or" "and", "not", "(", ")"
Invalid tokens should be discarded. If the input line is e.g.: 
  true and not (false or true)
the strings produced by subsequent calls to the next() method of a TokenIter should be: 
  "true", "and", "not", "(", "false", "or", "true", ")".
Examples of valid input lines are: 
true

true   or false
not (   not (true and    false))
The first input line contains the simple logic expression "true". The second input line is empty and demonstrates that your program needs to handle empty inputs properly. The third demonstrates that operands "true" and "or" must be separated by one or more blanks, so e.g., 
  trueor notfalse

has two incorrect input tokens, and should be 

  true or not false

The same goes for "not", and "and". In other words, tokens made up of letters must be separated from other tokens made up of letters by at least one blank.

The fourth input line demonstrates that parentheses do not need blanks for separation.

Implement the constructor, hasNext(), and next(). The remove method has been provided. Don't change it. The provided main method exercises TokenIter; it prints the input line and every next token surrounded by square brackets, to show white space, or the lack thereof.

When properly implemented 

javac TokenIter.java
java TokenIter
should produce the following output: 
line: [ not (true or error false) @# $% ]
next token: [not]
next token: [(]
next token: [true]
next token: [or]
next token: [false]
next token: [)]

Notice that invalid tokens are skipped.

Stack and Queue

Implement Stack and Queue. See StackIF and QueueIF.

In2Post

Essentially, In2Post has a constructor and two methods, convertIn2Post() and evalPost(), that you need to implement.

Method convertIn2Post() converts a valid infix expression to the corresponding postfix expression. It uses a 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 convertIn2Post is described in the Lecture notes (L3: Queues), and in Prichard 7.4.

Method evalPost() evaluates the postfix expression produced by convertIn2Post() and produces the result. The working of evalPost() is described in the Lecture notes (L2: Stacks), and in Prichard 7.4.

When properly implemented, 

javac In2Post.java
java In2Post
should produce 
input line: []
postfix: []
result: 
input line: [true]
postfix: [true]
result: true
input line: [ (true or  (false))  ]
postfix: [true, false, or]
result: true
input line: [ true and false  ]
postfix: [true, false, and]
result: false
input line: [not not true]
postfix: [true, not, not]
result: true
input line: [true and (true or false)]
postfix: [true, true, false, or, and]
result: true

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 **ONLY**.

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