Computer Science 210
Data Structures

Fall 2018, Siena College

Problem Set 5
Due: 10:00 AM, Tuesday, November 20, 2018

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 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>();
   SimpleLinkedList<Integer> b = a.clone();
   b.add(2, 19);
   for (int x: a) {

Question 1: What does the above code snip print? (1 point)

Question 2: Draw a memory diagram showing the state of the variables and objects in existence right before it executes the enhanced for loop. (5 points)

Question 3: Explain briefly why this would cause you concern as a programmer using the SimpleLinkedList class. (2 points)

Question 4: We saw that the Java API classes ArrayList, Vector, and LinkedList all implement the java.util.List interface. If we wanted our SimpleLinkedList class to be interchangeable with those, we could also have it implement List. What methods would need to be added to our SimpleLinkedList class to satisfy the List interface? (3 points)

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.

Practice Program: Implement the subList method, as described by the java.util.List interface in the SimpleLinkedList class. Include a complete set of tests in a main method of another class called SubListTester. For full credit, your implementation must be as efficient as possible in its construction of the new list, but must not suffer from the problem that the clone method above had. Hint: avoid method calls on the new list as you construct it. Build the entire structure directly. (12 points)

Linear Structures Questions

Question 5: Bailey Problem 10.8, p. 246. The add/remove operations can be interleaved in any valid order. (3 points)

Question 6: Bailey Problem 10.10, p. 246. The add/remove operations can be interleaved in any valid order. (3 points)

Question 7: Bailey Problem 10.12, p. 246. (3 points)

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:

Question 8: How you would "orient" the data structure so the four required deque operations addFirst, addLast, removeFirst, and removeLast are most efficient? (2 points)

Question 9: What is the time complexity (Big O) of each of those operations for each of the underlying data structures. Explain each briefly. (8 points)

Practice with a Stack

Practice Program: Write a program in a file that uses a stack to keep track of integer values read from the keyboard in this unusual way. If 0 is entered, the input loop terminates. If the stack is empty, the number entered is pushed. The number is also pushed if its sign matches the sign of the number at the top of the stack. However, if the sign does not match, then the number "cancels out" the number of the opposite sign at the top of the stack. Once a 0 is entered, the program either prints out the message "All negatives and positives cancelled" if the stack is empty, or prints the message "Uncancelled values" followed by the contents of the stack otherwise.

Use a stack declared as an instance of the java.util.Deque interface, but construct a java.util.LinkedList. Only use the push, pop and peek operations of the Deque. (10 points)

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:

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
(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:


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:

pop two values from the operand stack, add them together, and push the result.
pop two values from the operand stack, subtract the first one popped from the second one popped, and push the result.
pop two values from the operand stack, multiply them together, and push the result.
pop two values from the operand stack, divide the second one popped by the first one popped, and push the result.
pop and discard a value from the operand stack.
exchange the positions of the top two values on the operand stack.
duplicate the value at the top of the operand stack, so that it is on the top of the stack twice.
print the contents of the operand stack to the output, with the values from top to bottom, one per line.
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 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 <

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.


Please answer questions that require a text response in the 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.


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

> FeatureValueScore
Question 1 1
Question 2 5
Question 3 2
Question 4 3
SimpleLinkedList subList correctness 7
subList tests in SubListTester 5
Question 5 (10.8) 3
Question 6 (10.10) 3
Question 7 (10.12) 3
Question 8 2
Question 9 8
PositiveAndNegative correctness 10
TinyPostScript correctness 25
Design and style 5
Documentation 10
Git commit frequency and message quality 3
Total 95