Assignment 6

The Assignment

http://www2.hawaii.edu/~tp_250/ICS211/Fall03/hw06.htm

Comments

Stack

Note that this program/method takes a String to balance. You may want to specify a constructor that takes a String/StringBuffer/char[] of pairs of characters to match:

BracketMatcher matcher = new BracketMatcher("<>\"\"(){}");
boolean correct = matcher.isBalanced(myText);

You can implement your own Stack, or use one of the book's implementations. You can also use java.util.Stack for your stack implementation. However, limit yourself to calling only those methods defined in the book's Stack ADT: push, pop, peek, isEmpty, size, popAll/removeAll.

You will need to decide what to do with improperly nested delimiters. For instance, in "{[}]" all open marks have a closing mark. However, they are improperly nested and should probably be either "{}[]" or "{[]}". It is pretty standard practice to require that delimiters be properly nested to be considered balanced. (It's easier to implement this way too.) But when you make a decision like this, you need to add a short comment on it in your documentation.

Deque (or dequeue or deq)

The assignment says to write a reference-based implementation. I recommend you use a doubly-linked list, which uses double-ended Nodes. (That is, each node has both a setNext and a setPrev method.)

Remember in deques you need to differentiate which end you are affecting. That is, dequeue and enqueue methods become dequeueFront and dequeueBack and enqueueFront and enqueueBack. You will also need a peekFront and a peekBack method.

Grading

This assignment will be out of 10 points. You will get points for the following:

2.5 - Your program compiles without error

1.5 - Good documentation and follows ICS Java Coding Standards.

See this note on documenting your code. Use descriptive variable names, use internal capitalization for names, consistently indent and space code, etc.

2.0 - Parantheses checker

Uses a stack to balance open and closing delimiters.

0.5 - Checker is general

It is somehow possible to specify or customize the pairs of delimiters that your checker balances (either in a constructor, or by adding or removing pairs of delimiters.)

2.0 - Deque

A working reference-based implementation of a deque. Items can be enqueued or dequeued from either end.

0.5 - Concatanation

Either using a separate, general method or else in your test code using existing methods, you concatanate 3 deques.

1 - Testing

You test your code. This includes things such as dequeing an empty list, as well as adding and removing things normally a few times. Check each of your methods to see if they work, and try calling them with bad input to see if they fail properly. For your delimiter balancer, give it a string with the delimiters balanced and another string without them balanced. See if it can really tell the difference like it's supposed to.