Find if an expression has duplicate parenthesis

Problem statement : 

Given an balanced expression, find if it contains duplicate parenthesis or not. A set of parenthesis are duplicate if same sub-expression is surrounded by multiple parenthesis.

Examples:

Below expressions have duplicate parenthesis - 
((a+b)+((c+d)))
The subexpression "c+d" is surrounded by two
pairs of brackets.

(((a+(b)))+(c+d))
The subexpression "a+(b)" is surrounded by two 
pairs of brackets.

(((a+(b))+c+d))
The whole expression is surrounded by two 
pairs of brackets.

Below expressions don't have any duplicate parenthesis -
((a+b)+(c+d)) 
No subsexpression is surrounded by duplicate
brackets.

((a+(b))+(c+d))
No subsexpression is surrounded by duplicate
brackets.

It may be assumed that the given expression is valid and there are not any white spaces present. courtesy by geeksforgeeks .

Solution for this problem using stack data structure is below:

    Trace string expression left to right and insert all characters till you receive right parenthesis. If you find right parenthesis, pop all the elements till first occurrence of left parenthesis including left parenthesis itself.

     if top char itself is left parenthesis then duplicate parenthesis else no.

 package com.raj.stack;  
 import java.util.Stack;  
 public class DuplicateParenthesis {  
      private final static Character RIGHT_PARENTHESIS=')';  
      private final static Character LEFT_PARENTHESIS='(';  
      /**  
       * @param args  
       */  
      public static void main(String[] args) {  
           String exp1 = "((a+b)+((c+d)))";  
           String exp2 = "(((a+(b)))+(c+d))";  
           String exp3 = "(((a+(b))+c+d))";  
           String exp4 = "((a+b)+(c+d))";  
           String exp5 = "(a+((b))+(c+d))";  
           System.out.println("exp 1 : "+isDuplicateParenthesisFound(exp1));  
           System.out.println("exp 2 : "+isDuplicateParenthesisFound(exp2));  
           System.out.println("exp 3 : "+isDuplicateParenthesisFound(exp3));  
           System.out.println("exp 4 : "+isDuplicateParenthesisFound(exp4));  
           System.out.println("exp 5 : "+isDuplicateParenthesisFound(exp5));  
      }  
      private static boolean isDuplicateParenthesisFound(String exp){  
           Stack<Character> expstack = new Stack<>();  
           for(int i = 0; i < exp.length(); i++){  
                if(exp.charAt(i) != RIGHT_PARENTHESIS){  
                     push(expstack, exp.charAt(i));  
                }else if(pop(expstack, LEFT_PARENTHESIS)){  
                     return true;  
                }  
           }  
           return false;  
      }  
      private static <T> void push(Stack<T> expstack, T t){  
           expstack.push(t);  
      }  
      private static <T> boolean pop(Stack<T> expstack, T condition){  
           if(expstack.pop()==condition){  
                return true;  
           }  
           while(expstack.pop() != condition);  
           return false;  
      }  
 }  

 Design a stack that supports getMin() in O(1) time with extra space  
 Original problem statement from geeksforgeeks.org  
 This is the generic implementation of this stack data structure.  
 package com.raj.ds.stack;  
 import java.util.Comparator;  
 /**  
  * @author rajendar.bit@gmail.com  
  *  
  */  
 public interface IStack <T>{  
  /**  
  * <p>This method will be used to push the element onto stack.<p>  
  *  
  * @param t  
  */  
  public void push(T t);  
  /**  
  * <p>This method will be used to get and remove the top element from stack.<p>  
  * @return  
  */  
  public T pop();  
  /**  
  * It will return the current size of the stack.<p>  
  * @return  
  */  
  public int size();  
  /**  
  * @return  
  * <p> returns <code>true</code> if stack reached its capacity else <code>false</code>.<p>  
  */  
  public boolean isFull();  
  /**  
  *  
  * @return  
  * returns <code>true</code> if stack empty else <code>false</code>.<p>  
  */  
  public boolean isEmpty();  
  /**  
  * <p>It will return minimum element at current position of the stack.<p>  
  * @return  
  *  
  */  
  public T minElement();  
  /**  
  *  
  * @return  
  * <p>It will return user defined {@link Comparator}<p>  
  */  
  Comparator<? super T> comparator();  
 }  
 #################################################################################  
 package com.raj.ds.stack;  
 import java.util.Comparator;  
 /**  
  * @author rajendar.bit@gmail.com  
  *  
  *<p>Question: Design a Data Structure SpecialStack that supports all the stack operations<p>   
  *<p>like push(), pop(), isEmpty(), isFull() and an additional operation getMin() which should <p>  
  *<p>return minimum element from the SpecialStack. All these operations of SpecialStack must be O(1).<p>  
  *<p> To implement SpecialStack, you should only use standard Stack data structure and no other data<p>  
  *  
  *  
  */  
 public class MinStack<T> implements IStack<T>{  
  /**This Object array will be used to store elements for stack data structure **/  
  private Object stack[];  
  /**This Object array will be used to store minimum elements for stack data structure **/  
  private Object minStack[];  
  /** Capacity will be used to define the maximum size of stack**/  
  private int capacity;  
  /** Index will be used to store the element in Object array.**/  
  private int index;  
  /** DEFAULT_CAPACITY is the maximum default capacity of stack**/   
  private final static int DEFAULT_CAPACITY=10;  
  /**   
  * <p>{@linkplain Comparator} Will be used to compare the current minimum element with new element for user define class.<p>  
  * <p>User defined class must implement {@linkplain Comparator} interface.<p>  
  * **/  
  private final Comparator<? super T> comparator;  
  /**  
  * <p>This Constructor can be used for all wrapper classes with default {@link MinStack#capacity}<p>  
  */  
  public MinStack() {  
  this.capacity = DEFAULT_CAPACITY;  
  this.comparator = null;  
  stack = new Object[this.capacity];  
  minStack= new Object[this.capacity];  
  }  
  /**  
  * <p>This Constructor can be used for all wrapper classes with user defined {@link MinStack#capacity}<p>  
  * @param capacity  
  */  
  public MinStack( int capacity) {  
  this.capacity = capacity;  
  this.comparator = null;  
  stack = new Object[this.capacity];  
  minStack= new Object[this.capacity];  
  }  
  /**  
  *<p>This Constructor can be used for all user defined classes and comparator with default {@link MinStack#capacity}<p>  
  * @param comparator  
  */  
  public MinStack(Comparator<? super T> comparator) {  
  this.capacity = DEFAULT_CAPACITY;  
  this.comparator = comparator;  
  stack = new Object[this.capacity];  
  minStack= new Object[this.capacity];  
  }  
  /**  
  * <p>This Constructor can be used for all user defined classes and comparator with user defined {@link MinStack#capacity}<p>  
  * @param comparator  
  * @param capacity  
  */  
  public MinStack(Comparator<? super T> comparator, int capacity) {  
  this.capacity = capacity;  
  this.comparator = comparator;  
  stack = new Object[this.capacity];  
  minStack= new Object[this.capacity];  
  }  
  /* (non-Javadoc)  
  * @see com.raj.ds.stack.IStack#push(java.lang.Object)  
  */  
  @SuppressWarnings("unchecked")  
  @Override  
  public void push(T t) {  
  if(this.isFull()){  
   throw new RuntimeException("Stack is over flow.");  
  }  
  if(this.isEmpty()){  
   minStack[index] = t;  
  }else if(null != comparator && 0<=comparator.compare((T)minStack[index-1],t)){  
   minStack[index]=t;  
  }else if(0<=((Comparable< ? super T>)minStack[index-1]).compareTo(t)){  
   minStack[index]=t;  
  }else{  
   minStack[index]=minStack[index-1];  
  }  
  stack[index++] = t;  
  }  
  /* (non-Javadoc)  
  * @see com.raj.ds.stack.IStack#pop()  
  */  
  @Override  
  public T pop() {  
  @SuppressWarnings("unchecked")  
  T t = (T)stack[--index];  
  stack[index] = null;  
  minStack[index]= null;  
  return t;  
  }  
  /* (non-Javadoc)  
  * @see com.raj.ds.stack.IStack#size()  
  */  
  @Override  
  public int size() {  
  return index;  
  }  
  /* (non-Javadoc)  
  * @see com.raj.ds.stack.IStack#isFull()  
  */  
  @Override  
  public boolean isFull() {  
  return this.capacity==index;  
  }  
  /* (non-Javadoc)  
  * @see com.raj.ds.stack.IStack#isEmpty()  
  */  
  @Override  
  public boolean isEmpty() {  
  return 0==index;  
  }  
  /* (non-Javadoc)  
  * @see com.raj.ds.stack.IStack#minElement()  
  */  
  @SuppressWarnings("unchecked")  
  @Override  
  public T minElement() {  
  return (T)minStack[index-1];  
  }  
  /* (non-Javadoc)  
  * @see com.raj.ds.stack.IStack#comparator()  
  */  
  @Override  
  public Comparator<? super T> comparator() {  
  return comparator;  
  }  
 }  
 #################################################################################  
 package com.raj.ds.stack;  
 /**  
  * @author rajendar.bit@gmail.com  
  *  
  */  
 public class User {  
  public int id ;  
  public User(int id) {  
  this.id=id;  
  }  
  /* (non-Javadoc)  
  * @see java.lang.Object#toString()  
  */  
  @Override  
  public String toString() {  
  return "id = "+id;  
  }  
 }  
 #################################################################################  
 package com.raj.ds.stack;  
 import java.util.Comparator;  
 public class Main {  
  public static void main(String[] args) {  
  MinStack<String> minStack = new MinStack<>(3);  
  minStack.push("A");  
  minStack.push("C");  
  minStack.push("B");  
  minStack.pop();  
  MinStack<User> userDefinedClassMinStack = new MinStack<>(new Comparator<User>() {  
   @Override  
   public int compare(User o1, User o2) {  
   return o1.id > o2.id ? 1: o1.id == o2.id ? 0 : -1;  
   }  
  });  
  User t = new User(1);  
  User t1 = new User(2);  
  User t3 = new User(3);  
  userDefinedClassMinStack.push(t);  
  userDefinedClassMinStack.push(t1);  
  userDefinedClassMinStack.push(t3);  
  userDefinedClassMinStack.pop();  
  }  
 }  

Reverse stack using recursion in java

 Here I am going to implement stack with fixed size of array and it also has behavior that will reverse the stack data.  
 package com.raj;  
 /**  
  * @author rajendar.bit@gmail.com  
  *  
  */  
 public class Stack<T> {  
  private Object stack[];  
  private int capacity;  
  private int index;  
  private final static int DEFAULT_SIZE=10;  
  public Stack(){  
  this(DEFAULT_SIZE);  
  }  
  public Stack(int capacity){  
  this.capacity = capacity;  
  stack = new Object[capacity];  
  }  
  /**  
  *  
  * @return boolean  
  */  
  public boolean isEmpty(){  
  return this.index==0;  
  }  
  /**  
  *  
  * @return boolean  
  */  
  public boolean isFull(){  
  return this.capacity==this.index;  
  }  
  /**  
  * <p>This method will be used to push the data at top.<p>  
  * @param t  
  */  
  public void push(T t){  
  if(isFull())  
   throw new IllegalArgumentException("Stack over flow.");  
  stack[index++]=t;  
  }  
  /**  
  * <p>This method will return and remove the top element.<p>  
  * @return  
  */  
  @SuppressWarnings("unchecked")  
  public T pop(){  
  if(isEmpty())  
   throw new IllegalArgumentException("stack under flow.");  
   T t= (T)stack[--index];  
   stack[index] = null;  
   return t;  
  }  
  /**  
  * <p>This method will reverse the existing stack recursively.<p>  
  * @param size  
  */  
  public void reverse(int size){  
  if(size==0){  
   return;  
  }  
  T t = pop();  
  reverse(size-1);  
  inserAtBottom(t);  
  }  
  /**  
  * <p>This method returns number of elements in stack.<p>  
  * @return  
  */  
  public int size(){  
  return index;  
  }  
  /**  
  * <p>Inserts the element at bottom in existing stack.<p>  
  * @param t  
  */  
  private void inserAtBottom(T t){  
  if(isEmpty()){  
   push(t);  
  }else{  
   T tmp = pop();  
   inserAtBottom(t);  
   push(tmp);  
  }  
  }  
 }  
 Main method:  
 package com.raj;  
 /**  
  * @author rajendar.bit@gmail.com  
  *  
  */  
 public class StackMain{  
  public static void main(String[] args) {  
  Stack<Integer> stack = new Stack<>();  
  for (int i = 0; i < 10; i++) {  
   stack.push(i);  
  }  
  stack.reverse(stack.size());  
  while(stack.size()!=0){  
   System.out.println(stack.pop());  
  }  
  Stack<String> stacks = new Stack<>();  
  stacks.push("A");  
  stacks.push("B");  
  stacks.push("C");  
  stacks.reverse(stacks.size());  
  while(stacks.size()!=0){  
   System.out.println(stacks.pop());  
  }  
  }  
 }