Wellformed Parenthesis problem Write a Java program that det

Well-formed Parenthesis problem: Write a Java program that determines whether a given line of input has a balanced set of parentheses or not. The input String will only contain left and right parentheses and perhaps blank spaces.   If the input string has blank spaces, you can ignore them and look only for left or right parenthesis. Use the Stack data structure (as given in the java.util.* library) to solve the problem. What is the time-complexity of the algorithm underlying your program?

Here is the definition of balanced parentheses:

As you move from left to right through the input string, you should never encounter more right parentheses than left parentheses.

The total number of left parentheses must equal the total number of right parentheses.

You can either assume that the string is read in from the keyboard or hard-coded within the main () of your program. Here are some sample inputs and program outputs to help you understand the problem.

1. ((()) – Not balanced

2. ())(() – Not balanced

3. (()())) – Not balanced

4. (())() –   Balanced

2. Double Palindrome problem: A palindrome is a string that reads the same forward and backward. The classic examples are “mom”, “level”, “madam”, “rotator”, etc. A double palindrome is a string that has two palindromes back to back. These are somewhat artificial and may not exist in any language. For example, strings like “mommom”, “madammadam” are double palindromes.   Your task is to write a Java program, with a suitable data structure if needed, to detect if a string is a double palindrome or not. You can either assume that the string is read in from the keyboard or hard-coded within the main () of your program.

3. Double Ended Queue: (Dqueue) A double ended queue is much like a queue except that the operations of enqueing (adding) and dequeing (removing) can be done at both ends of the queue. In a conventional queue, the enque operation is done at the tail and deque is done at the tail but in a Dqueue these operations are allowed at both ends. The following 6 methods are possible.

public void enqueHead(E element),

public void enqueTail(E element)

public E dequeHead()

public E dequeTail()

public E peekHead() that returns the element at the Head but not remove it.

public E peekTail() that returns the element at the Tail but not remove it.

The goal is to develop a java program to implement a Dqueue in an efficient manner for all the above 6 methods.   Extend java.util.LinkedList <E> to Dqueue<E> and implement all of the above methods.

Solution

Answer Q1

public final class BalancedParanthesis {

private static final Map<Character, Character> brackets = new HashMap<Character, Character>();
static {
brackets.put(\'[\', \']\');
brackets.put(\'{\', \'}\');
brackets.put(\'(\', \')\');
}

private BalancedParanthesis() {};

/**
* Returns true is parenthesis match open and close.
* Understands [], {}, () as the brackets
* It is clients responsibility to include only valid paranthesis as input.
* A false could indicate that either parenthesis did not match or input including chars other than valid paranthesis
*
* @param str the input brackets
* @return true if paranthesis match.
*/
public static boolean isBalanced(String str) {
if (str.length() == 0) {
throw new IllegalArgumentException(\"String length should be greater than 0\");
}
// odd number would always result in false
if ((str.length() % 2) != 0) {
return false;
}

final Stack<Character> stack = new Stack<Character>();
for (int i = 0; i < str.length(); i++) {
if (brackets.containsKey(str.charAt(i))) {
stack.push(str.charAt(i));
} else if (stack.empty() || (str.charAt(i) != brackets.get(stack.pop()))) {
return false;
}
}
return true;
}

public static void main(String[] args) {
assertEquals(true, isBalanced(\"{}([])\"));
assertEquals(false,isBalanced(\"([}])\"));
assertEquals(true, isBalanced(\"([])\"));
assertEquals(true, isBalanced(\"()[]{}[][]\"));
}
}

Answer Q2

import java.util.ArrayList;
import java.util.List;

public class DoubleEndedQueueImpl {

private List<Integer> deque = new ArrayList<Integer>();

public void insertFront(int item){
//add element at the beginning of the queue
System.out.println(\"adding at front: \"+item);
deque.add(0,item);
System.out.println(deque);
}

public void insertRear(int item){
//add element at the end of the queue
System.out.println(\"adding at rear: \"+item);
deque.add(item);
System.out.println(deque);
}

public void removeFront(){
if(deque.isEmpty()){
System.out.println(\"Deque underflow!! unable to remove.\");
return;
}
//remove an item from the beginning of the queue
int rem = deque.remove(0);
System.out.println(\"removed from front: \"+rem);
System.out.println(deque);
}

public void removeRear(){
if(deque.isEmpty()){
System.out.println(\"Deque underflow!! unable to remove.\");
return;
}
//remove an item from the beginning of the queue
int rem = deque.remove(deque.size()-1);
System.out.println(\"removed from front: \"+rem);
System.out.println(deque);
}

public int peakFront(){
//gets the element from the front without removing it
int item = deque.get(0);
System.out.println(\"Element at first: \"+item);
return item;
}

public int peakRear(){
//gets the element from the rear without removing it
int item = deque.get(deque.size()-1);
System.out.println(\"Element at rear: \"+item);
return item;
}

public static void main(String a[]){

DoubleEndedQueueImpl deq = new DoubleEndedQueueImpl();
deq.insertFront(34);
deq.insertRear(45);
deq.removeFront();
deq.removeFront();
deq.removeFront();
deq.insertFront(21);
deq.insertFront(98);
deq.insertRear(5);
deq.insertFront(43);
deq.removeRear();
}
}