CS 200, Fall 2015
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 evaluating 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:

You need to work on the following codes.

TokenIter

You need to build an iterator TokenIter, that scans an input line character by character and produces Strings (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 blank, 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 BAD (true or false) && notgood ]
next token: [not]
next token: [(]
next token: [true]
next token: [or]
next token: [false]
next token: [)]

Notice that invalid tokens are skipped.

Stack

Implement Stack. When properly implemented, 
javac Stack.java
java Stack
should produce 
push: not
push: true
[not, true]
peek: true
[not, true]
pop: true
true
[not]
pop: not
not

Queue

Implement Queue. When properly implemented, 
javac Queue.java
java Queue
should produce 
[not, true]
not
true

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 
Testing In2Post, debug: true
input line: []
postfix: []
result: 
input line: [ true or  false  ]
enqueue: true
push: or
enqueue: false
pop: or
enqueue: or
postfix: [true, false, or]
dequeue: true
push: true
dequeue: false
push: false
dequeue: or
pop: false
pop: true
push: true
pop: true
result: true
input line: [not true]
push: not
enqueue: true
pop: not
enqueue: not
postfix: [true, not]
dequeue: true
push: true
dequeue: not
pop: true
push: false
pop: false
result: false
debug: false
input line: [true and true or false]
postfix: [true, true, and, false, or]
result: true
input line: [true and (true or false)]
postfix: [true, true, false, or, and]
result: true
input line: [not true]
postfix: [true, not]
result: false
input line: [not true or true]
postfix: [true, not, true, or]
result: true
input line: [not (not true or false)]
postfix: [true, not, false, or, not]
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.