/*
   This program illustrates a typical use of linked lists: the implementation
of stacks.  Stacks are the central structures of many important algorithms.
A stack is a structure that can grow and shrink dynamically, but you can
only add elements to the front of the stack and delete elements also at
the front of the stack.  Stacks are said to have a LIFO or "last in first
out" behavior because elements are added to and deleted from the same end
of the stack.  The front of the stack is called the TOS or "top of stack 
pointer".

The following operations forms the stack "abstract data type":

push(x) : inserts a new element x to the top of the stack
pop() :   deletes and returns the top of the stack element
peek() :  returns the element on top of the stack, but does not delete it.
empty() : determines if the stack is empty.

We are going to implement this abstract description in two different ways,
first using an array, which means that the stack will have a fixed maximum
size, then use a list, which means that the stack can grow arbitrarily large.
Each implementation has its advantages.

We also use a construct called and "interface".  An interface is a
description of an abstract data type.  It contains the "header" or
prototype of methods that any class that "implements" the interface
must provide definitions for.  By using such an interface, we can
write our programs using stacks regardless of how they're implemented.
In older languages such as C/C++, interfaces where called "header
files".
*/

interface stack
{
    public void push(int x) throws Exception;
    public int pop() throws Exception;
    public int peek() throws Exception;
    public boolean empty();
}

// basic linked lists of integers
class cell
{
    int head;
    cell tail;
    cell(int h, cell t) {head=h; tail=t;}
}


/////// implementation of stacks using a fixed-length array.  This kind of
/////// stack will have a maximum size.

class arraystack implements stack
{
    private int[] A;  // array to hold stack elements
    private int tos;  // current top of the stack
    public arraystack(int n) // constructor initializes array of size n
    {
	A = new int[n]; 
	tos = -1;       // a tos value of -1 indicates an empty stack
    }   

    public boolean empty() { return tos == -1; }
   
    public void push(int x) throws Exception
    {
	// first check if max size of stack reached:
	if (tos >= A.length-1) throw new Exception("stack overflow");
	A[++tos] = x;  // same as tos=tos+1; A[tos]=x;
    }

    public int pop() throws Exception
    {
	// first check if stack is empty:
	if (tos<0) throw new Exception("stack underflow");
	return A[tos--];
    }

    public int peek() throws Exception
    {
	// first check if stack is empty:
	if (tos<0) throw new Exception("stack underflow");
	return A[tos];
    }

} //arraystack


/// linked list implementation
class liststack implements stack
{
    private cell tos = null; 
    public void push(int x) throws Exception
    {
        tos = new cell(x,tos);
    }

    public int pop() throws Exception
    {
        if (tos == null) throw new Exception("stack underflow");
        int x = tos.head;
	tos = tos.tail;
	return x;
    }
    public int peek() throws Exception
    {
        if (tos == null) throw new Exception("stack underflow");
	return tos.head;
    }
    public boolean empty()
    { return tos == null; }
}

// application : eval expressions in prefix syntax:

public class stacks
{

    public static int eval(String[] S) throws Exception
    {
	int i = S.length-1; // start at right end of array
	stack estack = new arraystack(S.length);
	while (i>=0)
	    {
		if (S[i].equals("+"))
		    {
			int a = estack.pop();
			int b = estack.pop();
			estack.push(a+b);
		    }
		else if (S[i].equals("-"))
		    {
			int a = estack.pop();
			int b = estack.pop();
			estack.push(a-b);
		    }
		else if (S[i].equals("*"))
		    {
			int a = estack.pop();
			int b = estack.pop();
			estack.push(a*b);
		    }
		else if (S[i].equals("/"))
		    {
			int a = estack.pop();
			int b = estack.pop();
			estack.push(a/b);
		    }
		else  // push number on stack
		    {
			int a = Integer.parseInt(S[i]);
			estack.push(a);
		    }
		i--;
	    }// while
	return estack.pop();
    } //eval

    public static void main(String[] args) throws Exception
    {

	String[] S = args[0].split(" ");
	int val = eval(S);
	System.out.println("evaluates to "+val);
	/*
	stack SA = new liststack();  // new arraystack(100); 
	SA.push(2);
	SA.push(4);
	SA.push(6);
	while (!SA.empty()) { System.out.println(SA.pop()); }
	*/
    } // main
}

/*
sample output:
> java stacks "- * 4 2 - 3 1"
evaluates to 6

because the expression is (4*2)-(3-1) in prefix or "polish" notation.
*/