CS 200 P2

Converting infix expressions to postfix expressions, and evaluating postfix expressions

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 code.

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”, “^” “&”, “!”, “(”, “)”
Invalid tokens should be discarded. If the input line is e.g.: 
  true & ! (false ^ true)
the strings produced by subsequent calls to the next() method of a TokenIter should be: 
  "true", "&", "!", "(", "false", "^", "true", ")".
  1. ! means boolean NOT (highest precedence operator)
  2. & means boolean AND
  3. ^ means boolean EXCLUSIVE OR (lowest precedence operator)
    (true if exactly one of the operands is true)
Examples of valid input lines are: 
true

true false
true^false
true ^ false
      true      ^      false
! (   ! (true &    false))
  1. The first input line contains the simple logic expression "true".
  2. The second input line is empty and demonstrates that your program needs to handle empty inputs properly.
  3. The third demonstrates that adjacent alphabetic tokens must be separated by one or more spaces.
  4. The remaining lines show that spaces are allowed anywhere, (well, not inside the words "true" and "false") but are only required as specified in the previous item.
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: [ ! BAD (true ^ false) % truelybad]
next token: [!]
next token: [(]
next token: [true]
next token: [^]
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: alpha
push: beta
[alpha, beta]
peek: beta
[alpha, beta]
pop: beta
beta
[alpha]
pop: alpha
alpha

Queue

Implement Queue. When properly implemented, 
javac Queue.java
java Queue
should produce 
[gamma, delta]
gamma
delta

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 ^  false  ]
enqueue: true
push: ^
enqueue: false
pop: ^
enqueue: ^
postfix: [true, false, ^]
dequeue: true
push: true
dequeue: false
push: false
dequeue: ^
pop: false
pop: true
push: true
pop: true
result: true
input line: [! true]
push: !
enqueue: true
pop: !
enqueue: !
postfix: [true, !]
dequeue: true
push: true
dequeue: !
pop: true
push: false
pop: false
result: false
debug: false
input line: [true ^ true & false]
postfix: [true, true, false, &, ^]
result: true
input line: [true & (true ^ false)]
postfix: [true, true, false, ^, &]
result: true
input line: [! true]
postfix: [true, !]
result: false
input line: [! true ^ true]
postfix: [true, !, true, ^]
result: true
input line: [! (! true ^ false)]
postfix: [true, !, false, ^, !]
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.

The P2.jar file should have the *.java files in the top level directory and not in the src directory. jar files generated by Eclipse typically have source files in the src directory.

The directory structure of P2.jar should be as follows: 

    P2.jar
    |__ Stack.java
    |__ Queue.java
    |__ In2Post.java
    |__ TokenIter.java