Wednesday, August 31, 2016

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