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 main method in 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.

  • Read another sentence from the user, and 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.
  • (If you have time) Redo the previous two exercises by using exceptions to determine whether the stack is empty, rather than using the isEmpty() method.

---

Nested Parentheses

Another good use of stacks is to check for balanced matching items, like parentheses.

• Add code to the same main method as before to complete the following problem that uses a stack to test for balanced parentheses, braces, and brackets.
• Read an expression from the keyboard or from command-line arguments as a long string. Scan the characters in the string for parenthetical punctuation marks, in other words "(", ")", "[", "]", "{", 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. 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 "{". Use a stack of Character objects to implement your program.

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!