Dada uma entrada entre parênteses corretamente, digite uma lista de todas as substrings não vazias entre parênteses correspondentes (ou fora de todos os parênteses), com os parênteses aninhados removidos. Cada substring deve ter a sequência de caracteres exatamente nos mesmos parênteses correspondentes. As seqüências de caracteres devem ser listadas em ordem de profundidade e as da mesma profundidade devem ser listadas na ordem em que ocorrem na sequência. Suponha que a entrada esteja sempre entre parênteses corretamente.

Você pode supor que a entrada contenha apenas letras ASCII em minúsculas e parênteses.

Sua resposta deve ser uma função que, quando recebe uma string, retorna uma lista de strings.

Exemplos:

                   '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']

Menos bytes ganha.

JavaScript ES6, 91 93 104 133 148

Edit2 2 bytes salvos thx user81655

Editar Usando mais strings e menos matrizes

Teste a execução do snippet abaixo em um navegador compatível com 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 bytes

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

É uma solução regex.

Ungolfed:

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))*)\))(.*)"é um (?1)regex recursivo ( grupo de repetições 1) que corresponderá aos primeiros parênteses mais externos balanceados (que não contêm parênteses desequilibrados / revertidos), com o segundo grupo contendo tudo dentro dos parênteses (sem incluir os parênteses) e o terceiro grupo contendo tudo depois dos parênteses (até o final da string).

replace(v,r"...",s"\g<3> \g<2>")moverá o segundo grupo para o final da sequência (após um espaço, para atuar como um delimitador), com os parênteses relevantes removidos. Ao iterar até v == w, é garantido que a substituição seja repetida até que não haja parênteses. Como as correspondências são movidas para o final e a próxima correspondência segue para o primeiro parêntese, o resultado será a sequência dividida em ordem de profundidade.

Em seguida, splitretorna todos os componentes sem espaço em branco da cadeia de caracteres na forma de uma matriz de cadeias de caracteres (que não possuem espaço em branco).

Observe que w=""é usado no código não-bloqueado para garantir que o loop while seja executado pelo menos uma vez (exceto se a sequência de entrada estiver vazia, é claro) e não é necessária na forma de golf.

Agradecemos a Martin Büttner pela ajuda na economia de 3 bytes.

Python, 147 bytes

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]

Testes unitários:

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']

Eu gosto desse quebra-cabeça; é muito fofo!

Pitão, 32 bytes

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

Suíte de teste

Basicamente baseado na abordagem da @ Quuxplusone. Constrói listas separadas de espaço dos caracteres em cada profundidade, depois as divide e filtra os grupos vazios. A lista de trabalho é rotacionada para manter a lista de profundidade atual sempre à frente.

Retina , 44 41 bytes

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

Corra com a -sbandeira. Observe o espaço no final da última linha.

Eu vim com essa solução independentemente do Glen O, mas ela é idêntica. A idéia é combinar o primeiro par de parênteses, removê-lo e inserir seu conteúdo no final da saída (repetidamente). Devido à falta de recursão do .NET no regex, tive que usar grupos de balanceamento, que são quatro bytes mais longos.

Se você não entender o primeiro regex, deixe-me encaminhá-lo para minha resposta de SO sobre grupos de balanceamento . Como a entrada é garantida entre parênteses corretamente, podemos salvar dois bytes combinando )com em .vez de \). Então simplesmente combinamos o resto da string com (.*). $4 $1primeiro escreve de volta o restante da string (omitindo os parênteses e seu conteúdo) e depois o conteúdo dos parênteses após um espaço. O +`instrui o Retina a repetir essa etapa até que a string pare de mudar (o que só acontece quando todos os parênteses foram removidos).

Parênteses vazios resultarão em dois espaços consecutivos; portanto, finalmente dividimos a sequência inteira em espaços ( S`ativa o modo de divisão e o regex é um espaço único). A _opção informa ao Retina para omitir partes vazias da divisão, para que não incluamos os resultados vazios na saída.

Lisp comum, 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))))

Isso pode ter quatro bytes a menos se a conversão de caso não for necessária. A idéia é adicionar parênteses esquerdo e direito a cada lado da string de entrada, tratá-la como uma lista, gravar os elementos de nível superior da lista em uma string e processar as sublistas da mesma maneira.

Haskell, 114 112 111 bytes

')'%(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>""]

Exemplo de uso: g "ab(c(((d)ef()g)h()(i)j)kl)()"-> ["ab","ckl","hj","efg","i","d"].

Eu estou indo para trás através da string de entrada. A estrutura de dados intermediária é uma lista de lista de strings. A lista externa é por nível e a lista interna é por grupo dentro de um nível, por exemplo [["ab"],["ckl"],["hj"],["efg","i"],["d"]](nota: a lista real possui várias cadeias vazias no meio). Tudo começa com um número de cadeias vazias iguais ao comprimento da entrada - mais do que suficiente, mas as listas vazias são filtradas de qualquer maneira. As listas externas tanto gira em (/ )ou acrescenta o personagem para o elemento frontal. )também inicia um novo grupo.

Edit: @Zgarb encontrou um byte para salvar.

Sed, 90 bytes

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

Usa expressões regulares estendidas ( -rsinalizador), representadas por +1 byte. Além disso, isso usa uma extensão GNU (a Mbandeira no scomando).

Uso da amostra:

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

Explicação: Como o sed não suporta itens como expressões regulares recursivas, é necessário trabalho manual. A expressão é dividida em várias linhas, cada uma representando um nível de profundidade de aninhamento. As expressões individuais na mesma profundidade (e, portanto, na mesma linha) são separadas por um _. O script funciona através da string de entrada, um colchete por vez. A entrada restante é sempre mantida no final da linha que corresponde ao nível de aninhamento atual.

Python, 161 bytes

Aqui está o que eu criei, uma solução python funcional de uma linha:

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))],[]))

Esse desafio foi inspirado em https://github.com/samcoppini/Definition-book , que gera uma sequência longa com a palavra definida entre parênteses. Eu queria escrever um código que me desse cada frase, com os parênteses removidos. A solução funcional é lenta demais para ser eficaz em seqüências longas, mas soluções imperativas (como a solução da @ Quuxplusone) são muito mais rápidas.