Equilibre los paréntesis para el número dado N

Dado un número N , la tarea es insertar el número mínimo de paréntesis de apertura y cierre en el número N de modo que la string resultante esté equilibrada y cada dígito D esté exactamente en D pares de paréntesis coincidentes.

Ejemplos:

Entrada: N = 312
Salida: (((3))1(2))
Explicación:
Cada dígito en el número está exactamente entre paréntesis D.
Hay otras strings posibles como (((3)))(1)((2)) pero la string obtenida es la string que se puede formar con el mínimo número de paréntesis.

Entrada: N = 111000
Salida: (111)000
Explicación:
Cada dígito en el número está exactamente entre paréntesis D.
Hay otras strings posibles como (1)(1)(1)000, (11)(1)000 pero la string obtenida es la que se puede formar con el mínimo número de paréntesis.

Enfoque: la idea es utilizar una array para realizar un seguimiento de la cantidad de paréntesis que deben agregarse.

Para cualquier número, la cantidad mínima de paréntesis solo se puede agregar anidando los números dentro de los paréntesis.

Por ejemplo: sea N = 321.

• Inicialmente, se crea una array vacía A[].
• El número dado se itera en dígitos.
• Inicialmente, se agrega un número D de paréntesis de apertura en la array para almacenar el número. Por lo tanto, para el dígito 3, se agregan 3 corchetes de apertura en la array.
• En la siguiente iteración, el dígito puede ser mayor o menor que el dígito anterior. Si el siguiente dígito es más pequeño como 2 en el ejemplo anterior, 3 – 2 = 1 paréntesis están cerrados.
• Del mismo modo, si el dígito siguiente es mayor, se abre el número de paréntesis de la diferencia absoluta.
• Repita los dos pasos anteriores para todos los dígitos del número N dado. Finalmente, la string obtenida se forma con un número mínimo de paréntesis.

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

# Python program to find the balanced
# parentheses using the given number
  
# Function to find the balanced 
# parentheses using the given number
def balance(m):
  
    # Making the list of the
    # given number
    m = [int(i) for i in m]
  
    # Empty list to store the 
    # parentheses
    n = []
      
    # Iterating through the 
    # digits of the number
    for i in m: 
          
        # Calculating the difference between
        # opening and closing braces for the 
        # digit
        if (n.count('(')-n.count(')'))<= i:
  
            # If the next digit is greater, 
            # then open the brackets
            while (n.count('(')-n.count(')')) != i:
                n.append('(')         
            n.append(i)     
              
        # Similarly, find the difference 
        # between opening and closing braces
        elif (n.count('(')-n.count(')'))>i:
  
            # If the next digit is smaller,
            # then close the brackets
            while (n.count('(')-n.count(')'))!= i:
                n.append(')')
            n.append(i) 
              
    # Finally, close the remaining brackets
    while (n.count('(')-n.count(')'))!= 0:
        n.append(')')
      
    # Returning the string
    return ''.join(map(str, n))
      
# Driver code
if __name__ == "__main__":
      
    N = 312
      
    print(balance(str(N)))

(((3))1(2))

Complejidad Temporal: O(K ² ) , donde K es la suma de los dígitos del número N.