Cost mínim de parentitzar correctament (2) P10387

Donada una paraula composta només per parèntesis i claudàtors que obren i tanquen, s’hi poden fer dos tipus d’operacions:

• Girar l’orientació d’un parèntesi o d’un claudàtor. És a dir, es pot convertir ‘(’ en ‘)’, ‘)’ en ‘(’, ‘[’ en ‘]’, o ‘]’ en ‘[’. Això costa 1.

• Transformar un parèntesi en un claudàtor o a l’inrevés, sense canviar-ne l’orientació. És a dir, es pot convertir ‘(’ en ‘[’, ‘)’ en ‘]’, ‘[’ en ‘(’, o ‘]’ en ‘)’. Això costa 2.

Quin és el cost mínim de convertir una paraula donada en una parentització correcta? Per exemple, si la paraula és “](”, llavors es pot aconseguir la parentització correcta “[]” fent dos girs i una transformació, amb cost total 4.

Entrada

L’entrada consisteix en diversos casos. Cada cas consisteix en una paraula amb parèntesis i claudàtors que obren o tanquen. Totes les paraules tenen mides parells entre 2 i 100.

Sortida

Per a cada cas, escriviu el cost mínim de parentitzar correctament.

Pista

La solució esperada té cost temporal $\Theta\left(n^3 \right)$ i cost espacial $\Theta\left(n^2 \right)$.