Czy są zamaskowane nawiasy?

12

Ktoś dał nam ciąg znaków, ale wszystkie znaki podobne do nawiasów zostały zmienione na normalne i nie wiemy, które, a nawet ile ich było. Wiemy tylko, że gdyby L1,L2,L3,...,LNbyły różnego rodzaju lewe nawiasy i R1,R2,R3,...,RNbyły różnymi odpowiednimi rodzajami prawym nawiasami, wszystkie byłyby odrębne (2N znaki odrębnych nawiasów), łańcuch byłby prawidłowy, jeśli jest jednym z (+ jest normalnym połączeniem łańcucha):

  • L1+X+R1,, L2+X+R2..., LN+X+RNgdzie Xjest prawidłowym ciągiem,

  • X+Y, gdzie Xi Ysą poprawnymi ciągami,

  • Dowolny pojedynczy znak, który nie jest znakiem nawiasu.

  • Pusty ciąg

Wiemy, że zaczęli od prawidłowego ciągu przed zmianą nawiasów i nie zmienili ich na żadne znaki, które już istniały w ciągu. Dla każdego przedziału istniała również co najmniej jedna para. Czy potrafisz odtworzyć, które postacie były pierwotnie lewą i prawą parą nawiasów (znajdź Lii Riprzestrzegaj podanych warunków)?

Wyprowadza pary znaków, które były nawiasami. Na przykład, jeśli (){}[]faktycznie są znakami nawiasów, możesz wyprowadzać (){}[]lub {}[]()lub [](){}, itd. Może być wiele sposobów, aby to zrobić dla łańcucha, wystarczy zwrócić jeden taki, aby nie było przypisania nawiasów z większą liczbą par (patrz przykłady). Zauważ, że ciąg wyjściowy powinien zawsze mieć parzystą długość.

Przykłady:

abcc- cnie może być nawiasem, ponieważ nie ma innej postaci z dwoma wystąpieniami, ale abmoże być parą nawiasów, więc wynik byłby dokładny ab.

fffff - jakikolwiek ciąg z co najwyżej jednym znakiem nie może zawierać nawiasów, więc zwrócisz pusty ciąg lub nic nie wyświetlisz.

aedbedebdcecdec - ten ciąg nie może zawierać nawiasów, ponieważ jest 1 a, 2 bs, 3 cs, 4 ds i 5 es, więc żadne dwa znaki nie występują tyle samo razy, co jest wymagane, aby mieć nawiasy.

abcd- Możliwe są zadania ab, cd, abcd, cdab, adbc, bcad, ac, ad, bci bd, (jak również pustego przydziału, które z nich), ale należy zwrócić jeden z najdłuższych zadań, więc musisz wrócić abcd, cdab, adbc, lub bcad.

aabbcc, abc- to obie mają ab, aci bcjako ważnych parach. Musisz zwrócić jedną z tych par, nieważne która.

abbac- aib mają taką samą liczbę znaków, ale nie mogą faktycznie działać, ponieważ jeden z nich występuje zarówno po lewej, jak i po prawej stronie wszystkich wystąpień drugiego. Nic nie zwracaj.

aabcdb- cdi absą dokładnie dwiema parami nawiasów, więc wyprowadzaj albo cdabalbo abcd.

abcdacbd- tylko jedna para może zostać osiągnięty na raz, ale ab, ac, bd, cd, i adsą wszystkie możliwe pary można powrócić. Bez względu na to, która para wybrać, ma instancji, gdzie jeden inny znak jest w nim, który zakazuje wszelkich innych par, z wyjątkiem przypadku ad, gdy inne pary bci cbnie są możliwe albo sam, a więc nie może być możliwe z ad.

To jest kod golfowy, więc wygrywa najkrótszy kod w bajtach. Dane wejściowe pochodzą ze STDIN, jeśli to możliwe dla twojego języka. Jeśli nie jest to możliwe, wskaż metodę wprowadzania w swojej odpowiedzi.

code-golf string balanced-string Fricative Melon
źródło
1
w przypadku danych wejściowych abcdwyjście adbcbyłoby również do przyjęcia, prawda?
Patrick Roberts,
Tak, dodałem to do przykładu.
Fricative Melon

Odpowiedzi:

4

Rubinowy, 373 bajtów

i=gets.chomp
b=[*(i.chars.group_by{|x|x}.group_by{|x,y|y.size}.map{|x|s=x[1].size
x[1][0...s-s%2].map{|x|x[0]}*''}*'').chars.each_slice(2)]
puts [*[*b.size.downto(1).map{|n|b.combination(n).map{|t|[t*'',(h=Hash[t]
s=[]
o=1
i.each_char{|c|s.push(c)if h.keys.include?c
(o=false if s.empty?||!h[s.pop].eql?(c))if h.values.include?c}
o ?s.empty?: o)]}}.find{|x|x[0][1]}][0]][0]

Ten wykorzystuje golfed wersję parsera stosu tutaj .

Prawdopodobnie można to jeszcze bardziej uprościć, ale nie sądzę, aby mój mózg mógł sobie z tym poradzić.

Wszystkie przypadki testowe: http://ideone.com/gcqDkK

Z białymi znakami: http://ideone.com/pLrsHg

Ungolfed (głównie): http://ideone.com/oM5gKX

Icy Defiance
źródło