1) Write a program to evaluate postfix expressions using a Stack. Use the same algorithm as presented in your slides. For example if the user input is: 3 2 + 4 *, then the output should show the contents of the stack after every operation and also the final result. Make your program interactive so the user can provide input. Use the java files below.

2) Create a class ArrayStack that implements the methods of a stack using an array. Assume that the max size of an array is 100 elements.

////Stack.java////

public class Stack { private java.util.ArrayList pool = new java.util.ArrayList(); public Stack() { } public Stack(int n) { pool.ensureCapacity(n); } public void clear() { pool.clear(); } public boolean isEmpty() { return pool.isEmpty(); } public Object topEl() { if (isEmpty()) throw new java.util.EmptyStackException(); return pool.get(pool.size()-1); } public Object pop() { if (isEmpty()) throw new java.util.EmptyStackException(); return pool.remove(pool.size()-1); } public void push(Object el) { pool.add(el); } public String toString() { return pool.toString(); } }

////LLStack.java////

public class LLStack { private java.util.LinkedList list = new java.util.LinkedList(); public LLStack() { } public void clear() { list.clear(); } public boolean isEmpty() { return list.isEmpty(); } public Object topEl() { if (isEmpty()) throw new java.util.EmptyStackException(); return list.getLast(); } public Object pop() { if (isEmpty()) throw new java.util.EmptyStackException(); return list.removeLast(); } public void push(Object el) { list.add(el); } public String toString() { return list.toString(); } } ////Queue.java////

public class Queue { private java.util.LinkedList list = new java.util.LinkedList(); public Queue() { } public void clear() { list.clear(); } public boolean isEmpty() { return list.isEmpty(); } public Object firstEl() { return list.getFirst(); } public Object dequeue() { return list.removeFirst(); } public void enqueue(Object el) { list.add(el); } public String toString() { return list.toString(); } } ////StacksTest.java////

import java.util.*;

public class StacksTest { public static void main(String[] args) { Stack s = new Stack(); s.push(new Integer(3)); s.push(new Integer(5)); s.push(new String("hi")); while(!s.isEmpty()) { System.out.print(s.pop() + " "); } s.clear(); //Empty the contents of the stack System.out.println(" Here's how I reverse a string: "); Scanner k = new Scanner(System.in); System.out.print("Enter a string> "); String input = k.nextLine(); for(int i = 0; i < input.length(); i++) s.push(input.charAt(i) + ""); System.out.println("The reversed string is: "); while(!s.isEmpty()) { System.out.print(s.pop()); } System.out.println(); } }