ANTECEDENTES

El problema de paréntesis es simple de entender pero la solución requiere un poco de creatividad. La parte de programación es sencilla ya que requiere únicamente manejo de cadenas. El problema puede verse como una extensión del problema clásico de revisar si una cadena de paréntesis es válida.

APROXIMACIONES

En este problema lo que se requiere es cambiar ciertas posiciones de la cadena de paréntesis, para lograr que la cadena resultante sea válida. Por tanto podría pensarse inicialmente en hacer cambios en cada una de las posiciones. Como en cada posición tendriamos como opción cambiar el paréntesis de sentido o dejarlo igual, una secuencia de cambios podría verse como un número binario. Entonces el algoritmo implicaría generar todos los posibles cambios que en este caso sería contar desde 1 hasta 2^{longitud(cadena)} y de todas esas opciones elegir la que implique el menor número de cambios.

Sin embargo esta solución no es eficiente para los rangos dados, ya que la cadena de paréntesis tiene una longitud máxima de 1000.

SOLUCIÓN

Una alternativa a la solución por fuerza bruta es la de realizar dos recorridos para corregir paréntesis no válidos. En el problema clásico la revisión de validez de una cadena se realiza haciendo un recorrido en el que cada vez que se encuentra un paréntesis '(' se incrementa un contador y cada vez que se encuentra un ')' se decrementa. Si en algún punto este contador se vuelve negativo indica que sobra al menos un paréntesis de tipo ')' y si al final este contador es mayor que cero implica que sobra al menos un paréntesis '('.

Entonces la solución propuesta hace un primer recorrido hacia adelante, en el que cada vez que este contador se hace negativo, se realiza un cambio de paréntesis ')' por uno '('. De esta forma al final de este primer recorrido tenemos una cadena en la que solamente habrá un posible exceso de paréntesis de tipo '('.

Luego un recorrido de atrás hacia adelante realizará el mismo proceso, pero en este paso corregirá los paréntesis de tipo '(' sobrantes. Al final de estos dos recorridos, el resultado es una cadena de paréntesis válidos.

Una cadena de paréntesis inválida se caracteriza porque existe un punto a partir del cual existe un exceso de paréntesis de uno u otro tipo. El proceso anteriormente descrito realiza una corrección de este tipo de problema.

CÓDIGO

Dentro del código la función que resuelve el problema es

Proceso()

Realiza el recorrido hacia adelante y hacia atrás guardando los cambios en el arreglo sol.

Duvier Alexander Zuluaga Mora

duvier@softhome.net