Duplicate parenthesis in an expression

Problem: For any given balanced mathematical expression, find if it contains duplicate parenthesis.

Problem Explanation: Expression is said to contain duplicate parenthesis if a sub expression is surrounded by multiple parenthesis. For input expression expr = “((a+b)+((c)))”, c is surrounded by multiple parenthesis. Hence output is true. Similarly, for expr = “x+(y+z)” output is false, as no multiple parenthesis exits for any of the subexpression.

Java Implementation

public class DuplicateParenthesis {
     public boolean isDuplicate(String str) {
        Stack<Character> stack = new Stack<Character>();

        for (int i = 0; i < str.length(); i++) {
            if (str.charAt(i) != ')') {
                stack.push(str.charAt(i));
            } else {
                if (stack.peek() == '(') {
                    return true;
                }
                while (stack.peek() != '(') {
                    stack.pop();
                }
                stack.pop();
            }
        }
        return false;
    }

public static void main(String[] args) {
        String expr = "((a+b)+((c)))";
        DuplicateParenthesis duplicateParenthesis = new DuplicateParenthesis();
        System.out.println(duplicateParenthesis.isDuplicate(expr));
    }
}

TimeComplexity: O(n)


Note: If you find any other better way to approach to this problem or you find any issue/error in above code snippets/approaches – please share it in the comments section below and get a chance to enrol free of cost for an online Live Data Structure and Algorithm course (specially designed for interview preparation for software companies like Amazon, Google, Facebook, FlipKart, SnapDeal, HealthKart…)