/** * * @param component type */ public interface Stack { /** * Adds the given element to the top of stack. * @param e element to push on stack. * @throws IllegalStateException if stack is full */ public void push(E e); /** * Removes and returns element on top of stack. * @return element on top of stack * @throws EmptyStackException if stack empty */ public E pop(); /** * Returns, but does not remove, element on top of stack. * @return element on top of stack * @throws EmptyStackException if stack empty */ public E peek(); /** * Returns true if stack is empty. * @return true if stack empty */ public boolean empty(); }

Write the generic class[1] ArrayStack that implements the given Stack interface. Include the methods push, pop, peek and empty. Implement the stack using an array. All the stack elements go into the array. The top of the stack is the last element in the array.

For example, the following array is a stack:

9

3

4

2

6

1

The element at the top of the stack is 1. If you call the pop method, the 1 will be removed. If you call the push method, providing 5 as a parameter, then 5 will be added into the next available array slot.

[1] Recall that a generic class does not assume anything about the type of the data. So, your class will be ArrayStack, where E is a type variable representing the type of data in the stack.

If the array is full, then push throws an exception. If the array is empty, then pop throws an exception.

PART II: Test Your Stack

Write a test method that does the following:

1- Read a string entered by the user

2- Traverse the string and push each character onto the stack

3- After all characters are on the stack, write a loop that pops a character from the stack and prints that character until the stack is empty.

If your stack is correct, then the string the user enters will be printed backwards.

PART III: Matching Parentheses

Write a program that takes a string of parentheses, curly-braces and brackets and determines if the parentheses, curly-braces and brackets all match correctly. Two symbols match if there is a closing symbol for every open symbol. The symbols must also be properly nested.

For example, [(([{()}]))] is a properly nested string with matching symbols.

For example, [{]} has matching symbolsbut not properly nested.

For example, ({} has properly nested symbolsbut not matching symbols.

Heres the algorithm you must follow:

Traverse the string of symbols

Every time you encounter an open symbol, push it onto the stack

Every time you encounter a closed symbol, pop a symbol from the stack

If the popped open symbol does not match the closed symbol,

the string is not valid

If the stack is empty when you complete the string traversal, the string is valid

Otherwise, the string is not valid.

You can treat a string like an array of characters by using the String classs charAt() method. Just provide the index of the character you want as a parameter and the method will return the character. For example, the following prints the first character in the string named s:

System.out.println(s.charAt(0));

Note that this method returns a char, not a string.

The String class has a length() method that returns the number of characters in the string.

PART IV: Palindrome

Use an algorithm similar to the one from PART III to determine whether an input string is a palindrome. A palindrome is a sequence of characters that reads the same forwards as backwards. For example:

was it a car or a cat i saw

or my personal favorite:

go hang a salami im a lasagna hog

Assume all letters are lower-case and the string includes no punctuation. The string will include spaces, which your program should ignore.