Stack MINI-LAB

---

Getting Started

Read through the K_Stack interface, a simplified version of the standard Java Stack class that specifies five methods: size, isEmpty, push, pop, and peekNext. Become familiar with the descriptions of these methods, especially how they differ from the methods for KQueue.

Create a project for this mini-lab and download the K_Stack interface, the skeleton test driver K_SimpleStackTester.java, and ValidatedInputReader.java, which is a class used by K_SimpleStackTester.. (A test driver is a small program whose sole purpose is to run a series of isolated tests, without the full context or complexity of a true application.) You will be completing the incomplete K_ALStack class that is partially provided in partialK_ALStack.java. This class implements the K_Stack interface using a java.util.ArrayList internally. Download that file, change the filename to K_ALStack.java to match the name of the class, and then complete the unimplemented methods.

The K_ALStack class extends Object as well as implementing K_Stack, so it inherits methods such as toString and equals (and hashCode) unless it redefines them. The partial implementation provided above includes an overriding implementation of the toString method that returns a string showing the current state of the stack.

---

Testing and Using Stacks

This Mini-Lab will give you a chance to practice with stacks by reversing the order of strings and checking for balanced parentheses In each case, you should solve the problem using a stack, not by using a cleverly indexed for-loop.

Reversing Strings

One simple use of stacks is to reverse the order of a collection of items.

• Add code to the test driver to complete the following tasks.
  • Read a sentence from the user, and print out the words in reverse order: the sentence "Hi There!" would be printed as "There! Hi".

    Hint: Don't forget about the split method of the String class.

  • Then print out the letters of each word in reverse order, while keeping the order of the words intact: the sentence "Hi There!" would be printed as "iH !erehT". Use a stack of Character objects to store individual characters.

---

Nested Parentheses

Another good use of stacks is to check for balanced matching items, such as the parenthetical punctuation marks, "(", ")", "[", "]", "{", and "}".

• Write a method that takes an input string and uses a stack to test it for balanced parentheses, braces, and brackets. It should print the original string and report to the user whether or not the expression was properly parenthesized. In order for an expression to be parenthesized properly, each left parenthesis, brace, or bracket must be matched with a right parenthesis, brace, or bracket, respectively, at the appropriate nesting level.

  A straight-forward way to implement this is to push left punctuation marks onto a stack of Character objects. When you encounter right punctuation marks, check them against what is at the top of the stack. Errors occur when punctuation marks are not nested correctly. For example, the expressions:

  • {A (B ((C) D (E)) F) (G) } and {A [B (C) [D] {E} F] (G) } are correct.
  • {A [B} ] and {A [B] are incorrect.

  In the third expression, the inner "[" requires a matching "]" before you encounter the "}". In the final expression, there is no matching "}" for the "{".

• Test your method by calling it from the main method with a variety of hard-coded test strings that contain a mix of parenthetical punctuation marks. Your tests should include correct and incorrect strings. (Don't forget to test it with an empty string ("").)
• (If you have time) Redo this exercise using exceptions to determine whether the stack is empty, rather than using the isEmpty() method.

Submit your completed program through Kit, under Stack Mini-Lab.

Have fun! And if you have any questions remember I am available through email, Teams, and my office hours. And don't forget the Collaboration Center, which is a great place to work and ask questions too!