Computer Science 210
Data Structures

Fall 2018, Siena College

Home     Syllabus     Schedule     Examples     Style Guide

You may work alone or with a partner on this assignment. However, in order to make sure you learn the material and are well-prepared for the exams, you should work through non-coding problems on your own before discussing them with your partner, should you choose to work with someone. Also, be sure every programming task is a team effort. In particular, the "you do these and I'll do these" approach is sure to leave you unprepared for the exams.

All GitHub repositories must be created with all group members having write access and all group member names specified in the README.md file by 4:00 PM, Monday, November 12, 2018. This applies to those who choose to work alone as well!

There is a significant amount of work to be done here, and you are sure to have questions. It will be difficult if not impossible to complete the assignment if you wait until the last minute. A slow and steady approach will be much more effective.

Getting Set Up

You will receive an email with the link to follow to set up your GitHub repository for this problem set (ps5-yourgitname). One member of the group should follow the link to set up the repository on GitHub. Other group members will receive a subsequent email with a link to follow that will grant them the rights to clone the repository and commit and push changes to the origin on GitHub.

More Lists

When implementing some methods of lists, it can be tempting when creating new lists to improve efficieny by having lists that contain some of the same values share list nodes. For example, consider the following (very efficient, but problematic) implementation of a method to clone a SimpleLinkedList.

  public SimpleLinkedList<E> clone() {

     SimpleLinkedList<E> newList = new SimpleLinkedList<E>();
     newList.head = head;
     return newList;
  }

Consider the following code snip:

   SimpleLinkedList<Integer> a = new SimpleLinkedList<Integer>();
   a.add(3);
   a.add(17);
   SimpleLinkedList<Integer> b = a.clone();
   b.add(2, 19);
   for (int x: a) {
      System.out.println(x);
   }

While it would be a significant amount of work to have SimpleLinkedList implement the entire List interface, some of the methods are not that difficult to implement. We have already done a few earlier this semester.

Let's add another.

Linear Structures Questions

Java's Deque Interface

Bailey's structure package includes multiple implementations of both stacks and queues. The Java API has class java.util.Stack, but it is no longer recommended for use.

We mentioned briefly in class the idea of a deque, a "double ended queue", which provides the ability to add or remove values efficiently at either end of the structure. The Java API includes an interface java.util.Deque, which is implemented by a few Java API classes, that we can use when we need either a stack or a queue.

The essential operations of a deque are addFirst, addLast, removeFirst, and removeLast. When using the deque as a queue, the methods add and remove correspond to the "enqueue" and "dequeue" operations, and are aliases for the addLast and removeFirst method. The methods when using the deque as a stack are the standard push and pop, which are aliases for addFirst and removeFirst.

For each of the fundamental underlying data structures we used when considering stack and queue implementations, the array list, the singly-linked list, the circular list, and the doubly-linked list, answer the following questions:

Practice with a Stack

Tiny PostScript Interpreter

This portion will be graded as a programming project, worth a total of 40 points.

PostScript is a stack-based programming language often used by printers. When you print a PostScript file, the printer executes the instructions to form the image that will ultimately get printed on the page. At the heart of PostScript is an operand stack. When a PostScript command is encountered that requires some extra information, such as an "add" operation that would require the two numbers to add together, PostScript pops two operands from the stack, adds them, then pushes the result back onto the stack. We be implementing an interpreter for a very small subset of PostScript, focusing on arithmetic operations and a few related stack manipulation operators.

To specify an arithmetic expression which we'd like to evaluate with PostScript, we need to write that expression in postfix notation, where the operands are listedn before the operator.

For example, 2 + 3 becomes 2 3 +

There are three primary ways to represent an arithmetic expression:

• infix notation: (2 + 3) * 4 - 5
• postfix notation: 2 3 + 4 * 5 -
• prefix notation: - * + 2 3 4 5

In general, to convert an infix expression to postfix notation:

1. Write the expression fully parenthesized.
2. Recursively move operators after operands, dropping parentheses when done.

For example:

X * Y + Z * W
becomes
(X * Y) + (Z * W)
which becomes
(X Y *) (Z W *) +
which becomes
X Y * Z W * +

Note: in postfix notation, parentheses are no longer needed to enforce order of operations.

For PostScript, the actual operators are replaced by tokens, so the expression above would be computed by this PostScript program:

2 3 add 4 mul 5 sub

Then if we want to see our answer, which will be the lone value on the stack at the end, the PostScript token pstack can be used:

2 3 add 4 mul 5 sub pstack

which would result in the output:

15.0

Your task is to develop a complete interpreter for a subset of PostScript. It should be developed in the main method of a class called TinyPostScript. Your program should print nothing (no prompts, no "welcome to TinyPostScript" or anything like that) except the output of pstack commands and error messages. When an error message is printed, the program should terminate immediately.

The operators your program will need to handle are the following:

add

pop two values from the operand stack, add them together, and push the result.

sub

pop two values from the operand stack, subtract the first one popped from the second one popped, and push the result.

mul

pop two values from the operand stack, multiply them together, and push the result.

div

pop two values from the operand stack, divide the second one popped by the first one popped, and push the result.

pop

pop and discard a value from the operand stack.

exch

exchange the positions of the top two values on the operand stack.

dup

duplicate the value at the top of the operand stack, so that it is on the top of the stack twice.

pstack

print the contents of the operand stack to the output, with the values from top to bottom, one per line.

quit

exit the interpreter.

When your interpreter reads a number, it simply pushes that value onto the operand stack.

If your interpreter reads anything that is not a number or one of the supported operations listed above, it should print a message "Invalid token." and exit immediately.

If in the execution of any operation listed above, a value is needed from the stack but the stack is empty, it should print a message "Stack underflow." and exit immediately.

If your input Scanner runs out of input, your interpreter should also exit.

For testing, you might want to run your program from the command prompt instead of directly within BlueJ, so you can redirect your input from a .ps file. This would allow you to test without having to type in all of your PostScript tokens over and over in the terminal window. No code changes are needed to make this happen, you just need to run from your operating system's command prompt (Terminal on a Mac, Git Bash or the Command Prompt on Windows) and use input redirection. For example, the file test1.ps in your starter repository contains the same PostScript we saw above:

2 3 add 4 mul 5 sub pstack

You can run it at the command line as follows:

java TinyPostScript < test1.ps

and the output should be 15.0.

Your program will be tested using this capability and your output will need to match precisely with the expected output to pass the tests. A few more tests (.ps files) and their expected output (corresponding .out files) are in your repository.

Submitting

Please answer questions that require a text response in the README.md file of your repository. You may submit the memory diagram electronically as a file pushed to your repository or in hard copy. Only one submission per group is needed.

Your submission requires that all required code deliverables are committed and pushed to the master for your repository's origin on GitHub. That's it! If you see everything you intend to submit when you visit your repository's page on GitHub, you're set.

Grading

This assignment is worth 95 points, which are distributed as follows: