Homework 3

Post date: Jul 13, 2009 8:20:59 PM

Administrative

Deadlines:

    • With a 10% bonus: Friday, July 17, 2009, at 11:59pm.
    • Last deadline: Monday, July 20, 2009, at 11:59pm.
    • No late submission will be accepted.

All students must adhere to Academic Code of Conduct. You are welcome to brainstorm ideas with your fellow students, but you are not allowed to share code.

Description

Here is a quick rundown of a list of functions you need to implement or functions of interest. The provided functions may help you with the functions you need to implement, so you should study them.

    • DoublyLinkedList.java
      • (provided) public void Prepend(T item)
      • (provided) public void Append(T item)
      • (10 pts) public T RemoveFirst()
      • (10 pts) public T RemoveLast()
    • Queue.java
      • (20 pts) public class Queue<T>
    • QueueTest.java
      • (10 pts) public void testFIFO()
    • Stack.java
      • (20 pts) public class Stack<T>
    • StackTest.java
      • (10 pts) public void testLIFO()
    • ForthInterpreterMain.java
      • (30 pts) public class ForthInterpreterMain
    • BinarySearchTreeSet.java
      • (20 pts) public Iterator<T> iterator()
      • (provided) public boolean ContainsIter(T item)
      • (provided) public boolean ContainsRecurs(Node<T> curr, T item)
      • (10 pts) public void Add(T item)
      • (20 pts) public T Remove(T item)
      • (10 pts) public void Union(Iterable<T> xs)
      • (10 pts) public void Difference(Iterable<T> xs)
      • (20 pts) public void Intersect(Membership<T> xs)

For a total of 200 points.

If you cannot finish this homework, try to concentrate on what you do know how to do. Try not to work on many incomplete functions for partial credit.

Additional Instructions for Forth Interpreter

Forth is a programming language for manipulating and performing computation on stack. In this assignment, you'll implement a simplified Forth interpreter.

Basic Syntax

A Forth program is read from standard input (Eclipse console) as a sequence of tokens separated by whitespace (space, tab, new line, etc). Each token can either be an integer or the name of an operator. If the token is an integer, it is pushed on the stack. If the token is an operator, then some computation is performed. In particular, there is a special operator "." (just the period) which pops an item from the stack and prints it to the standard output.

Since the program operands are in stack order, "0 1 . ." will first print "1" then "0".

Operators

You will need to implement the following operators.

    • "." (provided): pop the stack and print it to standard output.
    • "dup": duplicate once what's on the top of the stack, e.g. "1 dup . ." prints "1" twice.
    • "drop": discard one item from the top of the stack, e.g. "0 1 drop ." prints "0".
    • "swap": exchange the top two items on the stack, e.g. "0 1 swap . ." prints "0" then "1".
    • "recall": takes one argument n that is >= 0; replaces the argument with a copy of the nth value down the stack. E.g. "5 4 3 2 1 0 3 recall ." prints "3" with the numbers "0" "1" "2" "3" "4" "5" still left on the stack, from top to bottom.
    • Binary arithmetic operators "+" "-" "*" "/" "mod" which pops two operands off the stack then pushes the result back on the stack, e.g. "1 2 + ." prints "3".
    • "negate": performs unary negation on the operand on top of the stack, e.g. "1 negate ." prints "-1"
    • "abs": computes the absolute value, e.g. "-1 abs ." prints "1"
    • "min" and "max": pops two operands off the stack and then pushes either one back, depending on which is smaller (for the "min" operator") or larger (for the "max" operator).

Running the program

ForthInterpreterMain.java hooks the standard input to a scanner, which converts a sequence of characters to a sequence of input tokens. The code for doing that is provided for you, as well as the ability to push integer tokens on the stack and the implementation of the "." operator. Before you can run this program, you need to implement Stack.java. Once this is done, you should be able to enter some numbers and use "." to see that integer tokens are printed in LIFO order.

Once you implement more operators, you can test them similarly, using "." to observe the output.

Example

If you enter "3 dup * ." (push 3 to the stack, duplicate 3, multiply 3 by 3, and print the result) you'd see "9" printed as the result. If you enter "3 dup * 4 dup * + ." ("3 dup *" becomes 9, which is saved to the stack; "4 dup *" becomes 16, which is saved to the stack; add 9 and 16, and print the result), you'd see "25" printed as the result.