Na tej stronie znajduje się kilka pytań dotyczących równoważenia nawiasów i sprawdzania, czy nawiasy są zrównoważone. Proponuję, że teraz nadszedł czas, aby użyć tych zrównoważonych nawiasów do czegoś!

W matematyce i programowaniu nawiasy kwadratowe są jak bańki, izolując wszystko w środku od wszystkiego na zewnątrz, dzięki czemu wszystko, co jest w środku, może robić swoje w spokoju, a wszystko na zewnątrz widzi tylko jeden obiekt. Jednak ciąg nawiasów jest jednowymiarowy, podczas gdy bąbelki zwykle są co najmniej dwuwymiarowe. Oznacza to, że bąbelki mogą się swobodnie przemieszczać wokół siebie, o ile nigdy się nie dotykają ani nie przechodzą między wnętrzem a zewnętrzem innych pęcherzyków.

Wyzwanie

Dane wejściowe to ciąg pasujących nawiasów pojedynczego typu, okrągłych (), kwadratowych [], kręconych {}lub kątowych <>. Od Ciebie zależy, jaki program chcesz zaakceptować, a program, który akceptuje tylko jeden rodzaj nawiasów, jest akceptowany. (Imaginacyjny bonus, jeśli twój program może obsłużyć którykolwiek z nich, ogromne wymyślone punkty bonusowe, jeśli może obsłużyć je wszystkie na tym samym wejściu.) Dane wejściowe nie mogą zawierać niczego między nawiasami, chociaż dozwolone są końcowe białe spacje.

Wyjściem są wszystkie możliwe reorganizacje (w dowolnej kolejności, w tym oryginalne dane wejściowe) tych nawiasów, które dają tę samą konfigurację bąbelków, bez dwóch identycznych ciągów. Oznacza to, że przy wejściu ()()wartość wyjściowa jest również sprawiedliwa ()(), chociaż technicznie są to dwa bąbelki, które mogłyby zamieniać się miejscami. W przypadku ogromnej wymyślonej premii wejście {}[]()woli prowadzi oczywiście do uzyskania 6 różnych elementów / ciągów / linii.

Dwie konfiguracje bąbelków są „takie same”, jeśli możesz zrobić jeden do drugiego, przesuwając bąbelki, nie pozwalając, aby jakikolwiek bąbelek przeciął się z innego bąbla na zewnątrz lub z zewnątrz do wewnątrz. Jeśli porównasz zagnieżdżone nawiasy do drzew (każda dopasowana para jest jednym węzłem, a każda dopasowana para w obrębie jest podwęzłem, a każda dopasowana para w obrębie jest ponownie podwęzłem itd.), Gdzie uporządkowane są podwęzły dowolnego danego węzła , wówczas pojedyncza konfiguracja bąbelków to drzewo, w którym węzły są nieuporządkowane.

Dowolny rozsądny format wyjściowy, na przykład zwrócenie listy ciągów znaków lub listy pojedynczych znaków lub pojedynczego ciągu znaków z pewnego rodzaju białymi spacjami , lub drukowanie do stdoutlub stderrz jakąś formą widocznych białych znaków (najczęściej nowa linia lub spacja) pomiędzy każda reorganizacja.

Końcowe spacje dla każdej reorganizacji oraz końcowe i poprzedzające elementy nowej linii / pustej listy przed i po dozwoleniu rzeczywistych wyników. Powinieneś używać tego samego rodzaju nawiasów wyjściowych, co akceptujesz w danych wejściowych. Poza nawiasami, znakami nowej linii i spacjami, jak określono tutaj, i niezależnie od użytego separatora, nic nie powinno być drukowane (w tym znaki niewidoczne / o zerowej szerokości).

Wynik to liczba bajtów w kodzie; najniższa liczba wygranych dla każdego języka. Możesz zauważyć, czy otrzymasz wymyśloną premię, zwykłą czy ogromną, ale nie wpływa to na twój wynik. Rzeczywiste bonusy są zbyt trudne do zrównoważenia.

Przykłady przepływów międzygałęziowych

Przykład 1:

Wkład:

()(())

Wydajność:

()(())
(())()

Przykład 2:

Wkład:

(()())()()

Wydajność:

(()())()()
()(()())()
()()(()())

Przykład 3:

Wkład:

(()(()))()

Wydajność:

((())())()
()((())())
(()(()))()
()(()(()))

CJam , 18 bajtów

{~{_{{B}%e!}&}:B~}

Wypróbuj online!

-2 dzięki Business Cat .

Odbiera dane wejściowe jako ciąg zawierający tylko []. Zwraca listę permutacji (puste listy są takie same jak puste ciągi w CJam, więc zamiast tego []będziesz otrzymywać "").

Haskell , 227 210 208 205 bajtów

import Data.List
l=last
a!x=init a++[l a++[x]]
h[]=[""]
h(x:y)=["("++z++")"++t|z<-v x,t<-h y]
g(a,r)x|x=='('=(a+1,l$(r++h[]):[r!x|a>0])|1>0=(a-1,l$r:[r!x|a>1])
v s=nub$h=<<(permutations.snd$foldl g(0,[])s)

Wypróbuj online!

Ten był trudny!

Trochę grałem w golfa

Zaoszczędzono dwa bajty dzięki Laikoni

Zaoszczędź dwa bajty dzięki Bruce Forte

Nie jestem pewien, czy to działa w każdym przypadku. Kilka wyjaśnień:

• a!xdodaj ciąg xdo ostatniej listy ciągu w a(a jest typu [[String]])

• snd$foldl(\(a,r)x->if x=='('then(a+1,last$(r++[[]]):[r!x|a>0])else(a-1,last$r:[r!x|a>1])używa krótszego warunku do wyrażenia prostej idei: podziel ciąg na root )( . Np . "(()(()))()"Daje ["()(())", ""].

• Musimy przetworzyć każdą część podziału, a następnie zebrać i połączyć wszystkie ciągi, aby uzyskać poprawny wynik:

  1. hprzetwarza listę części: dotyczy vpierwszej części i łączy wynik z procesem pozostałych części.

  2. v agreguje wyniki dla każdej permutacji części i usuwa duplikaty.

Aby dodać szerszy widok: masz w zasadzie drzewo (nie binarne) z pustymi węzłami. Zostaw to (). Musisz wygenerować wszystkie permutacje gałęzi dla każdego węzła, ale nie możesz pobrać gałęzi z węzła i umieścić go w innym węźle. Najpierw przeprowadziłem coś w rodzaju głębokości.

Python 2, 353 350 331 bajtów

s=input()
f=lambda i,t=0:i+1if t<0else f(i+1,t-1)if"("<s[i+1]else f(i+1,t+1)
c=[(x,f(x))for x in range(len(s))if")">s[x]]
p=lambda l:[[]]if len(l)<1else[x for y in p(l[1:])for x in[y[:i]+[l[0]]+y[i:]for i in range(len(y)+1)]]
print[''.join(x)for x in p([s[c[x][0]:c[x][1]]for x in range(len(c))if all(c[x][1]>y[1]for y in c[:x])])]

Odbiera ciąg ()wejściowy i wyświetla wynik.

Wypróbuj tutaj!

Unikałem korzystania itertools.permutationsz pomocy Paolo w odpowiedzi na to pytanie .

Dziękujemy Business Cat za znalezienie 3 bajtów i dziękuję Panu Xcoder za niewiarygodne 19 bajtów!

Wyjaśnienie

1. Utwórz listę krotek indeksów każdej ()pary w ciągu wejściowym.
2. Upuść krotki z listy, które są otoczone inną ()parą.
3. Pokrój ciąg według wskaźników pozostałych krotek.
4. Zrób listę każdej permutacji z listy plasterków.
5. Dołącz do listy z nową linią do drukowania.

JavaScript (Firefox 30-57), 222 bajty

s=>(g=a=>a+a?[for(x of g(a[0]))for(y of a.keys())for(z of g(a.slice(1)))(z.splice(y,0,x),z)]:[a])(eval(`[${s.replace(/]\[/g,`],[`)}]`)).map(g=a=>`[`+a.map(g).join``+`]`).sort().filter(s=>t<(t=s),t=``).map(s=>s.slice(1,-1))

Bierze []sznurki. Wyjaśnienie:

s=>(                                Inner function to permute an array
 g=a=>a+a?[                         If array is not empty
  for(x of g(a[0]))                 Permute the first element of the array
  for(y of a.keys())                Generate a list of insertion points
  for(z of g(a.slice(1)))           Permute the rest of the array
  (z.splice(y,0,x),z)]:             Make all possible permutations
  [a]                               Otherwise return a list of an empty array
)(eval(`[${                         Convert the string to a nested array
   s.replace(/]\[/g,`],[`)}]`)      ... inserting commas where necessary
).map(                              Process the results
 g=a=>`[`+a.map(g).join``+`]`       Recursively convert back to string
).sort().filter(s=>t<(t=s),t=``     Check for duplicates
).map(s=>s.slice(1,-1))             Remove outer `[]`s

Mathematica, 337 bajtów

Nie po to, żeby zdobyć punkty do gry w golfa, ale by pokazać wykorzystanie Permutations i Distributew tym problemie. Mogą być jednak lepsze podejścia.

( seq: sekwencja,alt alternatywy)

SetAttributes[alt, {Flat, OneIdentity}]
StringTake[
  StringReplace[ToString[
    ToExpression["{" <> StringReplace[#, "}{" -> "},{"] <> "}"]
        /. List -> Permutations@*seq
       /. List -> alt
      /. seq -> (Distribute[seq@##, alt] &)
     /. {seq -> List, alt -> Alternatives}],
   {", " -> "", "} | {" -> "\n"}],
  {2, -2}] &

Weź dane jako ciąg znaków, używając nawiasów klamrowych {i }. Wyjście ciągu wieloliniowego.