Find if an expression has duplicate parenthesis or not

Given a balanced expression, find if it contains duplicate parenthesis or not. A set of parenthesis are duplicate if the same subexpression 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.

Recommended: Please try your approach on {IDE} first, before moving on to the solution.

The idea is to use stack. Iterate through the given expression and for each character in the expression, if the character is a open parenthesis ‘(‘ or any of the operators or operands, push it to the top of the stack. If the character is close parenthesis ‘)’, then pop characters from the stack till matching open parenthesis ‘(‘ is found and a counter is used, whose value is incremented for every character encountered till the opening parenthesis ‘(‘ is found. If the number of characters encountered between the opening and closing parenthesis pair, which is equal to the value of the counter, is less than or equal to 1, then a pair of duplicate parenthesis is found else there is no occurrence of redundant parenthesis pairs. For example, (((a+b))+c) has duplicate brackets around “a+b”. When the second “)” after a+b is encountered, the stack contains “((“. Since the top of stack is a opening bracket, it can be concluded that there are duplicate brackets.

Below is the implementation of above idea :

C++

 // C++ program to find duplicate parenthesis in a // balanced expression #include #include using namespace std;    // Function to find duplicate parenthesis in a // balanced expression bool findDuplicateparenthesis(string str) {     // create a stack of characters     stack Stack;        // Iterate through the given expression     for (char ch : str)     {         // if current character is close parenthesis ')'         if (ch == ')')         {             // pop character from the stack             char top = Stack.top();             Stack.pop();                // stores the number of characters between a              // closing and opening parenthesis             // if this count is less than or equal to 1             // then the brackets are redundant else not             int elementsInside = 0;             while (top != '(')             {                 elementsInside++;                 top = Stack.top();                 Stack.pop();             }             if(elementsInside <= 1) {                 return 1;             }         }            // push open parenthesis '(', operators and         // operands to stack         else             Stack.push(ch);     }        // No duplicates found     return false; }       // Driver code int main() {     // input balanced expression     string str = "(((a+(b))+(c+d)))";        if (findDuplicateparenthesis(str))         cout << "Duplicate Found ";     else         cout << "No Duplicates Found ";        return 0; }

/div>

Java

 import java.util.Stack;    // Java program to find duplicate parenthesis in a  // balanced expression  public class GFG {    // Function to find duplicate parenthesis in a  // balanced expression      static boolean findDuplicateparenthesis(String s) {         // create a stack of characters          Stack Stack = new Stack<>();            // Iterate through the given expression          char[] str = s.toCharArray();         for (char ch : str) {             // if current character is close parenthesis ')'              if (ch == ')') {                 // pop character from the stack                  char top = Stack.peek();                 Stack.pop();                    // stores the number of characters between a                  // closing and opening parenthesis                  // if this count is less than or equal to 1                  // then the brackets are redundant else not                  int elementsInside = 0;                 while (top != '(') {                     elementsInside++;                     top = Stack.peek();                     Stack.pop();                 }                 if (elementsInside <= 1) {                     return true;                 }             } // push open parenthesis '(', operators and              // operands to stack              else {                 Stack.push(ch);             }         }            // No duplicates found          return false;     }    // Driver code  public static void main(String[] args) {            // input balanced expression          String str = "(((a+(b))+(c+d)))";            if (findDuplicateparenthesis(str)) {             System.out.println("Duplicate Found ");         } else {             System.out.println("No Duplicates Found ");         }        } }

Python3

 # Python3 program to find duplicate  # parenthesis in a balanced expression     # Function to find duplicate parenthesis  # in a balanced expression  def findDuplicateparenthesis(string):         # create a stack of characters      Stack = []         # Iterate through the given expression      for ch in string:                # if current character is          # close parenthesis ')'          if ch == ')':                         # pop character from the stack              top = Stack.pop()                 # stores the number of characters between              # a closing and opening parenthesis              # if this count is less than or equal to 1              # then the brackets are redundant else not              elementsInside = 0             while top != '(':                                 elementsInside += 1                 top = Stack.pop()                             if elementsInside <= 1:                  return True            # push open parenthesis '(', operators          # and operands to stack          else:             Stack.append(ch)             # No duplicates found      return False    # Driver Code if __name__ == "__main__":         # input balanced expression      string = "(((a+(b))+(c+d)))"        if findDuplicateparenthesis(string) == True:          print("Duplicate Found")      else:         print("No Duplicates Found")     # This code is contributed by Rituraj Jain

Output:

Duplicate Found

Time complexity of above solution is O(n).
Auxiliary space used by the program is O(n).

Stack Stack