Question

Stack Class

////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

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

////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

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

////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

MAIN

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("\nHere'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();
      
   }
}

///////////////////////////////////////////////////////////////////Lab Exercises.//////////////////////////////////////////////////////////////////////

Lab Exercises.

2. Write a method (in the class StackTest) public static boolean isPalindrome(String input) that checks if a given string is a palindrome using a stack. Test your method using the following strings: civic, madam, apple.

2. Write a method public static Stack reverse(Stack s) that reverses the order of elements on stack s using a Queue. Test your method using some example stacks.

2. Write a method public static boolean isBalanced(String expression), that checks if a given mathematical expression is balanced or not. 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.

The method takes as input a mathematical expression and outputs whether the input is balanced or not. Use stacks to find your answer. Test your method on ((3), [(3 + 4)] and {{( )( )}}.

Answer 1

Q2. public static boolean isPalindrome(char str[])
{
int len = str.length;
  
// Allocating the memory for the stack
Stack s = new Stack(40);
  
// Finding the mid
int i, mid = len/ 2;
  
for (i = 0; i < mid; i++)
{
s1. push(str[i]);
}
  
// Checking if the length of the String
// is odd then neglect the
// middle character
if (len % 2 != 0)
{
i++;
}
  
// While not the end of the String
while (i < len)
{
char el = s1.pop();
  
// If the characters differ then the
// given String is not a palindrome
if (el != str[i])
return false;
i++;
}
  
return true;
}

public static Stack  reverse( Stack s1)
{

while (!queue.isEmpty()) {
s1.push(queue.peek());
queue.dequeue();
}
while (!s1.isEmpty()) {
queue.enqueue(s1.peek());
s1.pop();
}
}
  

Q3.

public static boolean isBalanced(String expression)
{
Stack s =new Stack(40);
  
// Traversing the Expression
for (int i = 0; i < expression.length(); i++) {
char z = expression.charAt(i);
  
if (z == '(' || z == '[' || z == '{') {
// Push the element in the stack
s.push(z);
continue;
}
  

if (s.isEmpty())
return false;
  
switch (z) {
case ')':
s.pop();
if (z == '{' || z== '[')
return false;
break;
  
case '}':
s.pop();
if (z == '(' || z == '[')
return false;
break;
  
case ']':
s.pop();
if (z == '(' || z == '{')
return false;
break;
}
}
  
// Check Empty Stack
if (s.isEmpty())

return true;
}