Laboratory: Stacks

Summary: In this laboratory, you will have an opportunity to ground your understanding of stacks, particularly of the array-based implementation of stacks.

Required Code Files:

https://github.com/Grinnell-CSC207/linear

Preparation

a. Review the reading on linear structures.

b. Review the reading on stacks.

c. Fork and clone the repo at https://github.com/Grinnell-CSC207/linear

Exercises

Exercise 1: Basic Experiments

Read through LinkedStructureExpt.java and LinkedStackExpt. Summarize what the stack should look like at each step. (A piece of paper might help.) Note that the info method will print information on the stack (is it empty? is it full? what elements are in the stack) and the clear method will repeatedly call get until the stack is empty.

Run LinkedStackExpt and see if you get the output that you expect.

Exercise 2: A Wrapper Class

Skim through ReportingLinearStructure.java. Summarize the main approach of the class. What ideas from the class might you apply in other situations? (Pick at least one or two.)

Exercise 3: Helper Classes

You may note that the designers of LinkedStack.java made an interesting decision in their design of the iterators for linked stacks: Rather than using an anonymous inner class, they created a separate class.

a. Explain the role of the word “this” in the following implementation of the iterator method.

    @Override
    public Iterator<T> iterator()
    {
      return new LinkedStackIterator<T>(this);
    } // iterator()

b. Do you feel a named class for the iterator is a better or worse approach than using an anonymous inner class. Why?

c. It does not appear that LinkedStackIterator has any explicit approach for failing fast. Given that the remove method is not implemented, do such iterators need a fail-fast mechanism? Why or why not?

Exercise 4: A Faulty Implementation

The file ArrayBasedStack.java has a significant bug. Identify and correct that bug.

Exercise 5: Matching Parens

One useful application of stacks is matching things. For example, we can match the parens in a Scheme expression as follows:

Step through the characters in the expression
    When you encounter a left paren or left square bracket, push it
      on the stack
    When you encounter a right paren or right square bracket, pop
      an opening character off the stack.  If the two characters don't
      match (e.g., if you pop a left paren for a right square bracket),
      issue an error.
    If you encounter a right paren or square bracket an empty stack, that
      character is mismatched.
If the stack is not empty, there are unmatched left parents or brackets.

Implement this algorithm. (You might also add support for braces and angle brackets.) That is, write and experiment with a method, checkMatching(String str), that checks whether the parens, square brackets, and potentially other characters, match correctly.

For Those with Extra Time

Extra 1: Matching, Revisited

Revise your answer from the previous exercise to store the indices of matching symbols. That is, you will need to push both symbol and index. Use the indices to provide better error messages (e.g., you can say where the mismatch occurs in the string).

How can you store two kinds of values in stack? One option is to make it a stack of Objects, and alternately push Character and Integer objects. Another option is to create a simple class that groups a character and an integer.

Extra 2: Displaying Matching Parens

Extend your answer from the previous extra problem to provide a nice picture of the matching parens. For example, for each pair of matching parens, you might draw a line underneath, as in the following.

(oh (boy) (I am having) ((so) much) fun matching (parens))
    +---+
          +-----------+
	                 +--+
			+---------+
			                         +------+
+--------------------------------------------------------+