¡Estás mirando una avenida y alguien ha dejado la basura! Necesita escribir un programa para ayudar a solucionar el problema, colocando la basura en botes de basura.
La tarea
La avenida está compuesta por una cadena de caracteres ASCII imprimibles, por ejemplo:
[[](dust)[]] car ((paper)vomit) (broken(glass)) [[] (rotten) fence (dirty)
Algunos de los corchetes aquí no tienen comparación; esos son solo señuelos. Lo que nos importa son los conjuntos de soportes combinados.
Una papelera es una cadena que comienza [
y termina con ]
, y con paréntesis y corchetes coincidentes internamente. Por ejemplo, []
y [[](dust)[]]
son botes de basura en la cadena anterior.
Una bolsa de basura es una cadena que comienza (
y termina con )
, y con paréntesis y paréntesis internos. Por ejemplo, (dust)
es una bolsa de basura en la cadena anterior.
Es posible que algunas de las bolsas de basura ya estén en botes de basura. Sin embargo, al menos uno habrá quedado fuera, y necesitamos mover las bolsas de basura para que estén todas dentro de los botes de basura. Específicamente, para cada bolsa de basura que actualmente no se encuentra dentro de un bote de basura (es decir, una subcadena de ese bote de basura), debemos eliminarla de su ubicación actual en la cadena e insertarla en una ubicación que esté dentro de un bote de basura. .
Hay una regla adicional aquí. Debido a que no queremos gastar demasiado dinero en recolectores de basura, y su ruta los lleva a lo largo de la avenida de derecha a izquierda, queremos mover cada bolsa de basura a la izquierda (criterio más importante, suponiendo que tengamos que moverlo a todos) y la distancia más corta posible (siempre que se mueva hacia la izquierda). Entonces, por ejemplo, la única salida correcta para
[can1](bag)[can2]
es
[can1(bag)][can2]
(moviendo la bolsa solo un personaje hacia la izquierda). Además, las bolsas deben permanecer en el mismo orden relativo:
[can](bag1)(bag2)
tiene que convertirse
[can(bag1)(bag2)]
(es decir, no se puede poner (bag2)
a la izquierda de (bag1)
)
Aclaraciones
- No habrá bolsas de basura a la izquierda del bote de basura más a la izquierda; siempre será posible tirar toda la basura moviéndola hacia la izquierda.
- Siempre habrá al menos una bolsa para mover. Puede haber más de uno.
- Nunca habrá un bote de basura dentro de una bolsa de basura (las latas son demasiado valiosas para tirarlas).
- Si una bolsa ya está dentro de una lata, simplemente déjela sola.
- Está bien que la entrada y la salida difieran en los espacios en blanco finales (incluidas las nuevas líneas).
Ejemplos:
Entrada:
[[](dust)[]] car ((paper)vomit) (broken(glass)) [[] (rotten) fence (dirty)
Salida:
[[](dust)[]((paper)vomit)(broken(glass))] car [[(rotten)(dirty)] fence
Entrada:
[]] (unusable) door (filthy) car
Salida:
[(unusable)(filthy)]] door car
fuente
Respuestas:
JavaScript (ES6),
263228209205184177173162 bytesCualquier ayuda con el código / expresiones regulares es muy apreciada.
Una función anónima; toma un
String
parámetro,s
y devuelve la salida./\[\[][\w()]*\[]]|\[]/g
hace coincidir los botes de basura con bolsas de basura anidadas, sin embargo, no creo que pueda verificar los corchetes equilibrados dentro de las bolsas de basura si es necesario.fuente