Votre mission, si vous l'acceptez, consiste à ajouter le nombre minimum de parenthèses, d'accolades et de crochets pour que la chaîne donnée (contenant uniquement les parenthèses, les accolades et les crochets) ait une correspondance d'accolade correcte. Les liens des symboles ajoutés doivent être rompus en ayant la distance maximale entre les accolades appariées. Vous devez renvoyer une seule réponse correcte qui correspond à ces deux règles; D'autres liens, s'ils existent, peuvent être rompus comme bon vous semble.

Exemples:

input      output
                          // Empty String is a legal input
[          []             // Boring example
[()]       [()]           // Do nothing if there's nothing to be done
({{        ({{}})         // NOT (){}{} (0 + 0 + 0). Maximum distance is 4 + 2 + 0, ({{}})
[([{])]}   {[([{}])]}     // NOT [([])]{[([])]} or similar

Vous pouvez écrire un programme ou une fonction , recevoir l'entrée via STDIN en tant qu'argument chaîne à votre fonction, qui renvoie la sortie sous forme de chaîne ou l'imprime dans STDOUT (ou l'alternative la plus proche). Vous pouvez éventuellement inclure une seule nouvelle ligne de fin dans la sortie.

Vous pouvez supposer que la chaîne d'entrée ne comprend que les 6 caractères suivants (ou leur absence): [](){}(Vous n'avez pas besoin de prendre en charge <>)

Il s'agit du code-golf , le programme le plus court qui gagne. Les failles standard sont bien sûr interdites .

Python 2-198

J'espérais obtenir un peu plus de compréhension, mais je n'ai pas beaucoup de temps pour tester vraiment différentes façons de faire les choses.

s="()[]{}";f=s.find
def F(S):
 r=m=""
 for c in S:
    i=f(c)^1
    if i%2:m=c+m;r+=c
    else:
     for d in m:
        if d==s[i]:break
        r+=s[f(d)^1]
     else:r=s[i]+r+c
     m=m[1:]
 for c in m:r+=s[f(c)^1]
 return r

L'OP n'a pas inclus un exemple comme {[([{}])]}{[(avec des groupes adjacents), mais que cette fonctionnalité soit requise ou non, cela donne le bon{[([{}])]}{[]}

Haskell, 513

La fonction h. La version précédente ne donnait pas de réponses correctes pour "({{)["et"({{)}}"

import Control.Monad

m '('=')'
m '['=']'
m '{'='}'
m ')'='('
m ']'='['
m '}'='{'

data B=B Char[B]|N[B]|Z B Char[B]
instance Eq B where(==)a b=q a==q b
instance Ord B where(<=)a b=q a<=q b

w(B o s)=o:(s>>=w)++[m o]
v(N k)=k>>=w
n(B _ k)=(sum$n<$>k)+1
q(N k)=sum$n<$>k

u(Z(Z g pc pk) c k)=Z g pc(pk++[B c k])
u(Z(N pk) c k)=N(pk++[B c k])
t(N k)=N k
t z=t$u z

f z c|elem c "([{"=[Z z c[]]
f z@(Z p o k) c|m c==o=[u z]|2>1=(u$Z(Z p o [])(m c)k):f(u z)c
f (N k)c=[Z(N[])(m c)k]

h s=v.minimum$t<$>foldM f(N [])s