***** LLStack class *****

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(); } }

*** End of LLStack class ***

***** Queue Class ******

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(); } }

**** End of Queue Class ****

**** Stack class ****

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(); } }

***** End of stack class *****

*** Stack Test Class ****

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

s.push(input.charAt(i) + "");

System.out.println("The reversed string is: ");

while(!s.isEmpty()) {

System.out.print(s.pop());

}

System.out.println();

}

}

Question I (60 points) Download, compile and execute Stack.java. LLStack.java, Queue.java, and StackTest.java. 1. (30 points) Write a program BalancedParentheses.java. The algorithm for evaluating parentheses is as follows: (a) Remove all non-parentheses from a mathematical expression. (b) Given an opening parenthesis, i.e., a r. aor a {, push it onto the stack. (c) Given a closing parenthesis, pop an opening parenthesis from the stack (i) if the closing parenthesis and the opening parenthesis match, it is a successful match (ii) if the parentheses do not match, the expression is not balanced (iii) if the stack is empty, the expression is not balanced (d) if, at the end of the program, the stack is empty, then the expression is balanced. For example: [3+ (2-4) + ((a -b))] is balanced, while [3+2( and7+[a - b) ] are not balanced. The main program should contain a test method that will test your program. 2. (15 points) Write a program reverseStack to reverse the order of elements on stack s using a Queue. Develop a test method that checks how your program runs when given a stack of Integers. 3. (15 points) Implement a recursive method that for a positive integer returns a string with commas in the appropriate places, for example, putCommas(1234567) returns the string I ,234,567