Número de paréntesis de cierre necesarios para completar una secuencia regular de paréntesis

Dada una secuencia de corchetes incompleta S. La tarea es encontrar el número de corchetes de cierre ‘)’ necesarios para convertirla en una secuencia de corchetes regular e imprimir la secuencia de corchetes completa. Puede agregar corchetes solo al final de la secuencia de corchetes dada. Si no es posible completar la secuencia de paréntesis, escriba “IMPOSIBLE”.
Definamos una secuencia regular de paréntesis de la siguiente manera: 
 

• La string vacía es una secuencia de paréntesis regular.
• Si s es una secuencia de paréntesis regular, entonces (s) es una secuencia de paréntesis regular.
• Si s & t son secuencias de corchetes regulares, entonces st es una secuencia de corchetes regulares.

Ejemplos : 
 

Entrada : str = “(()(()(” 
Salida : (()(()())) 
Explicación : El número mínimo de ) necesarios para que la secuencia sea regular son 3, que se agregan al final.
Entrada : str = “())(()” 
Salida : IMPOSIBLE 
 

Enfoque:
necesitamos agregar una cantidad mínima de corchetes de cierre ‘)’, por lo que contaremos la cantidad de corchetes de apertura desequilibrados y luego agregaremos esa cantidad de corchetes de cierre. Si en algún punto el número del paréntesis de cierre es mayor que el del paréntesis de apertura entonces la respuesta es IMPOSIBLE .

Algoritmo:

1. Crea dos variables abrir = 0 y cerrar = 0
2. Traverse en una string de i = 0 a i = n (tamaño de la string)
3. Si el elemento actual es ‘(‘ entonces incremente la apertura; de lo contrario, si el elemento actual es ‘)’, entonces incremente el cierre.
4. Mientras atraviesa, verifique si el recuento de cierre es mayor que el de apertura o no, en caso afirmativo, imprima Imposible volver a principal 
5. Después de completar el recorrido, calcule (abrir-cerrar) tantas veces como sea necesario para cerrar los paréntesis para equilibrar la secuencia.

A continuación se muestra la implementación del enfoque anterior: 
 

// C++ program to find number of closing
// brackets needed and complete a regular
// bracket sequence
#include <iostream>
using namespace std;
 
// Function to find number of closing
// brackets and complete a regular
// bracket sequence
void completeSequence(string s)
{
    // Finding the length of sequence
    int n = s.length();
 
    int open = 0, close = 0;
 
    for (int i = 0; i < n; i++)
    {
        // Counting opening brackets
        if (s[i] == '(')
            open++;
        else
            // Counting closing brackets
            close++;
 
        // Checking if at any position the
        // number of closing bracket
        // is more then answer is impossible
        if (close > open)
        {
            cout << "Impossible" << endl;
            return;
        }
    }
 
    // If possible, print 's' and
    // required closing brackets.
    cout << s;
    for (int i = 0; i < open - close; i++)
        cout << ')';
    cout << endl;
}
 
// Driver code
int main()
{
    string s = "(()(()(";
    completeSequence(s);
    return 0;
}
 
// This code is contributed by
// sanjeev2552

// Java program to find number of closing
// brackets needed and complete a regular
// bracket sequence
class GFG {
 
    // Function to find number of closing
    // brackets and complete a regular
    // bracket sequence
    static void completeSequence(String s)
    {
        // Finding the length of sequence
        int n = s.length();
 
        int open = 0, close = 0;
 
        for (int i = 0; i < n; i++) {
 
            // Counting opening brackets
            if (s.charAt(i) == '(')
                open++;
            else
                // Counting closing brackets
                close++;
 
            // Checking if at any position the
            // number of closing bracket
            // is more then answer is impossible
            if (close > open) {
                System.out.print("IMPOSSIBLE");
                return;
            }
        }
 
        // If possible, print 's' and required closing
        // brackets.
        System.out.print(s);
        for (int i = 0; i < open - close; i++)
            System.out.print(")");         
    }
 
    // Driver code
    public static void main(String[] args)
    {
        String s = "(()(()(";
        completeSequence(s);
    }
}

# Python 3 program to find number of
# closing brackets needed and complete
# a regular bracket sequence
 
# Function to find number of closing
# brackets and complete a regular
# bracket sequence
def completeSequence(s):
 
    # Finding the length of sequence
    n = len(s)
 
    open = 0
    close = 0
 
    for i in range(n):
 
        # Counting opening brackets
        if (s[i] == '('):
            open += 1
        else:
             
            # Counting closing brackets
            close += 1
 
        # Checking if at any position the
        # number of closing bracket
        # is more then answer is impossible
        if (close > open):
            print("IMPOSSIBLE")
            return
 
    # If possible, print 's' and
    # required closing brackets.
    print(s, end = "")
    for i in range(open - close):
        print(")", end = "")
 
# Driver code
if __name__ == "__main__":
     
    s = "(()(()("
    completeSequence(s)
 
# This code is contributed by ita_c

// C# program to find number of closing
// brackets needed and complete a
// regular bracket sequence
using System;
 
class GFG
{
// Function to find number of closing
// brackets and complete a regular
// bracket sequence
static void completeSequence(String s)
{
    // Finding the length of sequence
    int n = s.Length;
 
    int open = 0, close = 0;
 
    for (int i = 0; i < n; i++)
    {
 
        // Counting opening brackets
        if (s[i] == '(')
            open++;
        else
            // Counting closing brackets
            close++;
 
        // Checking if at any position the
        // number of closing bracket
        // is more then answer is impossible
        if (close > open)
        {
            Console.Write("IMPOSSIBLE");
            return;
        }
    }
 
    // If possible, print 's' and
    // required closing brackets.
    Console.Write(s);
    for (int i = 0; i < open - close; i++)
        Console.Write(")");        
}
 
// Driver Code
static void Main()
{
    String s = "(()(()(";
    completeSequence(s);
}
}
 
// This code is contributed
// by ANKITRAI1

<?php
// PHP program to find number of closing
// brackets needed and complete a
// regular bracket sequence
 
// Function to find number of closing
// brackets and complete a regular
// bracket sequence
function completeSequence($s)
{
    // Finding the length of sequence
    $n = strlen($s);
    $open = 0;
    $close = 0;
 
    for ($i = 0; $i < $n; $i++)
    {
 
        // Counting opening brackets
        if ($s[$i] == '(')
            $open++;
        else
            // Counting closing brackets
            $close++;
 
        // Checking if at any position the
        // number of closing bracket
        // is more then answer is impossible
        if ($close > $open)
        {
            echo ("IMPOSSIBLE");
            return;
        }
    }
 
    // If possible, print 's' and
    // required closing brackets.
    echo ($s);
    for ($i = 0; $i < $open - $close; $i++)
        echo (")");    
}
 
// Driver Code
$s = "(()(()(";
completeSequence($s);
 
// This code is contributed
// by ajit
?>

<script>
    // Javascript program to find number of closing
    // brackets needed and complete a
    // regular bracket sequence
     
    // Function to find number of closing
    // brackets and complete a regular
    // bracket sequence
    function completeSequence(s)
    {
        // Finding the length of sequence
        let n = s.length;
 
        let open = 0, close = 0;
 
        for (let i = 0; i < n; i++)
        {
 
            // Counting opening brackets
            if (s[i] == '(')
                open++;
            else
                // Counting closing brackets
                close++;
 
            // Checking if at any position the
            // number of closing bracket
            // is more then answer is impossible
            if (close > open)
            {
                document.write("IMPOSSIBLE");
                return;
            }
        }
 
        // If possible, print 's' and
        // required closing brackets.
        document.write(s);
        for (let i = 0; i < open - close; i++)
            document.write(")");        
    }
     
    let s = "(()(()(";
    completeSequence(s);
         
</script>

(()(()()))

Complejidad de tiempo: O (n), donde n es el tamaño de la string dada

Espacio auxiliar: O (1), ya que no estamos usando ningún espacio adicional.