Вы смотрите на проспект, и кто-то оставил мусор! Вам нужно написать программу, которая поможет решить проблему, поместив мусорную корзину в мусорные баки.

Задание

Проспект состоит из строки печатных символов ASCII, например:

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

Некоторые из скобок здесь не имеют себе равных; это просто приманки. Что нас волнует, так это соответствующие наборы скобок.

Мусорный бак представляет собой строку , начиная с [и заканчивая ], и внутренне согласованных скобок и скобок. Например, []и [[](dust)[]]мусорные баки в приведенной выше строке.

Мешок для мусора является строкой , начиная с (и заканчивая ), и внутренне согласованные скобками и скобками. Например, (dust)мешок для мусора в строке выше.

Возможно, некоторые мешки для мусора уже находятся в мусорных баках. Однако, по крайней мере, один из них будет пропущен, и нам нужно переместить мешки для мусора так, чтобы они все были внутри мусорных баков. В частности, для каждого мешка для мусора, который в данный момент не находится в мусорном ведре (т.е. подстроке этого мусорного ведра), нам нужно удалить его из его текущего местоположения в строке и вместо этого вставить его в местоположение, которое находится внутри мусорного ведра. ,

Здесь есть дополнительное правило. Поскольку мы не хотим тратить слишком много денег на сборщики мусора, а их маршрут проходит по проспекту справа налево, мы хотим переместить каждый мешок для мусора влево (самый важный критерий, если предположить, что мы должны переместить его в все) и кратчайшее возможное расстояние (если оно перемещено влево). Так, например, единственный правильный вывод для

[can1](bag)[can2]

является

[can1(bag)][can2]

(перемещая сумку только на один символ влево). Кроме того, сумки должны оставаться в том же порядке:

[can](bag1)(bag2)

должен стать

[can(bag1)(bag2)]

(т.е. вы не можете поставить (bag2)слева от (bag1).)

Разъяснения

• Там не будет никаких мешков для мусора слева от самого левого мусорного ведра; всегда можно будет собрать весь мусор, переместив его влево.
• Всегда будет хотя бы одна сумка для перемещения. Там может быть больше, чем один.
• Внутри мешка для мусора никогда не будет мусорного бака (банки слишком ценны, чтобы их просто выбросить).
• Если сумка уже находится внутри банки, просто оставьте ее в покое.
• Это нормально для ввода и вывода, чтобы отличаться в конце пробела (включая переводы строки).

Примеры:

• Входные данные: [[](dust)[]] car ((paper)vomit) (broken(glass)) [[] (rotten) fence (dirty)

  Вывод: [[](dust)[]((paper)vomit)(broken(glass))] car [[(rotten)(dirty)] fence

• Входные данные: []] (unusable) door (filthy) car

  Вывод : [(unusable)(filthy)]] door car

JavaScript (ES6), 263 228 209 205 184 177 173 162 байта

Любая помощь с кодом / регулярные выражения очень ценится.

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``

Анонимная функция; принимает один Stringпараметр sи возвращает результат.

/\[\[][\w()]*\[]]|\[]/g сопоставляет мусорные баки с вложенными мусорными пакетами, однако я не думаю, что при необходимости можно было бы проверить сбалансированные скобки внутри мусорных пакетов.