How to Solve the Enclosure Matching Assignment for Data Strcutures II

Intended Audience:

This is a tutorial for students taking Data Structures II (CSC 301) at DePaul University instructed by Proessor Tao Hou. This is intended to be a tutorial on how to properly solve the enclosure matching assignment, the first assignment in the class.

Supplies

Prerequisites:

Prior knowledge of loops, stacks, arrays, reading from text files, conditional statements, and strings is required in Java. In addition, Eclipse IDE must be set up on your machine with the algs4 package in your workspace, a package dedicated to assignments, and the test files provided by Professor Hou on D2L. Make sure you follow Professor Hou’s setup process to ensure that you can run code on the test files that he has provided for you. Make sure the new file that you create is named “Balanced.java” as instructed to you in the assignment instructions.

Enclosure Assignment Problem:

To see whether a left-enclosing character corresponds with a right-enclosing character, we need to see if they are properly closed. Some examples of closed are: (), ({}), ()[], etc. Some examples of not closed are: ([), (}), {[{}. Essentially, every time we run into a left enclosing character, the next enclosing character in the file should match with the left one. Print “yes” if all enclosing characters have a match and print “no” if otherwise.

Step 1: Importing Necessary Packages

To complete this assignment, you will need access to the following classes: Stack.java, In.java, and StdOut.java. Luckily, they are available in the algs4 package, so all we need to do is import each of the packages listed earlier. The image above shows the code to import all of the necessary classes.

Step 2: Reading Input From the Test File

To read input from an input file, all you need to do is put lines 9 and 10 from the image above into your main method.

Code Explanation:

The In object named “in” is created to store the input of the file that is passed through the main function’s “args” argument. When you press the “run” button, the main function will take the file that Professor Hou told you to implement within the “arguments” sections of the “run configurations” menu. Line 10 converts the input from the “in” object and calls the “readString()” method in order to turn all of the “in” object’s contents into one string.

Step 3: Create a Stack

Creating the stack is very simple. After importing the stack class, all you need to do is create an object of type stack. The image below shows line 11 as being the line of code used to create a stack from the algs4.stack class.

Step 4: Searching for a Left Enclosing Character

To search for a left enclosing character, all you need to do is iterate through every character in the string and see if it is either a left parenthesis, a left bracket, or a left curly brace.

Code Explanation:

On line 14, we start by creating a for loop that iterates through the “str” string. Recall that the “str” variable holds all of the contents of the input file as a string. Thus, the for loop iterates through every character in the string. Line 15 simply stores the current character that is being inspected during an iteration of the loop. Line 16 checks if the character that is currently being inspected is a left enclocing character. If it is, then line 17 executes and pushes the character onto the stack.

Step 5: Checking for a Right Enclosing Character

Since we are already iterating through the string within the for loop, we can simply insert an if statement within the loop to see if the character that is currently being checked is a right enclosing character. If it is, then we pop from the stack that contains the left enclosing character so we can compare both enclosing characters in a later step. Before popping, however, we have to check if the stack is empty. If it is, then the program automatically ends the loop. This is because if we try to pop from an empty stack then our program will crash. In addition, if the stack is empty when we encounter a right-enclosing character, that means no left-enclosing character was found before the right-enclosing character. So we end the loop as a means to end our program early and conclude that the file does not have all enclosing characters. We will work through what happens after the loop ends in a later step.

Code Explanation:

Line 20 is the if-statement that checks if the stack is not empty and if the current character is a right enclosing character. Line 21 simply pops from the stack that contains the left enclosing character and stores it in a variable named “leftElement.” We need to store the popped value in a variable so it can be compared to the right enclosing character, which is the next step of the algorithm.

Step 6: Comparing Left Enclosing Character With Right Enclosing Character

The last step of the algorithm is to check whether the latest left enclosing character that your program encountered matches with the latest right enclosing character. To do this efficiently, we will implement an if-statement that checks if the left enclosing character does not match with the right enclosing character. This is because if both the left and right enclosing characters do not match, then automatically the entire file cannot consist of all enclosed enclosing characters, so we exit the loop.

Code Explanation:

Lines 26-29 is one if-statement that checks if the “leftElement” (last left enclosing character pushed to the stack) does not match with the right enclosing character that was encountered during the current loop iteration. If the statement is true, meaning they do not match, then we exit from the loop with a break statement on line 30. Again, we end the loop early as a means to automatically conclude that not all enclosing characters have a match.

Step 7: Printing Yes or No

In steps 3-5, you checked if every single left-enclosing character had a matching right-enclosing character. Therefore, if every single enclosing character had a match, then the stack containing all of the left enclosing characters should be empty by the time the loop is done executing. If the stack is not empty, then that means the loop ended early and there are still left enclosing characters in the stack. Thus, we must write one last if statement to check if the stack is empty or not by the end of the loop’s execution.

Code Explanation:

Lines 35-38 are a simple if-else statement that allows the program to check whether the stack is empty or not by calling the “isEmpty()” method on the stack. If it is empty, then the file has matching enclosing characters, otherwise the stack is not empty and the file does not have all enclosing characters.

Step 8: Testing on First Test File

Run your code on the in1.txt file that Professor Hou provided to you on D2L. If you run it and your console looks like the image above, then your code was successful in completing the task.

Step 9: Testing on Second Test File

Change your input file to the in2.txt file that Professor Hou provided to you on D2L. If you run it and your console looks like the image below, then your code was successful in completing the task.