1) 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 [, a ( or 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( and { 7 + [ a b} ] are not balanced.

2) Write a program to reverse the order of elements on a stack s using a Queue.

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