Если в качестве входных данных правильно задана строка в скобках, выведите список всех непустых подстрок в соответствующих скобках (или за пределами всех скобок) с удалением вложенных скобок. Каждая подстрока должна быть последовательностью символов в одинаковых совпадающих скобках. Подстроки должны быть перечислены в порядке глубины, а подстроки той же глубины должны быть перечислены в порядке их появления в строке. Предположим, что входные данные всегда правильно заключены в скобки.
Вы можете предположить, что ввод содержит только строчные буквы ASCII и круглые скобки.
Ваш ответ должен быть функцией, которая при задании строки возвращает список строк.
Примеры:
'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']
Побеждает несколько байтов.
code-golf
string
parsing
balanced-string
redstonerodent
источник
источник
'i'
и'd'
в правильном порядке в последнем тесте?i
менее глубоко вложен, чемd
.Ответы:
JavaScript ES6, 91
93 104 133 148Edit2 2 байта сохранено thx user81655
Редактировать, используя больше строк и меньше массивов
Протестируйте приведенный ниже фрагмент в браузере, совместимом с EcmaScript 6
источник
c=>l+=c<')'||-(o[l]=(o[l]||'')+c,c<'a'),
.Юлия,
1178683 байтаЭто регулярное решение.
Ungolfed:
r"(\(((?>\w|(?1))*)\))(.*)"
является рекурсивным(?1)
регулярным выражением ( группа рекурсивов 1), которое будет соответствовать первым наиболее сбалансированным круглым скобкам (которые не содержат несбалансированные / обращенные круглые скобки), причем вторая группа содержит все внутри скобок (не включая сами скобки), а третья группа содержит все после скобок (до конца строки).replace(v,r"...",s"\g<3> \g<2>")
затем переместит вторую группу в конец строки (после пробела, чтобы действовать как разделитель), с удалением соответствующих скобок. Итерируя до v == w, гарантируется, что замена повторяется до тех пор, пока не останется скобок. Поскольку совпадения перемещаются в конец, а затем следующее совпадение идет для первой круглой скобки, результатом будет строка, разбитая в порядке глубины.Затем
split
возвращает все непробельные компоненты строки в виде массива строк (которые не имеют пробелов).Обратите внимание, что
w=""
он используется в коде ungolfed, чтобы убедиться, что цикл while выполняется хотя бы один раз (за исключением, разумеется, если строка ввода пустая) и не требуется в форме для игры в гольф.Спасибо Мартину Бюттнеру за помощь в сохранении 3 байтов.
источник
\w
вместо[^()]
.Python, 147 байт
Модульные тесты:
Мне нравится эта головоломка; это очень мило!
источник
Pyth, 32 байта
Тестирование
Свободно основанный на подходе @ Quuxplusone. Создает разделенные пробелами списки символов на каждой глубине, затем разбивает их и отфильтровывает пустые группы. Рабочий список вращается, чтобы сохранить список текущей глубины всегда впереди.
источник
Retina ,
4441 байтБеги с
-s
флагом. Обратите внимание на пробел в конце последней строки.Я придумал это решение независимо от Глена О, но оно оказалось идентичным. Идея состоит в том, чтобы сопоставить первую пару скобок, удалить ее и вставить ее содержимое в конец вывода (повторно). Из-за отсутствия рекурсии в .NET мне пришлось использовать группы балансировки, которые на четыре байта длиннее.
Если вы не понимаете первое регулярное выражение, позвольте мне направить вас к моему SO-ответу о балансировке групп . Так как вход гарантированно будет правильно круглыми скобками, мы можем сохранить два байт путем сопоставления
)
с.
вместо\)
. Затем мы просто сопоставляем остальную часть строки с(.*)
.$4 $1
сначала записывает указанную оставшуюся часть строки (без скобок и их содержимого), а затем содержимое скобок после пробела.+`
Говорит Retina повторить этот шаг , пока строка не перестает меняться (что случается только один раз все скобки были удалены).Пустые скобки приведут к двум последовательным пробелам, поэтому, наконец, мы разбиваем всю строку на пробелы (
S`
активирует режим разделения, а регулярное выражение представляет собой один пробел)._
Опция указывает Retina пропустить пустые части раскола, поэтому мы не включаем в пустые результаты в выходном сигнале.источник
Common Lisp, 160
Это может быть на четыре байта меньше, если преобразование регистра не требуется. Идея состоит в том, чтобы добавить левую и правую круглые скобки к каждой стороне входной строки, обработать ее как список, записать элементы верхнего уровня списка в строку, а затем обработать подсписки таким же образом.
источник
Haskell,
114112111 байтовПример использования:
g "ab(c(((d)ef()g)h()(i)j)kl)()"
->["ab","ckl","hj","efg","i","d"]
.Я иду назад через строку ввода. Промежуточная структура данных представляет собой список строк. Внешний список для уровня и внутренний список для группы в пределах уровня, например
[["ab"],["ckl"],["hj"],["efg","i"],["d"]]
(примечание: реальный список содержит много пустых промежуточных строк). Все начинается с количества пустых строк, равного длине ввода - более чем достаточно, но пустые списки все равно отфильтровываются. Внешние списки либо поворачивается на(
/)
или добавляет характер к переднему элементу.)
также начинает новую группу.Редактировать: @Zgarb нашел байт для сохранения.
источник
Sed, 90 байт
Использует расширенные регулярные выражения (
-r
флаг), на которые приходится +1 байт. Также для этого используется расширение GNU (M
флаг вs
команде).Пример использования:
Объяснение: Поскольку sed не поддерживает такие вещи, как рекурсивные регулярные выражения, требуется ручная работа. Выражение разбито на несколько строк, каждая из которых представляет уровень глубины вложения. Отдельные выражения на одной и той же глубине (и, следовательно, на одной и той же строке) разделяются знаком
_
. Скрипт обрабатывает входную строку по одной скобке за раз. Остальные входные данные всегда сохраняются в конце строки, которая соответствует текущему уровню вложенности.источник
Python, 161 байт
Вот то, что я придумал, однострочное функциональное решение Python:
Эта проблема была вдохновлена https://github.com/samcoppini/Definition-book , которая выводит длинную строку со словом, определенным в скобках. Я хотел написать код, который давал бы мне каждое предложение со снятыми скобками. Функциональное решение слишком медленное, чтобы быть эффективным на длинных строках, но императивные решения (такие как решение @ Quuxplusone) намного быстрее.
источник