← back to the schedule


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.

Implement a Stack Class

Create a project for this mini-lab and download the following files:

Make a copy of your previous K_SimpleQueueTester.java file, calling it K_SimpleStackTester.java, and edit it to change the class name, the class documentation, and all references to enqueue and dequeue, which should now be push and pop.

Implement the methods in K_ALStack, testing them using your K_SimpleStackTester class. Note that 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 to you includes an overriding implementation of the toString method that returns a string showing the current state of the stack.

Simple Programs Using Stacks

The rest of 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.

In this section you will be adding code to the K_SimpleStackExamples class you downloaded above.

Reversing Strings

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

  • Add code to the K_SimpleStackExamples class 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 in the K_SimpleStackExamples class 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.

Clean and Refactor

Follow this link to clean and refactor your comments and code.

Submission

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!



← back to the schedule