Biorąc pod uwagę poprawnie nawiasowany ciąg jako dane wejściowe, wypisz listę wszystkich niepustych podciągów w pasujących nawiasach (lub poza wszystkimi nawiasami), z usuniętymi nawiasami zagnieżdżonymi. Każdy podciąg powinien być ciągiem znaków w dokładnie tych samych pasujących nawiasach. Podciągi powinny być wymienione w kolejności od głębokości, a podciągi o tej samej głębokości powinny być wymienione w kolejności, w jakiej występują w ciągu. Załóżmy, że dane wejściowe są zawsze poprawnie nawiasowane.

Możesz założyć, że dane wejściowe zawierają tylko małe litery ASCII i nawiasy.

Twoja odpowiedź powinna być funkcją, która po podaniu łańcucha zwraca listę ciągów.

Przykłady:

                   'a(b)c(d)e' -> ['ace', 'b', 'd']
                   'a(b(c)d)e' -> ['ae', 'bd', 'c']
                  'a((((b))))' -> ['a', 'b']
                        'a()b' -> ['ab']
                            '' -> []
                           'a' -> ['a']
          '(((a(b)c(d)e)f)g)h' -> ['h', 'g', 'f', 'ace', 'b', 'd']
'ab(c(((d)ef()g)h()(i)j)kl)()' -> ['ab', 'ckl', 'hj', 'efg', 'i', 'd']

Wygrywa najmniej bajtów.

JavaScript ES6, 91 93 104 133 148 148

Edytuj2 2 bajty zapisane przez użytkownika 81655

Edycja Używanie większej liczby ciągów i mniej tablic

Przetestuj poniższy fragment kodu w przeglądarce zgodnej z EcmaScript 6

f=s=>[...s].map(c=>l+=c<')'||-(o[l]=(o[l]||'')+c,c<'a'),o=[],l=0)&&(o+'').match(/\w+/g)||[]

// Less golfed

u=s=>{
  o=[]; l=0;
  [...s].map(c=>{
    if (c>'(') // letters or close bracket
      o[l]=(o[l]||'')+c, // add letter or close bracket to current level string
      l-=c<'a' // if close bracket, decrement level
    else
      ++l // open bracket, increment level
  })
  o = o+'' // collapse array to comma separated string
  return o.match(/\w+/g)||[] // fetch non empty strings into an array
}

// TEST
console.log=x=>O.innerHTML+=x+'\n'

;[ 'a(b)c(d)e'                    // ['ace', 'b', 'd']
 , 'a(b(c)d)e'                    // ['ae', 'bd', 'c']
 , 'a((((b))))'                   // ['a', 'b']
 , 'a()b'                         // ['ab']
 , ''                             // []
 , 'a'                            // ['a']
 , '(((a(b)c(d)e)f)g)h'           // ['h', 'g', 'f', 'ace', 'b', 'd']
 , 'ab(c(((d)ef()g)h()(i)j)kl)()' // ['ab', 'ckl', 'hj', 'efg', 'i', 'd']
].forEach(t=>console.log(t +" -> " + f(t)))

<pre id=O></pre>

Julia, 117 86 83 bajtów

v->(while v!=(v=replace(v,r"(\(((?>\w|(?1))*)\))(.*)",s"\g<3> \g<2>"))end;split(v))

To rozwiązanie regularne.

Nie golfowany:

function f(v)
  w=""
  while v!=w
    w=v
    v=replace(v,r"(\(((?>\w|(?1))*)\))(.*)",s"\g<3> \g<2>"))
  end
  split(v)
end

r"(\(((?>\w|(?1))*)\))(.*)"jest (?1)wyrażeniem rekurencyjnym ( grupa rekurencyjna 1), które będzie pasowało do pierwszych najbardziej zrównoważonych nawiasów okrągłych (które nie zawierają niezrównoważonych / odwróconych nawiasów), przy czym druga grupa zawiera wszystko w nawiasach (bez samych nawiasów), a trzecia grupa zawiera wszystko po nawiasach (do końca łańcucha).

replace(v,r"...",s"\g<3> \g<2>")przeniesie następnie drugą grupę na koniec łańcucha (po spacji, aby działał jako separator), z usuniętymi odpowiednimi nawiasami. Iterując do v == w, zapewnione jest powtarzanie zamiany, dopóki nie pozostaną żadne nawiasy. Ponieważ dopasowania są przenoszone na koniec, a następnie następne dopasowanie przechodzi do pierwszego nawiasu, wynikiem będzie łańcuch podzielony w kolejności według głębokości.

Następnie splitzwraca wszystkie elementy niebiałych znaków ciągu w postaci tablicy ciągów (które nie mają białych znaków).

Zauważ, że w=""jest używany w kodzie bez golfa, aby upewnić się, że pętla while działa co najmniej raz (z wyjątkiem sytuacji, gdy łańcuch wejściowy jest oczywiście pusty) i nie jest potrzebny w formie golfa.

Podziękowania dla Martina Büttnera za pomoc w oszczędzaniu 3 bajtów.

Python, 147 bajtów

def f(s):
 d=0;r=[['']for c in s]
 for c in s:
  if c=='(':d+=1;r[d]+=['']
  elif c==')':d-=1
  else:r[d][-1]+=c
 return[i for i in sum(r,[])if i]

Testy jednostkowe:

assert f('a(b)c(d)e') == ['ace', 'b', 'd']
assert f('a(b(c)d)e') == ['ae', 'bd', 'c']
assert f('a((((b))))') == ['a', 'b']
assert f('a()b') == ['ab']
assert f('') == []
assert f('a') == ['a']
assert f('(((a(b)c(d)e)f)g)h') == ['h', 'g', 'f', 'ace', 'b', 'd']
assert f('ab(c(((d)ef()g)h()(i)j)kl)()') == ['ab', 'ckl', 'hj', 'efg', 'i', 'd']

Lubię tę łamigłówkę; to jest bardzo urocze!

Pyth, 32 bajty

fTscR)uX0.<GJ-FqLH`()@[Hdk)Jzmkz

Zestaw testowy

Luźno oparty na podejściu @ Quuxplusone. Tworzy oddzielone spacjami listy znaków na każdej głębokości, a następnie dzieli je i odfiltrowuje puste grupy. Lista robocza jest obracana, aby przez cały czas wyświetlać bieżącą listę głębokości.

Retina , 44 41 bajtów

+`\(((\w|(\()|(?<-3>.))*).(.*)
$4 $1
S_` 

Uruchom z -sflagą. Zwróć uwagę na spację na końcu ostatniego wiersza.

Wymyśliłem to rozwiązanie niezależnie od Glen O, ale okazało się, że jest identyczne. Chodzi o to, aby dopasować pierwszą parę nawiasów, usunąć ją i wstawić jej zawartość na końcu danych wyjściowych (wielokrotnie). Z powodu braku rekurencji .NET w wyrażeniu regularnym musiałem użyć grup równoważących, które są cztery bajty dłuższe.

Jeśli nie rozumiesz pierwszego wyrażenia regularnego, pozwól, że odniosę się do mojej SO odpowiedzi na temat równoważenia grup . Ponieważ wejście ma zagwarantowane prawidłowe nawiasy, możemy zapisać dwa bajty, dopasowując )z .zamiast \). Następnie po prostu dopasowujemy resztę ciągu (.*). $4 $1najpierw zapisuje wymienioną resztę ciągu (pomijając zarówno nawiasy, jak i ich treść), a następnie treść nawiasów po spacji. +`Mówi Retina powtarzać tę czynność aż łańcuch zatrzyma się zmienia (co zdarza się tylko raz wszystkie nawiasy zostały usunięte).

Puste nawiasy spowodują powstanie dwóch kolejnych spacji, więc w końcu dzielimy cały ciąg znaków na spacje ( S`aktywuje tryb podziału, a wyrażenie regularne jest pojedynczą spacją). Ta _opcja mówi Retinie, aby pomijała puste części podziału, więc nie uwzględniamy pustych wyników w danych wyjściowych.

Common Lisp, 160

(lambda(x)(labels((g(l)(cons(#1=format()"~(~{~A~}~)"(#2=remove-if'listp l))(mapcan #'g(#2#'atom l)))))(remove""(g(read-from-string(#1#()"(~A)"x))):test'equal))))

Może to być cztery bajty mniej, jeśli konwersja wielkości liter nie byłaby konieczna. Chodzi o to, aby dodać lewy i prawy nawias do każdej strony ciągu wejściowego, traktować go jako listę, napisać elementy najwyższego poziomu listy do ciągu, a następnie przetworzyć listy podrzędne w ten sam sposób.

Haskell, 114 112 111 bajtów

')'%(h:i:t)=("":i):t++[h]
'('%l=last l:init l
c%((h:i):t)=((c:h):i):t
g x=[a|a<-id=<<foldr(%)(x>>[[""]])x,a>""]

Przykład użycia: g "ab(c(((d)ef()g)h()(i)j)kl)()"->["ab","ckl","hj","efg","i","d"] .

Przechodzę do tyłu przez ciąg wejściowy. Pośrednia struktura danych jest listą ciągów znaków. Lista zewnętrzna jest na poziom, a lista wewnętrzna na grupę na poziomie, np. [["ab"],["ckl"],["hj"],["efg","i"],["d"]](Uwaga: lista rzeczywista zawiera wiele pustych ciągów pomiędzy nimi). Wszystko zaczyna się od szeregu pustych ciągów znaków równych długości danych wejściowych - więcej niż wystarczająco, ale i tak puste listy są odfiltrowywane. Listy zewnętrzne albo obracają się na (/ )albo dodają znak do elementu przedniego. )zakłada także nową grupę.

Edycja: @Zgarb znalazł bajt do zapisania.

Sed, 90 bajtów

:
s/^(\w*)\((.*)\n?(.*)/\1\n\3_\2/M
s/(\n\w*_)(\w*)\)(.*)/\3\1\2/M
t
s/[_\n]+/,/g
s/,$//

Wykorzystuje rozszerzone wyrażenia regularne ( -rflaga), co odpowiada +1 bajtowi. Używa to również rozszerzenia GNU ( Mflaga spolecenia).

Przykładowe użycie:

$ echo 'ab(c(((d)ef()g)h()(i)j)kl)()' | sed -r -f deparenthesize.sed
ab,ckl,hj,efg,i,d

Objaśnienie: Ponieważ sed nie obsługuje rzeczy takich jak rekursywne wyrażenia regularne, wymagana jest praca ręczna. Wyrażenie jest podzielone na wiele linii, z których każda reprezentuje poziom głębokości zagnieżdżenia. Poszczególne wyrażenia na tej samej głębokości (a zatem w tej samej linii) są oddzielone znakiem _. Skrypt działa przez ciąg wejściowy po jednym nawiasie. Pozostałe dane wejściowe są zawsze przechowywane na końcu wiersza, który odpowiada bieżącemu poziomowi zagnieżdżenia.

Python, 161 bajtów

Oto, co wymyśliłem, jedno-liniowe funkcjonalne rozwiązanie python:

p=lambda s:filter(None,sum([''.join([s[i]for i in range(len(s))if s[:i+1].count('(')-s[:i+1].count(')')==d and s[i]!=')']).split('(')for d in range(len(s))],[]))

Wyzwanie to zostało zainspirowane https://github.com/samcoppini/Definition-book , który generuje długi ciąg ze słowem zdefiniowanym w nawiasach. Chciałem napisać kod, który dawałby mi każde zdanie, bez nawiasów. Rozwiązanie funkcjonalne jest zbyt wolne, aby było skuteczne na długich łańcuchach, ale rozwiązania imperatywne (takie jak rozwiązanie @ Quuxplusone) są znacznie szybsze.