CS 201: Data Structures (Spring 2017)
HW09: Code interpreter
Due: Monday, 05/15 at 22:00
1. Goals
To implement an array-based structure and get experience working with a large body of preexisting code.
2. Setup
This is a pair programming assignment. You will continue with your same partner (unless I have told you otherwise).
Download the starter files and unzip.
You may find it helpful to review the Javadocs for Scanner
, String
, and Character
classes when you do Step 3 (syntax checking).
3. Specification
Step 0: Checking out the starter code
This assignment is structured around modifying a relatively large, pre-existing code base (from the zip file). The program expressed in the code is a virtual machine (VM) simulator for a fake programming language. The code compiles and runs, with very limited capabilities, without any initial modification. So before you try writing any code of your own, you should first verify that you're starting from the right place.
-
Compile all of the code from
hw09.zip
except forDequeTester.java
.DequeTester.java
should not compile, but everything else should compile with no errors. The only errors inDequeTester.java
should be that the symbolCircularArrayDeque
was not found (since you haven't created it!).If you run into any problems with this code before you start modifying it (that is, if anything goes wrong in an unexpected way), your development environment probably doesn't match the "supported" environment; that is, the Carleton lab machines. Try doing these steps on lab machines instead of your own computer to isolate any problems. The most likely issue is that your version of Java is older than ours. Update your version from Oracle's website, or just use the lab computers.
-
Try running the
MainWindow
class as a Java application (that is, runjava MainWindow
on the command line). The VM Simulator window should appear. You should not get any error messages at this point. -
Open one of the given fake "programs" (that is, one of the files named
program-XXXX.avaj
in thefake-programs
subdirectory of the starter archive) by using theLoad
button.-
In the
Status Information
window, you should see a message like this:Syntax error in program-1.avaj: Syntax checking not implemented! Program not loaded.
This is normal: you will implement syntax checking in Step 2.
-
On the command line (where you typed in the
java
command to run the program), you should see an error message that says:Cannot instantiate CallStack. Method calls won't work. The CallStack class doesn't exist yet. (ClassNotFoundException)
This is normal: you will fix it in Step 3.
-
Note that in the rest of this assignment, you will only need to edit three files:
CircularArrayDeque.java
where you write your implementation of the Deque ADT,Program.java
in which you implement syntax checking, andCallStack.java
where you extend your implementation.
Step 1: Your own Deque implementation
In order to do the next step (syntax checking), you'll need an implementation of the Stack ADT. To make this a little more interesting, we're going to follow the same design as Java and build an implementation of the Deque ADT. The steps below provide some tips for writing this implementation:
-
Create a new class
CircularArrayDeque
that uses an array (not links!) to implement the includedDeque
interface. Your class should start withpublic class CircularArrayDeque<E> implements Deque<E>
to indicate that you're implementing a generic stack: it can store any type of object. -
You'll have an array as an instance variable in
CircularArrayDeque
. This array needs to hold generic objects. Unfortunately, Java makes it hard to construct generic arrays. Because of the way generics are actually implemented in the language, you can't sayE[] array = new E[10];
. (Try it: you'll see you get a compiler error!) Instead, you need to create an array ofObject
s and cast it to the generic type:@SuppressWarnings("unchecked") E[] tmp = (E[])new Object[10]; items = tmp;
Here, items is an instance variable of typeE[]
. You've created an array of objects, and then told the compiler to treat that array as an array of objects of typeE
. The@SuppressWarnings("unchecked")
is a way to tell the compiler that you don't want a warning about the cast from anObject
array to anE
array.Generally, you should only suppress warnings when you are very sure that there is not a better way to do what you're doing: the situation of creating a generic array is the only one I can remember where I've ever suppressed unchecked warnings.
You may wish to read Segment 2.7 of the textbook for more on this.
- As implied by its name, you should treat the array as circular in your deque implementation. You should look back at your reading or class notes on queue implementations if you've forgotten what this means.
-
When a client attempts to
getFirst()
,getLast()
,removeFirst()
, orremoveLast()
on an empty deque, throw aNoSuchElementException
using the following code:throw new NoSuchElementException();
You should importNoSuchElementException
first fromjava.util
. -
All of your methods in your implementation should run in O(1)
time in the average case, although the
add
methods may occasionally take more time due to increasing the capacity of the deque. - When you increase the size of your array, you should make an array that is a multiple of the current size (e.g., twice as long), not a constant amount bigger (e.g., not 10 items longer). Think about why this is more efficient: If you eventually store n items in the array, in Big Oh notation, how many calls does the former approach require versus the latter?
-
DequeTester
provides some tests of the methods you'll be writing. I encourage you to create the skeleton of your implementation first: just the method names with bodies that don't do anything or return some dummy value of an appropriate type. Then you should be able to compileDequeTester
. The tests aren't completely segmented into parts that should work with just one part of the code done, but you're welcome to modify them in any way that would be helpful. I encourage you at the very least to use them when debugging your methods or trying to decide if your deque is really working properly. - You may wish to write more tests, though you do not need to turn in your testing code this time.
addLast
, removeLast
, getLast
, and
isEmpty
. As such, as long as you can get one side of your deque
working (the back side), you will be able to continue with the rest of the
assignment and get most of the points. If you go this route, have
addFirst
, removeFirst
, and getFirst
throw UnsupportedOperationException
. If you are really stuck,
talk to me and I will supply you with a .class
file so you can
continue with Steps 2 and 3.
Step 2: Syntax checking
The goal of this part is to write a method that can read through the lines of a text file and determine whether it has properly matching parentheses, square brackets, and curly braces. You'll use the Deque implementation that you just wrote to properly parse the syntax of a fake "Java-like" program.
I say "Java-like" because the "programs" that we'll be using are mostly just
nonsense written in an extremely simplistic pseudocode version of Java. For
now, we're only going to pay attention to the nesting of the three types of
brackets, i.e., ()[]{}
, in these "programs."
-
Go into the
Program
class and edit thesyntaxCheck(Scanner)
method. Notice now that it currently just throws aSyntaxErrorException
. Modify the method so that it returnstrue
when the syntax is correct, and throws aSyntaxErrorException
otherwise. Note that if you throw an exception, you do not also need to return something at that point: the method will pass the exception to the method that called it, and that method will decide what to do. -
Important: the only thing you should edit in the
Program
class is thesyntaxCheck(Scanner)
method. Do not change any other code. -
In class back in Week 3, we talked about how you can use a Stack to check
for matching parentheses: this is your opportunity to implement that
algorithm. You'll need to use your deque implementation, and go through the
input character-by-character. You shouldn't use any stack or deque
implementation other than the one you just wrote. You can implement any
helper methods you want for
syntaxCheck(Scanner)
to call, but you shouldn't modify any other methods in this class that already exist. -
A
switch
statement might be helpful in structuring your code for this portion of the assignment, but it is not required. (Your textbook eschewsswitch
statements.) - You know how frustrating vague error messages are when you get them from the compiler or other programs? Well, now's your chance to be the change you want to see in the world! Make sure that the exceptions you throw contain helpful messages. The optional first argument to the exception constructor is a string containing the exception's message. Clearly identify in your exception the line number on which the error happened (keeping in mind that lines are traditionally counted starting from 1, not 0) and what the exact problem was. If the problem is that a bracket isn't closed, it's okay to just indicate the last line of the file as the problem.
Run
button. At this stage, "running" the program
simply results in all the lines of the first method being printed to the status
window.
Note: You must actually click the Run
button in order to run programs: just
loading the programs will not run them. On some operating systems, the run
button doesn't appear as button-like as load, but it is still a button.
Step 3: A call stack to simulate function calls
We will create a classCallStack
to simulate function calls.
-
Create a new class
CallStack
that extendsCircularArrayDeque<Method>
. Specifically, your class must have the following signature:public class CallStack extends CircularArrayDeque<Method>
This means thatCallStack
is a subclass of yourCircularArrayDeque
that only storesMethod
s (just like yourSortedLinkedList
only storedZooAnimal
s). -
Create a constructor for
CallStack
that takes aSimulationComponent
as an argument, and saves a reference to theSimulationComponent
as an instance variable. -
You'll actually be making this class behave like a stack, so you don't want
the user to be able to add to the front, remove from the front, or look at
the front (i.e.,
getFront
). Thus, override each of these methods and make them simply throw anUnsupportedOperationException
. This is a built-in Java exception in the packagejava.lang
. -
This stack should behave like your original deque implementation for the
remaining methods, except that when
Method
s are pushed to the stack, in addition to performingaddLast
(see below), you should call theaddMethodToGraphicalStack(Method)
method of yourSimulationComponent
instance, passing it theMethod
that was just added. Similarly, whenMethod
s are removed from the stack, you should call theremoveMethodFromGraphicalStack(Method)
method of yourSimulationComponent
in addition to peforming the pop. -
In a subclass, you can call a super class method using
super
. For instance, if I wanted to call theaddLast
method inCircularArrayDeque
inside ofCallStack
, I would writesuper.addLast()
. This can be a great way to avoid duplicating code. -
Change (override) any methods you need to in order to make
CallStack
behave correctly as a stack that holdsMethod
s and that adds or removes the relevant methods from theSimulationComponent
when they are added or removed from the stack, respectively. - Note that when making a subclass, you only have to override methods that you want to change. Thus, if any of your methods don't have to change, you don't have to—and indeed should not—write new versions of them. Step 3 actually requires very little code: you are simply delegating actions to other classes as appropriate.
Run
button to
run the programs.)
4. Code notes
-
You can make your own
.avaj
files and you can open mine in any text editor to see what's in them. - The call stack is how computers keep track of various method calls. Hopefully the visualization gives you a better understanding of how the computer keeps track of different methods, including when calling methods recursively.
-
Optional extra challenge: Change your
syntaxChecker(Scanner)
method to look for single-line comments (double slashes), and ignore the rest of a line if a single-line comment is found. The programsprogram-error-comment-1.avaj
andprogram-error-comment-2.avaj
are included to help you test this functionality. With only Part 2 of the homework they should not load properly because they have mismatched brackets inside of single-line comments. If the single-line comment code is working, the programs should load properly. - Even more challenge: If you are feeling very ambitious, you can also parse for multi-line comments, or make sure single- or multi-line comment tokens inside strings to be printed are ignored. This is likely very challenging.
5. Submission and grading
Submit to Moodle azip
archive containing:
CircularArrayDeque.java
(created in Step 1),Program.java
(modified in Step 2), andCallStack.java
(created in Step 3).
Follow the previously established guidelines. In particular, do not include any other files.
Assignment requirements
This is a partial list of the things that we'll be looking for when evaluating your work (in addition to style):
CircularArrayDeque.java
uses an array, treats it as "circular," and implements Deque.CallStack
extendsCircularArrayDeque
and avoids duplicating code.- The correct exceptions are thrown in the circumstances described in the assignment.
- Syntax checking correctly checks whether brackets are matched and displays helpful error messages, including indicating the line number of the problem and printing error messages that are helpful.
- Your code compiles without errors or warnings. In particular, there should not be any "uses unchecked or unsafe operations" warnings.
Grading
- Assignment requirements [20 points]
- Comments, style, and design [5 points]
This assignment modified from one designed by Andy Exley, Jadrian Miles, and Anna Rafferty.
Start early, have fun, and discuss questions on Moodle.