Encuentra si una expresión tiene paréntesis duplicados o no

Dada una expresión balanceada, encuentre si contiene paréntesis duplicados o no. Un conjunto de paréntesis está duplicado si la misma subexpresión está rodeada por varios paréntesis. 

Ejemplos: 

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.

((a+(b))+(c+d))
(b) and ((a+(b)) 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.

Se puede suponer que la expresión dada es válida y que no hay espacios en blanco presentes. 

La idea es usar stack. Itere a través de la expresión dada y para cada carácter en la expresión, si el carácter es un paréntesis de apertura ‘(‘ o cualquiera de los operadores u operandos, empújelo a la parte superior de la pila. Si el carácter es un paréntesis de cierre ‘)’, luego extraiga los caracteres de la pila hasta que se encuentre el paréntesis de apertura ‘(‘ coincidente y se use un contador, cuyo valor se incrementa para cada carácter encontrado hasta que se encuentre el paréntesis de apertura ‘(‘. Si el número de caracteres encontrados entre la apertura y el cierre par de paréntesis, que es igual al valor del contador, es menor que 1, entonces se encuentra un par de paréntesis duplicados, de lo contrario no hay pares de paréntesis redundantes. Por ejemplo, (((a+b))+c) tiene corchetes duplicados alrededor de «a+b». Cuando se encuentra el segundo «)» después de a+b, la pila contiene «((«.

A continuación se muestra la implementación de la idea anterior: 

// C++ program to find duplicate parenthesis in a
// balanced expression
#include <bits/stdc++.h>
using namespace std;
 
// Function to find duplicate parenthesis in a
// balanced expression
bool findDuplicateparenthesis(string str)
{
    // create a stack of characters
    stack<char> 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;
}

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<Character> 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 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

// C# program to find duplicate parenthesis
// in a balanced expression
using System;
using System.Collections.Generic;
 
class GFG
{
 
// Function to find duplicate parenthesis 
// in a balanced expression
static Boolean findDuplicateparenthesis(String s)
{
    // create a stack of characters
    Stack<char> Stack = new Stack<char>();
 
    // Iterate through the given expression
    char[] str = s.ToCharArray();
    foreach (char ch in 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))
    {
        Console.WriteLine("Duplicate Found ");
    }
    else
    {
        Console.WriteLine("No Duplicates Found ");
    }
}
}
 
// This code is contributed by 29AjayKumar

<script>
 
// Javascript program to find duplicate
// parenthesis in a balanced expression
 
// Function to find duplicate parenthesis
// in a balanced expression
function findDuplicateparenthesis(s)
{
     
    // Create a stack of characters
    let Stack = [];
 
    // Iterate through the given expression
    let str = s.split("");
    for(let ch = 0; ch < str.length;ch++)
    {
         
        // If current character is close
        // parenthesis ')'
        if (str[ch] == ')')
        {
             
            // pop character from the stack
            let 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
            let elementsInside = 0;
            while (top != '(')
            {
                elementsInside++;
                top = Stack.pop();
            }
            if (elementsInside < 1)
            {
                return true;
            }
        }
         
        // push open parenthesis '(', operators
        // and operands to stack
        else
        {
            Stack.push(str[ch]);
        }
    }
 
    // No duplicates found
    return false;
}
 
// Driver code
let str = "(((a+(b))+(c+d)))";
 
// Input balanced expression
if (findDuplicateparenthesis(str))
{
    document.write("Duplicate Found ");
}
else
{
    document.write("No Duplicates Found ");
}
 
// This code is contributed by rag2127
 
</script>

Producción: 

Duplicate Found

La complejidad temporal de la solución anterior es O(n). 

El espacio auxiliar utilizado por el programa es O(n).

Este artículo es una contribución de Aditya Goel . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.