During this lab activity you will use pointers to write your own stack class mystack.java that manages a stack of char. To check that your implementation works correctly, you will modify an existing client program to work with a mystack object. Finally, you will use a mystack object to solve a new problem.

1. Implement a stack of char with pointers. To make sure the headings of your member functions have the same names and parameters as those in the mystack interface, use "mystack.java", the shell shown below. This class has the basic member functions for a stack (a constructor to initialize an empty stack of char, push and pop operations, a check that determines whether a stack is empty, and a destructor that returns memory for re-use) as well as some of the other member functions. Fill in "mystack.java" the implementation section on the back of this handout. Then copy the shell, "mystack.java" to your working directory and enter your code. Note that the assignment function and the copy constructor have already been written.

   //  mystack.java	 mystack class INTERFACE using pointers
   public class mystack
   {	
      public:
         mystack( );           // constructs empty stack
         mystack(mystack S); // copy constructor
         ~mystack( );          // destructor deallocates memory
         char top( ) const;    // returns top, no pop
         Boolean isEmpty( ) const;// test for no nodes
         int length( ) const;  // return number of elements
         void push(char item);// push char onto top
         void pop( );          // remove top and deallocate node
         void pop(char item); // retrieve top char and deallocate node
         void makeEmpty(  );   // make stack empty & deallocate memory
         mystack operator=(mystack S);  // assignment operator
      private:
         struct nodetype
         {
            char info;
            nodetype *next;
         };
         nodetype *mytop;	    // pointer to top of stack
   };
   
   //mystack.java mystack class  IMPLEMENTATION using pointers
   mystack::mystack( )  
   { 
      ...
   }
   mystack::mystack(mystack S)
   {
      // the shell contains this code
   }
   mystack::~mystack( )
   {
      ...
   }
   char mystack::top(  ) 
   {
      ...
   }
   Boolean mystack::isEmpty( ) 
   {
      ...
   }
   int mystack::length(  ) 
   {
      ...
   }
    void mystack::push( char item)
   {
      ...
   }
   void mystack::pop(  )
   {
      ...
   }
   void mystack::pop(char item)
   {
      ...
   }
   void mystack::makeEmpty(  )
   {
      ...
   }
   mystack mystack::operator=(mystack S)
   {
      // the shell contains this code  
   }
   

2. Test that your class works correctly by compiling, stackpal.java, a client program you may obtain from your teacher, that uses mystack objects to check whether a word is a palindrome.

3. Complete the function below and write a client program to test it. Use a mystack object in your solution.

   Boolean bracketsMatch(String str)
   // returns true if and only if str contains correctly matching 
   //     and non-overlapping brackets - (  )  [  ]  {  }
   // For example,	"[N(ov)(emb)er]1st" returns true
   //              "{Oc[t}ober2]3rd"   returns false
   {
      ...
   }
   

   Hint: Push opening symbols onto a stack of characters. When a closing symbol is found, pop the stack to see if the brackets match.

Bonus! Modify this second client program to check for correctly placed brackets in any java program. This is one of the many tasks the compiler performs as it checks for correct syntax.