Você está olhando para uma avenida e alguém deixou o lixo de fora! Você precisa escrever um programa para ajudar a resolver o problema, colocando o lixo em lixeiras.

A tarefa

A avenida é composta por uma sequência de caracteres ASCII imprimíveis, por exemplo:

[[](dust)[]] car ((paper)vomit) (broken(glass)) [[] (rotten) fence (dirty)

Alguns dos colchetes aqui são incomparáveis; esses são apenas chamarizes. O que nos preocupa são os conjuntos de colchetes correspondentes.

Uma lata de lixo é uma sequência que começa [e termina com ]e entre parênteses e parênteses. Por exemplo, []e [[](dust)[]]são latas de lixo na sequência acima.

Um saco de lixo é uma sequência que começa (e termina com ), e entre parênteses e parênteses. Por exemplo,(dust) é um saco de lixo na sequência acima.

É possível que alguns dos sacos de lixo já estejam em latas de lixo. No entanto, pelo menos um deles foi deixado de fora e precisamos mover os sacos de lixo para que estejam todos dentro de latas de lixo. Especificamente, para cada saco de lixo que não está atualmente dentro de uma lata de lixo (por exemplo, uma substring dessa lata de lixo), precisamos removê-lo de seu local atual na string e inseri-lo em um local dentro de uma lata de lixo .

Há uma regra adicional aqui. Como não queremos gastar muito dinheiro com coletores de lixo, e sua rota os leva pela avenida da direita para a esquerda, queremos mover cada saco de lixo para a esquerda (critério mais importante, supondo que tenhamos que movê-lo em tudo) e a menor distância possível (desde que movida para a esquerda). Por exemplo, a única saída correta para

[can1](bag)[can2]

é

[can1(bag)][can2]

(movendo a bolsa apenas um caracter para a esquerda). Além disso, as malas precisam permanecer na mesma ordem relativa:

[can](bag1)(bag2)

tem que se tornar

[can(bag1)(bag2)]

(ou seja, você não pode colocar (bag2)à esquerda de (bag1).)

Esclarecimentos

• Não haverá sacos de lixo à esquerda da lixeira mais à esquerda; sempre será possível colocar todo o lixo no lixo, movendo-o para a esquerda.
• Sempre haverá pelo menos uma bolsa para mover. Pode haver mais de um.
• Nunca haverá uma lata de lixo dentro de um saco de lixo (as latas são valiosas demais para serem jogadas fora).
• Se uma bolsa já estiver dentro de uma lata, deixe-a em paz.
• Não há problema em a entrada e a saída diferirem no espaço em branco à direita (incluindo novas linhas).

Exemplos:

• Entrada: [[](dust)[]] car ((paper)vomit) (broken(glass)) [[] (rotten) fence (dirty)

  Resultado: [[](dust)[]((paper)vomit)(broken(glass))] car [[(rotten)(dirty)] fence

• Entrada: []] (unusable) door (filthy) car

  Resultado : [(unusable)(filthy)]] door car

JavaScript (ES6), 263 228 209 205 184 177 177 173 162 162 bytes

Qualquer ajuda com o código / expressões regulares é muito apreciada.

f=s=>s.match(t=/\[\[][\w()]*\[]]|\[]/g,g=/\([\w()]*\)/g,i=0,u=s.split(t).filter(e=>e)).map(e=>e.substr(0,e.length-1)+u[i].match(g).join``+`]`+u[i++].replace(g,``)).join``

Uma função anônima; leva um Stringparâmetro,s e retorna a saída.

/\[\[][\w()]*\[]]|\[]/g corresponde a latas de lixo com sacos de lixo aninhados, no entanto, acho que não seria possível verificar colchetes equilibrados em sacos de lixo, se necessário.