Assignment 6: Linear Structures

The standard array-based implementation of queues uses two pointers: one to keep track of where to put the next value (we'll call that back) and one to keep track of where to get the least recently added value (we'll call that front). For example, after adding the strings "alpha", "beta", and "gamma" to an array-based queue, we might end up with the following.

front            back
  |               |
  |       +-------+
  |       |
  v       v
+---+---+---+---+---+
| * | * | * | / | / |
+-|-+-|-+-|-+---+---+
  |   |   +---------------------------+
  |   |                               |
  |   +--------------+                |
  |                  |                |
  v                  v                v
  a l p h a \0 . . . b e t a \0 . . . g a m m a \0 . . .

That's a bit cumbersome to draw, so we'll use the usual shorthand of putting the values “in” the array.

front            back
  |               |
  |               |  
  |               |
  v               v
+-------+-------+-------+-------+-------+
| alpha | beta  | gamma |       |       |
+-------+-------+-------+-------+-------+

After we add and remove a few elements (say we add another gamma and an alpha, and then remove the initial alpha and beta), we'll have “empty space” at the beginning of the array

front            back
  |               +---------------+
  |                               |  
  +---------------+               |
                  v               v
+-------+-------+-------+-------+-------+
|       |       | gamma | gamma | alpha |
+-------+-------+-------+-------+-------+

What happens if we add another element, say "delta"? In the naive implementation of array-based queues, we've run out of space. But we should be able to wrap around to the front of the array.

front            back 
  |  +------------+
  |  |            
  +--|------------+ 
  v--+            v 
+-------+-------+-------+-------+-------+
| delta |       | gamma | gamma | alpha |
+-------+-------+-------+-------+-------+

Implement and test array-based queues with wrapping. You may find it useful to start with the ArrayBasedQueue class from the Tao of Java's linear structures repository.

Write a procedure that takes a string as input and prints out a picture that shows the nesting. For each pair of matched symbols, you should draw a line underneath, as in the following picture.

{oh [boy] (I am having) (<so> much) fun matching `symbols'}
    [---]
          (-----------)
                         <-->
                        (---------)
                                                 `-------'
{---------------------------------------------------------}

You should support parentheses, square brackets, curley braces, angle brackets, and matched single quotation marks. You may also choose to support double-quotation marks, although they can be a bit troublesome.

If the symbols do not match, you can do whatever you think is appropriate to indicate the failure to match. For examlpe

(Hello (world)
       (-----)
( < - UNMATCHED

(Hello (world))}  ]
       (-----)
(-------------)
               } <- UNMATCHED
                  ] <- UNMATCHED

To solve this problem, you will need to store the indices of the matching symbols on the stack. That is, you will need to push both symbol and index. How can you store two kinds of values in stack? One option is to make it a stack of general Objects, and alternately push Character and Integer objects. Another option is to create a simple class that groups a character and an integer.

Implement a calculator that uses Reverse Polish Notation (RPN). You should support input of real numbers and the following operations:

Although it doesn't have exactly the same interface, you can experiment with the command-line RPN calculator dc to help understand these operations. (I don't think dc provides s.)

In implementing your calculator, do your best to use the model-view-controller (MVC) pattern. You may need to Google that pattern.