← back to the schedule


MINI-LAB #2
Stacks




Reversing Strings

One simple use of stacks is to reverse the order of a collection of items. This Mini-Lab will give you a chance to practice with stacks by reversing the order of strings.

  • Begin by downloading the file StackMiniLab.zip. Unzip that file, and import the project into BlueJ.
  • Add code to main to complete the following exercises. In each case, you should solve the problem using a stack, not by using a cleverly indexed for-loop.
    • 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 a 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 Mini-Lab 2.

EVALUATION

Mini-lab #2 is worth 15 points. This project will be submitted individually. The following items describe the criteria we will use to evaluate your mini-lab:

  • Correct implementation of reversing strings (part 1, by words) 4 pts.
  • Correct implementation of reversing strings (part 2, by character) 4 pts.
  • Correct implementation of nested parenthesis 5 pts.
  • Adding appropriate amount of comments to the code (your name and description of the class, method description, and so on) 1 pt.
  • Proper organization of your code (indentation, clarity, cleverness) 1 pts.

Have fun! And if you have any questions remember my email, my office hours, and the collaboration center are here for you!



← back to the schedule