/*     Help for lab 8.
 
  There was some confusion as to how to use the data structures for
stacks that I gave you.  I first gave two examples of how to implement
a stack of integers, using arrays and cell-lists.  This was to provide
a general example of stacks.  The actual stack class I gave you to
help you finish lab 8 has a slightly different structure.  You are not
required to use these classes to finish the assignment.  You may, for
example, edit the sample code for stacks using arrays (but instead of
storing ints, you will need to have arrays pointing to structures that
contain multiple pieces of information).

Please take some time to understand the classes below, if you wish to use
them.  The class sstack implements an abstract data type that offers you
the push, pop, peek and isempty methods.  What exactly do we push onto the 
stack?  We have to push a structure that records both the character, '[',
'(' or '{', and the position in the string that it was found, so we can
report the error precisely.  These two pieces of information are captured
inside scell objects.  That is, given:

sstack T = new sstack();  // start with an empty stack.

T.push('[',0); // will add a new scell on the stack, recording both
the char '[' and the position value 0.

scell N = T.pop();  // popping the stack returns a pointer to an scell object.

// at this point, N.symbol refers to the char stored in the object, and
// N.position refers to the position value.  peek is the same as pop except
// it doesn't remove the cell from the stack.

In the sample main program, I write code to further illustrate the usage
of these structures.  A string is called a "palindrome" if it's the same
when reversed.  "noon" and "bob" are examples of palindromes.  The 
program checks if a string is a palindrome, and if not, at which characters
there's a problem.  A stack is not necessary for solving this problem,
but I will use one anyway in order to show how it can be used.
*/


class scell
{
    public final char symbol;
    public final int position;
    public final scell tail;
    public scell(char s, int p, scell t)
    { symbol=s; position=p; tail=t; }
} 

class sstack  // symbolic stack class
{
    private scell tos = null; // top of stack pointer

    public void push(char s, int p)  // add cell in front
    {
	tos = new scell(s,p,tos);
    }

    // the following function tries to delete the top cell from the stack.
    // it returns null if the stack is empty, or the cell that was deleted.
    public scell pop()
    {
	if (tos == null) return null;
	scell oldtos = tos;
	tos = tos.tail;
	return oldtos;
    }

    // the following function returns the cell at the top of the stack
    // without popping it
    public scell peek() { return tos; }

    public boolean isempty() { return tos==null; }
} // sstack


public class stacksample
{
    // function to check if a string is a palindrome.  it returns a
    // string message.

    public static String palindrome(String S)
    {
        int n = S.length();      // length of string
	int i;                   // for indexing into string
	String answer = "it is a palindrome";  // default return value
        sstack T = new sstack(); // empty stack
        // loop to push all chars on stack
	for(i=0;i<n;i++) { T.push(S.charAt(i),i); }
        // loop to pop stack, checking if they match string characters
	for(i=0;i<n;i++)
	 {
	     scell N = T.pop();
	     if (N.symbol != S.charAt(i))  // not a palindrome
	      {
		  answer = "characters "+i+" and "+N.position+" don't match";
		  i = n; // setting i=n forces for-loop to stop.
	      }	
	 } // for loop to pop stack
	return answer;
    } //palindrome

    public static void main(String[] args)
    {
	String p = palindrome(args[0]);
	System.out.println(p);
    } // main
}
/* sample output:
> java stacksample "noon"
it is a palindrome
> java stacksample "asbta"
characters 1 and 3 don't match
*/