Eliminar paréntesis no válidos

Se dará una expresión que puede contener paréntesis de apertura y cierre y, opcionalmente, algunos caracteres. No habrá ningún otro operador en la string. Necesitamos eliminar el número mínimo de paréntesis para que la string de entrada sea válida. Si es posible más de una salida válida eliminando el mismo número de paréntesis, imprima toda esa salida. 
Ejemplos: 
 

Input  : str = “()())()” -
Output : ()()() (())()
There are two possible solutions
"()()()" and "(())()"

Input  : str = (v)())()
Output : (v)()()  (v())()

Como necesitamos generar todos los resultados posibles, retrocederemos entre todos los estados eliminando un corchete de apertura o cierre y verificando si son válidos, si no son válidos, luego agregue el corchete eliminado y vaya al siguiente estado. Usaremos BFS para movernos a través de los estados, el uso de BFS asegurará la eliminación de un número mínimo de paréntesis porque atravesamos los estados nivel por nivel y cada nivel corresponde a la eliminación de un paréntesis adicional. Aparte de esto, BFS no implica recursividad, por lo que también se ahorra la sobrecarga de pasar parámetros. 
El siguiente código tiene un método isValidString para verificar la validez de la string, cuenta los paréntesis abiertos y cerrados en cada índice ignorando el carácter sin paréntesis. Si en cualquier instante el conteo de paréntesis cerrados se vuelve más que abierto, devolvemos falso; de lo contrario, seguimos actualizando la variable de conteo. 
 

/*  C/C++ program to remove invalid parenthesis */
#include <bits/stdc++.h>
using namespace std;
 
//  method checks if character is parenthesis(open
// or closed)
bool isParenthesis(char c)
{
    return ((c == '(') || (c == ')'));
}
 
//  method returns true if string contains valid
// parenthesis
bool isValidString(string str)
{
    int cnt = 0;
    for (int i = 0; i < str.length(); i++)
    {
        if (str[i] == '(')
            cnt++;
        else if (str[i] == ')')
            cnt--;
        if (cnt < 0)
            return false;
    }
    return (cnt == 0);
}
 
//  method to remove invalid parenthesis
void removeInvalidParenthesis(string str)
{
    if (str.empty())
        return ;
 
    //  visit set to ignore already visited string
    unordered_set<string> visit;
 
    //  queue to maintain BFS
    queue<string> q;
    string temp;
    bool level;
 
    //  pushing given string as starting node into queue
    q.push(str);
    visit.insert(str);
    while (!q.empty())
    {
        str = q.front();  q.pop();
        if (isValidString(str))
        {
            cout << str << endl;
 
            // If answer is found, make level true
            // so that valid string of only that level
            // are processed.
            level = true;
        }
        if (level)
            continue;
        for (int i = 0; i < str.length(); i++)
        {
            if (!isParenthesis(str[i]))
                continue;
 
            // Removing parenthesis from str and
            // pushing into queue,if not visited already
            temp = str.substr(0, i) + str.substr(i + 1);
            if (visit.find(temp) == visit.end())
            {
                q.push(temp);
                visit.insert(temp);
            }
        }
    }
}
 
//  Driver code to check above methods
int main()
{
    string expression = "()())()";
    removeInvalidParenthesis(expression);
 
    expression = "()v)";
    removeInvalidParenthesis(expression);
 
    return 0;
}

// Java program to remove invalid parenthesis
import java.util.*;
 
class GFG
{
 
// method checks if character is parenthesis(open
// or closed)
static boolean isParenthesis(char c)
{
    return ((c == '(') || (c == ')'));
}
 
// method returns true if string contains valid
// parenthesis
static boolean isValidString(String str)
{
    int cnt = 0;
    for (int i = 0; i < str.length(); i++)
    {
        if (str.charAt(i) == '(')
            cnt++;
        else if (str.charAt(i) == ')')
            cnt--;
        if (cnt < 0)
            return false;
    }
    return (cnt == 0);
}
 
// method to remove invalid parenthesis
static void removeInvalidParenthesis(String str)
{
    if (str.isEmpty())
        return;
 
    // visit set to ignore already visited string
    HashSet<String> visit = new HashSet<String>();
 
    // queue to maintain BFS
    Queue<String> q = new LinkedList<>();
    String temp;
    boolean level = false;
 
    // pushing given string as
    // starting node into queue
    q.add(str);
    visit.add(str);
    while (!q.isEmpty())
    {
        str = q.peek(); q.remove();
        if (isValidString(str))
        {
            System.out.println(str);
 
            // If answer is found, make level true
            // so that valid string of only that level
            // are processed.
            level = true;
        }
        if (level)
            continue;
        for (int i = 0; i < str.length(); i++)
        {
            if (!isParenthesis(str.charAt(i)))
                continue;
 
            // Removing parenthesis from str and
            // pushing into queue,if not visited already
            temp = str.substring(0, i) + str.substring(i + 1);
            if (!visit.contains(temp))
            {
                q.add(temp);
                visit.add(temp);
            }
        }
    }
}
 
// Driver Code
public static void main(String[] args)
{
    String expression = "()())()";
    removeInvalidParenthesis(expression);
 
    expression = "()v)";
    removeInvalidParenthesis(expression);
}
}
 
// This code is contributed by 29AjayKumar

# Python3 program to remove invalid parenthesis
 
# Method checks if character is parenthesis(open
# or closed)
def isParenthesis(c):
    return ((c == '(') or (c == ')'))
 
# method returns true if contains valid
# parenthesis
def isValidString(str):
    cnt = 0
    for i in range(len(str)):
        if (str[i] == '('):
            cnt += 1
        else if (str[i] == ')'):
            cnt -= 1
        if (cnt < 0):
            return False
    return (cnt == 0)
     
# method to remove invalid parenthesis
def removeInvalidParenthesis(str):
    if (len(str) == 0):
        return
         
    # visit set to ignore already visited
    visit = set()
     
    # queue to maintain BFS
    q = []
    temp = 0
    level = 0
     
    # pushing given as starting node into queue
    q.append(str)
    visit.add(str)
    while(len(q)):
        str = q[0]
        q.pop()
        if (isValidString(str)):
            print(str)
             
            # If answer is found, make level true
            # so that valid of only that level
            # are processed.
            level = True
        if (level):
            continue
        for i in range(len(str)):
            if (not isParenthesis(str[i])):
                continue
                 
            # Removing parenthesis from str and
            # pushing into queue,if not visited already
            temp = str[0:i] + str[i + 1:]
            if temp not in visit:
                q.append(temp)
                visit.add(temp)
 
# Driver Code
expression = "()())()"
removeInvalidParenthesis(expression)
expression = "()v)"
removeInvalidParenthesis(expression)
 
# This code is contributed by SHUBHAMSINGH10

// C# program to remove invalid parenthesis
using System;
using System.Collections.Generic;
 
class GFG
{
 
// method checks if character is
// parenthesis(open or closed)
static bool isParenthesis(char c)
{
    return ((c == '(') || (c == ')'));
}
 
// method returns true if string contains
// valid parenthesis
static bool isValidString(String str)
{
    int cnt = 0;
    for (int i = 0; i < str.Length; i++)
    {
        if (str[i] == '(')
            cnt++;
        else if (str[i] == ')')
            cnt--;
        if (cnt < 0)
            return false;
    }
    return (cnt == 0);
}
 
// method to remove invalid parenthesis
static void removeInvalidParenthesis(String str)
{
    if (str == null || str == "")
        return;
 
    // visit set to ignore already visited string
    HashSet<String> visit = new HashSet<String>();
 
    // queue to maintain BFS
    Queue<String> q = new Queue<String>();
    String temp;
    bool level = false;
 
    // pushing given string as
    // starting node into queue
    q.Enqueue(str);
    visit.Add(str);
    while (q.Count != 0)
    {
        str = q.Peek(); q.Dequeue();
        if (isValidString(str))
        {
            Console.WriteLine(str);
 
            // If answer is found, make level true
            // so that valid string of only that level
            // are processed.
            level = true;
        }
         
        if (level)
            continue;
        for (int i = 0; i < str.Length; i++)
        {
            if (!isParenthesis(str[i]))
                continue;
 
            // Removing parenthesis from str and
            // pushing into queue,if not visited already
            temp = str.Substring(0, i) +
                   str.Substring(i + 1);
            if (!visit.Contains(temp))
            {
                q.Enqueue(temp);
                visit.Add(temp);
            }
        }
    }
}
 
// Driver Code
public static void Main(String[] args)
{
    String expression = "()())()";
    removeInvalidParenthesis(expression);
 
    expression = "()v)";
    removeInvalidParenthesis(expression);
}
}
 
// This code is contributed by Princi Singh

<script>
 
// JavaScript program to remove invalid parenthesis
 
// method checks if character is parenthesis(open
// or closed)
function isParenthesis(c)
{
    return ((c == '(') || (c == ')'));
}
 
// method returns true if string contains valid
// parenthesis
function isValidString(str)
{
    let cnt = 0;
    for (let i = 0; i < str.length; i++)
    {
        if (str[i] == '(')
            cnt++;
        else if (str[i] == ')')
            cnt--;
        if (cnt < 0)
            return false;
    }
    return (cnt == 0);
}
 
// method to remove invalid parenthesis
function removeInvalidParenthesis(str)
{
    if (str.length==0)
        return;
   
    // visit set to ignore already visited string
    let visit = new Set();
   
    // queue to maintain BFS
    let q = [];
    let temp;
    let level = false;
   
    // pushing given string as
    // starting node into queue
    q.push(str);
    visit.add(str);
    while (q.length!=0)
    {
        str = q.shift();
        if (isValidString(str))
        {
            document.write(str+"<br>");
   
            // If answer is found, make level true
            // so that valid string of only that level
            // are processed.
            level = true;
        }
        if (level)
            continue;
        for (let i = 0; i < str.length; i++)
        {
            if (!isParenthesis(str[i]))
                continue;
   
            // Removing parenthesis from str and
            // pushing into queue,if not visited already
            temp = str.substring(0, i) + str.substring(i + 1);
            if (!visit.has(temp))
            {
                q.push(temp);
                visit.add(temp);
            }
        }
    }
}
 
// Driver Code
let expression = "()())()";
removeInvalidParenthesis(expression);
 
expression = "()v)";
removeInvalidParenthesis(expression);
 
// This code is contributed by rag2127
 
</script>

Producción:  

(())()
()()()
(v)
()v

Este artículo es una contribución de Utkarsh Trivedi . 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.