Find if an Expression has Duplicate Parenthesis or Not

Given a string containing balanced parenthesis. Find if the expression/string contains duplicate parenthesis or not.

Duplicate Parenthesis

When an expression is in the middle of or surrounded by the same type of balanced parenthesis i.e. enclosed between the same type of opening and closing parenthesis more than once it is said to have duplicate parenthesis. For example – ((a+b)) i.e. the whole expression is in the middle of two similar parentheses but in expression (a+(b)) neither the whole expression nor any sub-expression contains duplicate parenthesis.

For instance –

Example

Input: s = “(((a+(b))+(c+d)))”

Output: Expression contains duplicate parenthesis.

Input: s = “((a+b)+c+d)”

Output: Expression does not contain duplicate parenthesis.

Method Using Stack

Create a stack. Traverse or iterate through the given string. Check for each character, if it is equal to ‘(‘ or any operator or operand, push it to the the stack. Else if it is equal to ‘)’, pop the characters untill the open parenthesis of same kind is found. A count variable is used, increment it for every character till the opening parenthesis ‘(‘ is found. If the variable count is less than 1, then return true else there is no duplicate parenthesis found.

Algorithm

1. Initialize a string expression containing balanced parenthesis.
2. Initialize a stack to store characters.
3. Traverse the string and check if the current character is not a closing parenthesis, push the character into the stack.
4. Else pop the top of the stack and initialize a counter to count the elements inside the parenthesis as 0. While the top is not equal to an opening parenthesis increment the counter and pop the top.
5. Check if elements inside it are less than 1, return 1.
6. Return false.

C++ Program for Expression has Duplicate Parenthesis or Not

#include <bits/stdc++.h> 
using namespace std; 
  
bool isDuplicate(string s){ 
    
    stack<char> Stack; 
  
    for(char ch : s){ 
        
        if(ch == ')'){ 
            
            char top = Stack.top(); 
            Stack.pop(); 
  
            int elementsInside = 0; 
            
            while(top != '('){ 
                elementsInside++; 
                top = Stack.top(); 
                Stack.pop(); 
            } 
            
            if(elementsInside < 1){ 
                return 1; 
            } 
        } 
  
        else{
            Stack.push(ch); 
        }    
    } 
  
    return false; 
} 
  
  
int main(){ 
    
    string s = "(((a+(b))+(c+d)))"; 
  
    if(isDuplicate(s)){ 
        cout<<"Expression contains duplicate parenthesis.";
    }    
    else{
        cout<<"Expression does not contain duplicate parenthesis."; 
    }    
  
    return 0; 
}

Expression contains duplicate parenthesis.

Java Program for Expression has Duplicate Parenthesis or Not

import java.util.Stack; 
  
class Parenthesis{ 
  
    static boolean isDuplicate(String s){ 
        
        Stack<Character> Stack = new Stack<>(); 
  
        char[] str = s.toCharArray(); 
        for(char ch : str) { 
            
            if (ch == ')') { 
                
                char top = Stack.peek(); 
                Stack.pop(); 
  
                int elementsInside = 0; 
                
                while (top != '(') { 
                    elementsInside++; 
                    top = Stack.peek(); 
                    Stack.pop(); 
                } 
                
                if (elementsInside < 1){ 
                    return true; 
                } 
            } 
            
            else{ 
                Stack.push(ch); 
            } 
        } 
  
        return false; 
    } 
  
    public static void main(String[] args) { 
  
        String s = "(((a+(b))+(c+d)))"; 
  
        if(isDuplicate(s)){ 
            System.out.println("Expression contains duplicate parenthesis."); 
        } 
        
        else{ 
            System.out.println("Expression does not contain duplicate parenthesis."); 
        } 
  
    } 
}

Expression contains duplicate parenthesis.

Complexity Analysis for Expression has Duplicate Parenthesis or Not

Time Complexity: O(n) where n is the number of characters in expression.

Auxiliary Space: O(n) because we used space of stack to store the characters.

References