Patrzysz na aleję, a ktoś wyrzucił śmieci! Musisz napisać program, który pomoże rozwiązać problem, umieszczając kosz w koszach.
Zadanie
Aleja składa się z ciągu drukowalnych znaków ASCII, np .:
[[](dust)[]] car ((paper)vomit) (broken(glass)) [[] (rotten) fence (dirty)
Niektóre nawiasy tutaj nie mają sobie równych; to tylko wabiki. Dbamy o dopasowane zestawy nawiasów.
Kosza jest ciągiem zaczynając [
i kończąc ]
, i wewnętrznie dopasowane nawiasów i nawiasów. Na przykład, []
i [[](dust)[]]
są kosze na śmieci w powyższym ciągu.
Worek śmieci jest ciągiem zaczynając (
i kończąc )
, i wewnętrznie dopasowane nawiasów i nawiasów. Na przykład (dust)
jest worek na śmieci w powyższym sznurku.
Możliwe, że niektóre worki na śmieci są już w pojemnikach. Jednak przynajmniej jeden zostanie pominięty i musimy przenieść worki na śmieci, aby wszystkie znajdowały się w pojemnikach na śmieci. W szczególności dla każdego worka na śmieci, który nie znajduje się obecnie w koszu (tj. Podłoży tego kosza), musimy go usunąć z jego bieżącej lokalizacji w ciągu i zamiast tego wstawić do miejsca, które znajduje się w koszu .
Tutaj jest dodatkowa zasada. Ponieważ nie chcemy wydawać zbyt dużo pieniędzy na śmieciarki, a ich trasa wiedzie ich aleją od prawej do lewej, chcemy przenieść każdy worek na śmieci w lewo (najważniejsze kryterium, zakładając, że musimy go przenieść wszystkie) i najkrótszą możliwą odległość (o ile jest przesunięta w lewo). Na przykład jedyne prawidłowe wyjście dla
[can1](bag)[can2]
jest
[can1(bag)][can2]
(przesuwając torbę tylko jedną postać w lewo). Ponadto torby muszą pozostać w tej samej względnej kolejności:
[can](bag1)(bag2)
musi się stać
[can(bag1)(bag2)]
(tzn. nie możesz umieścić (bag2)
na lewo od (bag1)
.)
Wyjaśnienia
- Po lewej stronie lewej skrzynki na śmieci nie będzie żadnych worków na śmieci; zawsze będzie można zebrać wszystkie śmieci, przesuwając je w lewo.
- Zawsze będzie co najmniej jedna torba do przeniesienia. Może być więcej niż jeden.
- Nigdy nie będzie kosza na śmieci w koszu na śmieci (puszki są zbyt cenne, aby je wyrzucić).
- Jeśli worek znajduje się już w puszce, zostaw go w spokoju.
- Dopuszczalne jest, aby dane wejściowe i wyjściowe różniły się końcowymi spacjami (w tym znakami nowej linii).
Przykłady:
Wejście:
[[](dust)[]] car ((paper)vomit) (broken(glass)) [[] (rotten) fence (dirty)
Wynik:
[[](dust)[]((paper)vomit)(broken(glass))] car [[(rotten)(dirty)] fence
Wejście:
[]] (unusable) door (filthy) car
Wynik :
[(unusable)(filthy)]] door car
źródło
Odpowiedzi:
JavaScript (ES6),
263228209205184177173162 bajtówKażda pomoc związana z kodem / wyrażeniami regularnymi jest bardzo mile widziana.
Anonimowa funkcja; pobiera jeden
String
parametrs
i zwraca wynik./\[\[][\w()]*\[]]|\[]/g
pasuje do pojemników na śmieci z zagnieżdżonymi workami na śmieci, ale nie sądzę, aby w razie potrzeby sprawdził zrównoważone wsporniki w workach na śmieci.źródło