You can grab the stencil code from this GitHub Classroom link. Be sure to follow the Java Stencil setup guide for instructions on how to do this.
Refer to the GitHub guide for instructions on how to use git. Make sure you push your code regularly to back it up!
In general, lists are a flexible and valuable data structure for maintaining linear order among items. In practice, however, there are different orderings themselves that are useful in different situations. Here are two examples:
Let’s look at the differences in how lists are used in these settings.
Consider this example: Assume the restaurant has two meals waiting to be prepared:
toPrepare = [Meal("Dan", "impossible turkey sandwich"),
Meal("Sebastian", "possible turkey sandwich")]
Discuss with your partner:
Consider this example: Assume you are browsing the CS200 website. You started on the homepage, then went to the lectures page, then to the notes for lecture 14. When you are done with lecture 14, you hit the back button on your browser and then visit lecture 15. The browser uses a list to maintain which pages you came from so that it can retrieve previous pages when you hit the back button.
If we were to think about this as a list, we could write it as:
cameFromPages = [lec14, lectures, home]
// hit the back button
cameFromPages = ___________
// click on lecture 15
cameFromPages = ___________
1. Fill in the blank lines with the content of the cameFromPages list after each user action.
2. State a more general rule about where to place items in the cameFrompages list: where are new pages inserted? Where does pressing the back button take pages from?
Fill in the following table to summarize what we have observed about these two uses of lists:
| Restaurant | Back Button | |
| Where are new items added (front or end)? | ||
| Where is the next item to process (front or end)? | ||
| Where are items deleted from (front or end)? |
These examples represent two fundamental types of data structures:
While stacks and queues are both forms of lists, their usage patterns are sufficiently common that computer scientists and programmers give them their own names, including names of the core operations on them. Java, like many programming languages, provides versions of these built-in (we’re giving you the links here for reference – you don’t need them right now).
Side Note: Why is `Queue` an interface and `Stack` a class?
Because we’ve given you an introductory view of Queues as based on lists here, whereas they are actually richer in practice. We’ll return to this later in the course.
Now let’s look at one particular way to use queues that we’ll use in class soon, as part of learning about graphs.
While regular queues are used to process requests/issues/etc in the order that they arrive (add to the end, take from the front), in many settings we want a variation that considers items in order of priority. Think of a hospital, for example, patients are treated in order of urgency, with arrival time as a secondary criterion. This situation needs what we call a Priority Queue.
In this part of the lab, you’ll learn to work with Java’s built-in PriorityQueue class, which implements the Queue interface.
What determines the priority among objects? If our objects are just numbers, we can use the natural ordering of numbers. Here’s the definition of a basic priority queue on numbers:
import java.util.PriorityQueue;
PriorityQueue<Integer> numsLowToHigh = new PriorityQueue<Integer>();
More interesting cases are when the objects either do not inherently have an ordering or we want to use a non-default ordering. In this case, we define a Java Comparator, which is an object that defines how to compare or order other objects.
A comparator is a method that takes two objects of the type to be compared and returns an integer indicating the relationship between the arguments:
Recent versions of Java have added a notation for defining small functions like the lambdas you may have seen in other languages. We can use this to define comparators.
Let’s look at two examples of how we can use comparators:
Example 1: largest integer first
import java.util.Comparator;
// order numbers decreasing
Comparator<Integer> numHigher = (int1, int2) -> {
return Integer.compare(int1, int2) * -1;
};
Here, int1 and int2 are the parameters of a lambda function. The body of the lambda is in the curly braces. Inside the lambda, we use a built-in compare method on Integers that returns a negative number when the first number is smaller than the second, a positive number when the first is larger, and 0 if they are equal. To prioritize the second number, we multiply that result by -1.
PriorityQueue<Integer> numsHightoLow = new PriorityQueue<Integer>(numHigher);
When comparing two elements, the priority queue will give higher priority to those elements that come earlier according to the comparator (so if the comparator called on itm1 and itm2 returns a negative number, itm1 will have higher priority than itm2).
Example 2: prioritize shorter strings
// order strings by length
Comparator<String> stringShorter = (str1, str2) -> {
return Integer.compare(str1.length(), str2.length());
};
PriorityQueue<String> stringsByLength = new PriorityQueue<String>(stringShorter);
The stencil code has a class called PQ.java. Use the PriorityQueue method add to add items to each of the queues defined above, then print out the queue to make sure you are getting the expected order in each one.
Use the printPQ method to print out your PriorityQueues throughout the lab. Not doing this will print the PriorityQueue in a representation you do not need to understand yet.
Checkpoint!: Call over a TA to review your work.
The CIT has decided to implement a system in order to prepare lab spaces for CS Lab. They’ve already implemented a class MeetingTime that represents a meeting time given a DayOfWeek enum and a starting time (using int to represent 24-hour time), and a class CSLab that holds a MeetingTime and the course code of the CS class. All of these classes are in the stencil.
An enum is a type in Java used to enumerate constants. For example, if you needed constants for directions, you could define and use an enum as follows:
enum Direction {
NORTH, SOUTH, EAST, WEST
}
public Direction opposite(Direction ofDirection) {
if (ofDirection == Direction.NORTH) {
return Direction.SOUTH;
}
...
}
In the main method of PQ, write a Comparator called labsByCode that orders CSLabs by course code so they can prepare labs for lower-level courses before upper-level ones. Check your comparator by using it to create a PriorityQueue, adding items and printing out the queue to check the ordering.
Implement a comparator labsByTime that orders CSLabs by proximity to the current MeetingTime.
For example, if you define now to be Wednesday 16:00 with the following comparator:
MeetingTime now = new MeetingTime(DayOfWeek.WEDNESDAY, 16);
Comparator<CSLab> labsByTime = (lab1, lab2) -> {
//Fill in the rest here!
};
The Priority Queue usinglabsByTime would have the following order:
You might find it helpful to write in the MeetingTime class an hoursUntil method that takes in a MeetingTime and returns an int for the number of hours from this MeetingTime to the next.
The ordinal() method will be helpful here! It will return an Integer that represents the order of the enum value in its initial declaration. For example, DayOfWeek.MONDAY.ordinal() returns 1 and DayOfWeek.THURSDAY.ordinal() returns 4
Checkpoint!: Call over a TA to review your work.
For this section of the lab you will be creating a parenthesis checker. You will be able to take a String and print a message indicating wether it’s valid or invalid.
Take a look at these examples:
"{[}", "hello)", "{", "{hello()[]{)}}", "({hello)}", "{]""{}", "hello()", "(hello)", "{(hello)}", "((hello)hello)", "[]{}hello"Turn and talk: Take a minute to explain to your partner(s) or the person sitting next to you why each of the invalid strings above is invalid. Then, explain why each valid string is valid. Try to define a generalizable rule as to what makes a string valid.
For a string to be considered valid, each opening parenthesis '(' must have a corresponding closing parenthesis ')'. Also, the parentheses must be closed in the correct order.
Pairs of parentheses can be any of: "()", "[]" or "{}"
Write your own version of 5 invalid strings and 5 valid strings. You will be using these to test your parenthesis checker.
Checkpoint!: Call over a TA to review your work and check your understanding.
If the string you’re trying to process has an invalid number or order of parentheses, you will have to indicate this by throwing an exception.
So, what is an exception?
Imagine the following scenario:
Somewhere in the code, this unexpected behavior from the user (i.e. including an invalid character in the username or password) was reported and then handled accordingly, in this case by prompting you to re-enter your credentials. Programmers use exceptions to report invalid behaviors, and then use exception handlers to deal with these behaviors instead of letting their program crash.
In Java we say that we report these exceptions by “throwing” them:
throw new NameOfSomeExceptionClass();
How do we deal with exceptions?
In Java, exceptions are handled with a try/catch block. The try block executes first and contains any code that may potentially throw an exception. If an exception is thrown in the try block and that type of exception is caught in the catch block, the catch block will execute.
The generalized form for the try/catch block:
try {
<code that could throw an exception or keep running>
} catch <Exception e> {
<code to run if an exception is thrown> //called "handling the exception"
}
Basically, a try/catch block “tries” some code (e.g. program tries logging in with the given username and password), and if that doesn’t work, it jumps to the catch section where the error is handled (e.g. user is prompted to correctly enter their username and password).
Take a look at the exception we’ve defined for you in the ParenthesisException class. It comes with a default error message and a method to get the error details.
Exceptions and exception handling exist in most mainstream programming languages, though sometimes by slightly different names. For example, later in the course we’ll see that Python has different keywords for its error handling (try/except instead of try/catch).
For any of these languages the general idea remains the same. If a function encounters a situation that was not expected, it does not try to return a normal value. Instead it announces that a problem occured by “throwing” or “raising” an exception.
In Java it’s important to know if a particular function/method can cause an exception, so that the programmer can be ready to handle that exception when using that function/method. Many other languages, like Python, don’t make you specify that information, which can sometimes result in the programmer being caught off-guard by unexpected exceptions.
Many modern languages, including Java, allow you to create custom exception classes, so that the program can distinguish between different kinds of invalid behavior and respond appropriately. This is what we’ve done in the provided ParenthesisException class.
For now, you don’t need to worry about creating an exception class or understanding what goes on under the hood. We just want you to get familiar with how we use them.
Fill out the try block in the MainParenthesis class to appropriately handle our parenthesis check if it fails. We want to be validating the first command line argument (args) passed in.
Remember that the try block contains the code we want to run that might throw the exception we want to catch. In this case, ParenthesisExceptionStencil.
Note that we created a ParenthesisChecker object in our main method. So, what method in ParenthesisChecker.java file throws a ParenthesisExceptionStencil exception?
How is the computer supposed to know what characters are corresponding opening and closing parentheses to each other? For example, how will our program know that "(" and ")" “match”?
We need a way to store which opening parenthesis corresponds to which closing parenthesis. In other words, we need some sort of data structure that, given an opening parenthesis character (i.e. "(", "[", "{"), can return which character is its corresponding closing parenthesis.
What data structure do we know that can store matching pairs that we can access in constant runtime?
In our ParenthesisChecker class, populate the parentheses_match hashmap to store the “pairs” of parentheses.
static {
your_hashmap.put(key1, val1);
your_hashmap.put(key2, val2);
}
Hint: What is KV data type of parenthesis_match? Use single quotes instead of double!
Checkpoint!: Call over a TA to review your work.
Our goal is to create an algorithm that checks if parentheses in a string are correctly closed. We want to make sure each opening parenthesis has a corresponding closing one. The most recent open parenthesis needs to be “closed” in order for a previous one to be correctly closed as well.
Decide which data structure is best in this case. Think back to what you know about Stacks and Queues. How are they different? When should we pick one over the other? LIFO (Last In First Out) vs. FIFO (First In First Out)?
Be ready to explain to the TA why one data structure is more appropiate in this case than the other.
Once you have done this, click the drop down to see our answer and be ready to explain why we chose the data structure listed.
We chose to use a stack. Why might we have picked this data structure?
In our ParenthesisChecker class, initialize the stack we instantiated in the constructor.
While reading through the steps with your partner, you may have now realized that, in order to validate a string, we need a way to move from left to right through the string and keep track of all of the parentheses that were opened and closed.
As we move from left to right in the string, if we encounter an open parenthesis, we store that in our data structure.
If we encounter a closing parenthesis, we can use our hashmap to check if it matches the parenthesis most recently opened. If it does, that opening parenthesis has been closed, and we may remove that from our data structure. If it doesn’t, or there are no stored opening parentheses, the string is invalid.
We iterate through the whole string until we reach the end. At this point, we need to check if all the parentheses that were open have been closed. How might we do this? How does our chosen data structure, the Stack, help us in this algorithm?
Implement the above algorithm in the parenthesisChecker() method to take in a string and iterate from left to right through the string to determine its validity.
As you can see from the stencil, we gave you most of the logic for this algorithm. Try to understand what each case is covering.
Once you are done with the TODO items, run the code with different strings trying to cover all edge cases.
Remember how we wanted to validate the string inputted as the 1st command-line argument? In order to input command line arguments, you can go to Run > Edit Configurations and type in the string to validate in Program arguments.
Final Checkpoint!: Congratulations! You completed this week’s lab. Call a TA over to get checked off.
Please let us know if you find any mistakes, inconsistencies, or confusing language in this or any other CSCI0200 document by filling out the anonymous feedback form.