Lab: 18 - Stacks

Assigned

Wednesday, 4 October 2023

OBJECTIVE

The following links will demonstrate -using a visualization- how a Stack works using an Array Implementation and a Linked List Implementation.

The goal for today’s lab is to write a simple application that uses the stack methods in Java’s generic LinkedList class. The application allows the user to type in a string and checks that the parentheses, brackets, and braces that occur in that string are correctly balanced and properly nested.

Background

A string that may contain parentheses, brackets, and/or braces is balanced if it has the same number of left and right parentheses, the same number of left and right brackets, and the same number of left and right braces. These characters are correctly nested if each right-hand parenthesis, bracket, or brace can be paired with a left-hand parenthesis, bracket, or brace that precedes it and matches its shape, in such a way that the only parentheses, brackets, and braces that occur between the paired characters are similarly paired (within the enclosed string).

For example, the string "(a [(b c) d]" is not balanced, because it has two left parentheses and only one right parenthesis, and the string "(a [b c)]" is not correctly nested because the parentheses enclose a string containing an unpaired left bracket. But "(a [{b c} (d e)])" is both balanced and correctly nested.

One conventional method for determining that a string is balanced and correctly nested is to draw arcs above the string connecting the paired left and right characters. If there is a way to draw the arcs so that they do not cross and connect characters that match in shape, leaving no parentheses, brackets, or braces unpaired, then the test succeeds.

This pencil-and-paper method provides the basis for the algorithm that we’ll implement today. The idea is to traverse the string from left to right. Whenever we find a left parenthesis, left bracket, or left brace, we’ll “start an arc” by pushing that character onto a stack. The arc will be terminated when we find the matching character later in the string, at which point we’ll pop it off the stack. The “last-in, first-out” property of stacks will guarantee that we cannot pop anything off the stack until we have successfully paired every parenthesis, bracket, or brace that occurs between the pushing of the arc-starting character onto the stack and the popping of it from the stack.

Stack: LinkedList Implementation

Use the LinkedList generic class. The type of data stored in each node/element will be a Character, e.g., LinkedList<Character> stack (note that this is capitalized as the reference object rather than the primitive char) Note: In Java, you could also use the Stack class, e.g., Stack<Character> stack

Getting Started

1. In Eclipse, open a new project for this application. Create a BalanceChecker.java file and write the header and documentation (though not yet the body) for a checkBalance method that determines whether a given string is balanced and correctly nested with respect to parentheses, brackets, and braces.
2. When you eventually implement it (consider the pencil-and-paper method described above), you’ll want the checkBalance method to push characters onto a stack and eventually pop them off again. This stack could either be created once, in the BalanceChecker constructor, stored in a field of the BalanceChecker object, and re-used for every call to checkBalance, or it could be created inside each call to checkBalance and stored in a local variable of that method. What are tradeoffs between these two ways for creating the stack? (You may do either one. The design choice is up to you!!)

Exercises

The code that implements checkBalance could encounter several kinds of problems.

• First, when we encounter, say, a right bracket in the string and pop the stack, we might find that the character we popped is a left parenthesis rather than a left bracket. What would this imply about the given string?
• Second, when we encounter, say, a right brace in the string, and try to pop the stack, we might find that the stack is empty. (In this case, the pop method throws an exception.) What would this imply about the given string?
• Third, we might reach the end of the string and find that the stack still has some characters in it that were pushed early on and have not yet been popped. What would this imply about the given string?

1. (2 points) Bearing all these possibilities in mind, implement the checkBalance method. Use the switch statement (see BJP - Appendix C pag. 1184 or Switch - Java tutorials) when matching a right parenthesis, bracket, or brace with a character popped from the stack. Note than characters other than parentheses, brackets, and braces need not be pushed into the stack.
   • It might be a good idea for the checkBalance method to ensure that the stack is empty before it returns a value. (This is essential if you are storing the stack in a field of an BalanceChecker object and reusing it in every call to checkBalance —you don’t want cruft left over from one call still to be in the stack when the next call begins.) Save and compile BalanceChecker.java.
2. (1 point) Devise some JUnit tests. Include some cases in which the bracketing symbols are balanced and correctly nested, and some in which they are not. For each of the possible kinds of error described in the exercises above, include at least one test case that illustrates an error of that kind.
3. (1 point) Create a BalanceCheckerTester.java file with a main method that will invoke the checkBalance method on a few sample strings and report its findings to the user (use informative user-friendly messages). Compile and run BalanceCheckerTester and interpret the output to confirm or refute the hypothesis that your implementation handles them all correctly. For imbalanced or incorrectly nested strings, check your program with the following test cases: "(a[b)c]", "(a[b(c)]", and "[a(b(c))d]]".

Note: Change the type of object. Use a Stack instead of a LinkedList. What changes do you have to do in your code?

Lab Submission

You will submit your files via Gradescope by the end of the week. Please submit the source files, and JUnit class.

I strongly recommend that each student keep a copy of the lab. Therefore, don’t forget to share the files/folder with your lab partner!

Remember: Write your code anticipating errors and print user-friendly error messages, all your public methods should be well documented (use Javadoc comments). Please include comments or organize your code and report in a way that will help the grader to find the answer to the exercises or posted questions.

For those with extra time

1. Modify the program so that it also checks to make sure that “angle brackets,” as represented by the less-than and greater-than signs, are also balanced and correctly nested in strings, with the added constraints that within every pair of angle brackets there must be a vertical bar character, |, and that both the string between the less-than sign and the vertical bar and the string between the vertical bar and the greater-than sign must be balanced and correctly nested strings. Vertical should only appear within the angle brackets as in < … | … >. Test your program to confirm that <(ab)|<c|[d(ef)]>> is balanced and correctly nested.