/*
* Compilation: javac ResizingArrayStack.java
* Execution: java ResizingArrayStack < input.text
* Data files:http://algs4.cs.princeton.edu/13stacks/tobe.txt
*
* Algorithm 1.1 is an implementation of our Stack API that resizes the array, allows 
* clients to make stacks for any type of data, and supports client use of foreach to iterate 
* through the stack items in LIFO order. This implementation is based on Java language 
* nuances involving Iterator and Iterable, but there is no need to study those nuances 
* in detail, as the code itself is not complicated and can be used as a template for other 
* collection implementations.
*
*/

import java.util.Iterator;
import java.util.NoSuchElementException;
public class ResizingArrayStack<T> implements Iterable<T>
{
	private T[] a; // array of items
	private int N; // number of elements on stack

	// create an empty stack
	public ResizingArrayStack() {
	    a = (T[]) new Object[2];
	}

	public boolean isEmpty() {
	    return N == 0;
	}

	public int size() {
	    return N;
	}
	// resize the underlying array holding the elements
	private void resize(int capacity) {
	    assert capacity >= N;
		T[] temp = (T[]) new Object[capacity];
		for (int i=0; i<N; i++)
		{
			temp[i] = a[i];
		}

		a = temp;
	}

	// push a new item onto the stack
	public void push(T item) {
	    if (N == a.length)
	    {
			resize(2*a.length);  // double size of array if necessary
	    }

		a[N++] = item; // add item
	}

	// delete and return the item most recently added
	public T pop() {
	    if (isEmpty())
	    {
			throw new RuntimeException("Stack underflow error");
	    }
		T item = a[N-1];
		a[N-1] = null;
		N--;

		// shrink size of array if necessary
		if (N > 0 && N == a.length/4) // when a.length = 0,N = a.length/4 = 0
		{
			resize(a.length/2);
		}

		return item;
		
	}
	// impelemts Interface Iterable<T> 's method
	public Iterator<T> iterator() {
	    return new ReverseArrayIterator();
	}

	// an iterator,doesn't implement remove() since it's optional
    private class ReverseArrayIterator implements Iterator<T>
    {
		private int i;

		public ReverseArrayIterator() {
		    i = N;
		}

		public boolean hasNext() {
		    return i > 0;
		}
		public void remove() {
		    throw new UnsupportedOperationException();
		}
		public T next() {
		    if (!hasNext())
		    {
				throw new NoSuchElementException();
		    }

			return a[--i];
		}
    }
	public static void main(String[] args) 
	{
		ResizingArrayStack<String> s = new ResizingArrayStack<String>();
        while (!StdIn.isEmpty()) {
            String item = StdIn.readString();
            if (!item.equals("-")) s.push(item);
            else if (!s.isEmpty()) StdOut.print(s.pop() + " ");
        }
        StdOut.println("(" + s.size() + " left on stack)");
	}
}

public class  FixedCapacityStack<T>
{
	private T[] a;
	private int N;

	public FixedCapacityStack(int capacity) {
		a = (T[])new Object[capacity];
		N = 0;
	}

	public void push(T item) {
		a[N++] = item;
	}

	public T pop() {
		return a[--N];	    
	}

	public boolean isEmpty() {
	    return N == 0;
	}

	public int size() {
	    return N;
	}

	// test client
	public static void main(String[] args) 
	{
		FixedCapacityStack<String> s = new FixedCapacityStack<String>(100);

		while (!StdIn.isEmpty())
		{
			String in = StdIn.readString();

			if (!in.equals("-"))
			{
				s.push(in);
				
			}else if (!s.isEmpty())
			{
				System.out.println(s.pop());
			}
		}

		if (!s.isEmpty())
		{
			System.out.println("there has " + s.size() + "left in the stack");
		}
	}
}

public class  FixedCapacityStackOfStrings
{
	private String[] a;
	private int N;

	public FixedCapacityStackOfStrings(int capacity) {
		a = new String[capacity];
		N = 0;
	}

	public void push(String item) {
		a[N++] = item;
	}

	public String pop() {
		return a[--N];	    
	}

	public boolean isEmpty() {
	    return N == 0;
	}

	public int size() {
	    return N;
	}

	// test client
	public static void main(String[] args) 
	{
		FixedCapacityStackOfStrings s = new FixedCapacityStackOfStrings(100);

		while (!StdIn.isEmpty())
		{
			String in = StdIn.readString();

			if (!in.equals("-"))
			{
				s.push(in);
				
			}else if (!s.isEmpty())
			{
				System.out.println(s.pop());
			}
		}

		if (!s.isEmpty())
		{
			System.out.println("there has " + s.size() + "left in the stack");
		}
	}
}
/* java FixedCapacityStackOfStrings < tobe.txt*/

//  Dijkstra’s two-stack arithmetic expression-evaluation algorithm
public class Evaluate 
{	
	public static void main(String[] args) 
	{      // 这里的表达式是全括号表达式，为了简单起见
		Stack<String> operators = new Stack<String>();
		Stack<Double> operands = new Stack<Double>();
		int count = 0;  // count Of left Parenthesis
		while (!StdIn.isEmpty())
		{			
			String s = StdIn.readString();
			if (s.equals("("))
			{
				count++;
			}else if (s.equals("+"))
			{
				operators.push(s);
			}else if (s.equals("-"))
			{
				operators.push(s);
			}else if (s.equals("/"))
			{
				operators.push(s);
			}else if (s.equals("*"))
			{
				operators.push(s);
			}else if (s.equals("sqrt"))
			{
				operators.push(s);
			}else if (s.equals(")"))
			{
				if (count-- == 0)
				{
					return;
				}else {
					double val = operands.pop();
					String op = operators.pop();
					if (op.equals("+"))
					{
						operands.push(val + operands.pop());
					}else if (op.equals("-"))
					{
						operands.push(operands.pop() - val);
					}else if (op.equals("/"))
					{
						operands.push(operands.pop() / val);
					}else if (op.equals("*"))
					{
						operands.push(operands.pop() * val);
					}else if (op.equals("sqrt"))
					{
							operands.push(Math.sqrt(val));
					}
				}
				
			}else {
			    operands.push(Double.parseDouble(s));
			}
		}

		System.out.println(operands.pop());
	}
}

import java.util.Iterator;
import java.util.NoSuchElementException;
public class Stack<E> implements Iterable<E> 
{
	private int size; // size of the stack
	private Node first; // top of stack
	
	// helper linked list class
	private class Node
	{
		private E element;
		private Node next;
	}
    // create an empty stack
	public Stack() {
	    size = 0;
		first = null;
		assert check();
	}
    // Is the stack empty?
	public boolean isEmpty() {
	    return (first == null);
	}
    // return the number of items in the stack
	public int size() {
	    return size;
	}

     /*
	 Add the element to the stack.
	 */
	 public void push(E element) {
	     Node oldfirst = first;
		 first = new Node();
		 first.element = element;
		 first.next = oldfirst;
		 size++;
		 assert check();
	 }
     /*
	 Delete and return the item most recently added to the stack.
	 @throws java.util.NoSuchElementException if the stack is Empty
	 */

	 public E pop() {
	     if (isEmpty())
	     {
			 throw new NoSuchElementException("Stack underflow");
	     }
		 E element = first.element;  // save  element to return 
		 first = first.next;   // delete first node
		 size--;
		 assert check();
		 return element; // return the saved element
	 }

	 /*
	 Return the element most recently added to the stack.
	 @throws java.util.NoSuchElementException if stack is Empty.
	 */
	 public E peek() {
	     if (isEmpty())
	     {
			 throw new NoSuchElementException("Stack underflow");
	     }
		 return first.element;
	 }

    /*
	 Return string representation.
	*/

	public String toString() {
	    StringBuilder sb = new StringBuilder();
		for (E element: this)
		{
			sb.append(element + "-");
		}
		return sb.toString();
	}

	/* check internal invariants */
	private boolean check() {
	    if (size == 0)
	    {
			if (first != null)
			{
				return false;
			}
	    }

		return true;
	}
	/* return an iterator to the stack that iterates
	 through the elemets in LIFO order */
	public Iterator<E> iterator() {
	    return new ListIterator();
	}
	// an iterator,doesn't implement remove() since it's optional
	private class ListIterator implements Iterator<E> {
	    private Node current = first;
		public boolean hasNext() {
		    return current != null;
		}

		public void remove() {
		    throw new UnsupportedOperationException();
		}

		public E next() {
		    if (!hasNext()) {
			   throw new NoSuchElementException(); 
			}
			E element = current.element;
			current = current.next;

			return element;
		}
	}

	public static void main(String[] args) 
	{
		Stack<String> s = new Stack<String>();
		while (!StdIn.isEmpty())
		{
			String element = StdIn.readString();
			if (!element.equals("-"))
			{
				s.push(element);
			}else if(!s.isEmpty()) {
				StdOut.print(s.pop() + " ");
			}
		}

		StdOut.println("(" + s.size() + "left on stack)");
	}
}