Napraw aparat ortodontyczny itp

15

Twoim zadaniem, należy wybrać, aby go zaakceptować, jest dodanie do minimum liczbę nawiasów, szelki i wsporników, aby dany ciąg (zawierający tylko nawiasy, szelki i uchwyty) posiadają odpowiedni dobór nawiasów. Dodane powiązania symboli należy przerwać, zachowując maksymalną odległość między sparowanymi nawiasami klamrowymi. Musisz zwrócić tylko jedną poprawną odpowiedź, która pasuje do tych dwóch zasad; Dalsze więzi, jeśli istnieją, mogą zostać zerwane w dowolny sposób.

Przykłady:

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

Możesz napisać program lub funkcję , odbiera dane wejściowe przez STDIN jako argument ciągu do swojej funkcji, która zwraca dane wyjściowe jako ciąg znaków lub wypisuje je do STDOUT (lub najbliższej alternatywy). Opcjonalnie możesz dołączyć jeden końcowy znak nowej linii do wyniku.

Możesz założyć, że ciąg wejściowy składa się tylko z następujących 6 znaków (lub ich brak): [](){}(Nie musisz obsługiwać <>)

To jest golf golfowy , wygrywa najkrótszy program. Oczywiście standardowe luki są zabronione .

code-golf string balanced-string durron597
źródło
Czy chciałeś powtórzyć tytuł bezpośrednio pod faktycznym tytułem, czy powtórzyć tag bezpośrednio nad rzeczywistymi tagami? Tylko pytam na wypadek, gdybyś skopiował wklejony z piaskownicy i zapomniał je usunąć.
Rainbolt
@Rainbolt Pierwsze nie (piaskownica), drugie tak
durron597
1
@AlexA. Widzę, jak różnią się one na drobne sposoby, ale myślę, że są zbyt podobne, aby można je było traktować jako osobne pytania.
NinjaBearMonkey
Słusznie. Z pewnością nie jest to wycinanka i suchość i nie będę dążył do zamknięcia go, jeśli inni zdecydują się tego nie robić.
NinjaBearMonkey
Uważałbym to za wystarczająco inne. Zagłosowano ponownie otworzyć.
nderscore

Odpowiedzi:

1

Python 2 - 198

Miałem nadzieję, że trochę bardziej zrozumiem to rozumienie, ale nie mam teraz dużo czasu na przetestowanie różnych sposobów działania.

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

OP nie zawierał takiego przykładu {[([{}])]}{[(z sąsiednimi grupami), ale to, czy ta funkcjonalność jest wymagana, daje prawidłowe wyniki{[([{}])]}{[]}

KSab
źródło
Jak to jest 198 bajtów?
Zacharý
@ZacharyT, tabs ( \t) są sformatowane jako 4 spacje po przepełnieniu stosu, ale tak naprawdę zmieniam tabulacje i spacje (możesz to zrobić dla poziomów wcięcia w Pythonie 2, a nie 3), więc pierwszy poziom to [space]drugi, [tab]trzeci to [tab][space]czwarty, to czwarty [tab][tab]. Wpisanie kodu spacjami daje mi 227 stąd mothereff.in/byte-counter , a ja liczę 10 tabulatorów, więc 227 - (3 * 10) = 197. Huh, chyba tak naprawdę przeliczyłem się o jedną drogę wstecz, kiedy wysłał to.
KSab,
NIEBEZPIECZEŃSTWO! To naprawdę dobra sztuczka. (Wpisz na końcu wiersza). Możesz połączyć dolną pętlę for i instrukcję return, return r+[s[f(c)^1]for c in m]aby zapisać bajty.
Zacharý
1

Haskell, 513

Funkcja h. Poprzednia wersja nie zawierała poprawnych odpowiedzi dla "({{)["i"({{)}}"

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
Matt
źródło