An input line consists of many characters (numbers, letters, blanks, etc) including a number of different kinds of parentheses, for example ( [ { ) ] }. Write a Java program that will determine if the parentheses are balanced (ie match). For example, ( ( [ ] ) ) [ ] { [ ] } is balanced (all parentheses match) but this is not: ( [ { } ( ) ).

Your assignment is to input (or hard code) some Strings containing a number of brackets (with or without spaces in betweenthats up to you; you can use the 2 examples above just assign them to 2 different String variables) and use the ArrayStack to solve the problem. Use the ArrayStack class code and supply the missing code.

As you process the input start producing an output string containing each symbol examined. If you encounter a problem add that symbol to the output string and a message describing the problem.

In the seminar we will have a brief discussion about the algorithm you use to solve this problem and the data sets needed to adequately test code.

import java.util.Arrays;

/**

* An array implementation of a stack in which the

* bottom of the stack is fixed at index 0.

*

*/

public class ArrayStack implements StackADT

{

private final static int DEFAULT_CAPACITY = 100;

private int top;

private T[] stack;

// Creates an empty stack using the default capacity.

public ArrayStack()

{

this(DEFAULT_CAPACITY);

}

// Creates an empty stack using the specified capacity.

public ArrayStack(int initialCapacity)

{

top = 0;

stack = (T[])(new Object[initialCapacity]);

}

/* Adds the specified element to the top of this stack, expanding

* the capacity of the array if necessary.

*/

public void push(T element)

{

if (size() == stack.length)

expandCapacity();

stack[top] = element;

top++;

}

/**

* Creates a new array to store the contents of this stack with

* twice the capacity of the old one.

*/

private void expandCapacity()

{

stack = Arrays.copyOf(stack, stack.length * 2);

}

/**

* Removes the element at the top of this stack and returns a

* reference to it.

*/

public T pop() throws EmptyCollectionException

{

if (isEmpty())

throw new EmptyCollectionException("stack");

top--;

T result = stack[top];

stack[top] = null;

return result;

}

/**

* Returns a reference to the element at the top of this stack.

* The element is not removed from the stack.

*/

public T peek() throws EmptyCollectionException

{

if (isEmpty())

throw new EmptyCollectionException("stack");

return stack[top-1];

}

}

------------

public class EmptyCollectionException extends RuntimeException

{

// Sets up this exception with an appropriate message.

public EmptyCollectionException(String collection)

{

super("The " + collection + " is empty.");

}

}