Там являются несколько вопросов на этом сайте о балансировании скобки, и проверок , является ли уравновешиваются скобки. Я предлагаю, что пришло время использовать эти сбалансированные скобки для чего-то!
В математике и программировании скобки похожи на пузыри, изолирующие все внутри от всего, что находится внутри, так что все, что внутри, может делать свое дело в мире, а то, что снаружи, видит только один объект. Тем не менее, цепочка скобок является одномерной, в то время как пузыри, как правило, по крайней мере двумерные. Это означает, что пузырьки могут свободно перемещаться друг относительно друга, если они никогда не касаются друг друга и не пересекаются между внутренней и внешней частью любых других пузырьков.
Вызов
Входные данные представляют собой строку совпадающих скобок одного типа: круглую ()
, квадратную []
, фигурную {}
или угловую <>
. Вам решать, какой тип вы хотите, чтобы ваша программа принимала, и программа, которая принимает только один вид скобок, принимается. (Воображаемый бонус, если ваша программа может обработать любой из них, огромные воображаемые бонусные баллы, если он может обрабатывать все их в одном входе.) Вход не может содержать ничего в скобках, хотя конечные пробелы разрешены.
Выходными данными являются все возможные реорганизации (в произвольном порядке, включая исходный ввод) тех скобок, которые дают одинаковую конфигурацию пузырьков, без двух одинаковых строк. Это означает, что при вводе ()()
, вывод также является простым ()()
, хотя технически это два пузыря, которые могут поменяться местами. Для огромного воображаемого бонуса, {}[]()
конечно , ввод воли приведет к выводу 6 различных элементов / строк / линий.
Две конфигурации пузырьков "одинаковы", если вы можете превратить один в другой, перемещая пузырьки, не позволяя ни одному пузырю пересекаться из другого пузырька наружу или снаружи внутрь. Если вы сравниваете вложенные скобки с деревьями (каждая совпавшая пара является одним узлом, и каждая совпавшая пара внутри является подузлом, и каждая совпавшая пара внутри имеет подузел тех же и т. Д.), Где подузлы любого данного узла упорядочены тогда единственная конфигурация пузырьков - это дерево, где узлы неупорядочены.
Любой разумный формат вывод будет делать, как и возвращает список строк или список списка отдельных символов или одной строки с каким - то пробелом, или печатью на stdout
или stderr
с какой - либо формой видимого символа пробела (обычно перевод строки или пробела) между каждая реорганизация.
Конечные пробелы для каждой реорганизации и конечные и предшествующие новые строки / пустые элементы списка до и после фактического вывода разрешены. Вы должны использовать такие же скобки в своем выводе, как и в своих. Кроме скобок, новых строк и пробелов, как указано здесь, и любого используемого разделителя, ничего не должно быть напечатано (включая невидимые символы / символы нулевой ширины).
Оценка - это количество байтов в коде; самый низкий счет для каждого языка выигрывает. Вы можете заметить, получаете ли вы воображаемый бонус, обычный или массовый, но это не влияет на ваш счет. Реальные бонусы слишком сложно сбалансировать правильно.
Примеры ввода-вывода
Пример 1:
Входные данные:
()(())
Выход:
()(())
(())()
Пример 2:
Входные данные:
(()())()()
Выход:
(()())()()
()(()())()
()()(()())
Пример 3:
Входные данные:
(()(()))()
Выход:
((())())()
()((())())
(()(()))()
()(()(()))
((()))
в примере 1? или()()()
? Кажется, вам не хватает перестановок для каждого входа.Ответы:
CJam , 18 байт
Попробуйте онлайн!
-2 благодаря Business Cat .
Получает входные данные в виде строки, содержащей только
[]
. Возвращает список перестановок (пустые списки такие же, как пустые строки в CJam, поэтому вместо них[]
вы получите""
).источник
[][]
всего""
? - Должен ли вход заключаться в дополнительный набор[]
? Если так, то почему существует дополнительный набор,[]
который (возможно?) Представляет собой вывод для вышеупомянутого примера? Кроме того, вопрос гласит: «Вы должны использовать в выводе те же скобки, что и в вводе. Помимо скобок, переносов и пробелов, как указано здесь, и независимо от того, какой разделитель вы используете, ничего не должно печататься», поэтому я ' Я не уверен, что сочетание[]
и""
является приемлемым.[][]
дополнительную пару[]
. Для других я не совсем уверен, что они недействительны._{{B}%e!}&
вместо_!!{{B}%e!}*
&
короткое замыкание или что-то?&
запускает блок, только если другое значение верноHaskell ,
227210208205 байтПопробуйте онлайн!
Этот был жестким!
Немного поиграл в гольф
Сохранено два байта благодаря Laikoni
Сэкономьте два байта благодаря Брюсу Форте
Я не уверен, что это работает в каждом случае. Некоторые объяснения:
a!x
добавить строкуx
в последний список строк вa
(тип a[[String]]
)snd$foldl(\(a,r)x->if x=='('then(a+1,last$(r++[[]]):[r!x|a>0])else(a-1,last$r:[r!x|a>1])
использует более короткое условное выражение для выражения простой идеи: разбить строку на корень)(
s. Например"(()(()))()"
дает["()(())", ""]
.Нам нужно обработать каждую часть разбиения, затем собрать и объединить все строки, чтобы получить правильный вывод:
h
обрабатывает список частей: он применяетсяv
к первой части и объединяет результат с процессом остальных частей.v
агрегирует результаты для каждой перестановки частей и удаляет дубликаты.Чтобы добавить более широкое представление: у вас есть в основном дерево (не двоичное) с пустыми узлами. Оставь это
()
. Вы должны произвести все перестановки ветвей для каждого узла, но вы не можете взять ветку из узла и поместить ее в другой узел. Я сделал своего рода углубленный первый поиск.источник
init a
.Python 2,
353350331 байтПолучает строку в
()
качестве входных данных и печатает результат.Попробуй это здесь!
Я избегал использовать
itertools.permutations
с помощью ответа Паоло на этот вопрос .Спасибо Business Cat за то, что он нашел 3 байта, и спасибо мистеру Xcoder за невероятные 19 байтов!
объяснение
()
пары во входной строке.()
парой.источник
print
и в таких местах, какi+1 if
(может бытьi+1if
). Кроме того, в одном месте выy[0:i]
можете опустить 0.JavaScript (Firefox 30-57), 222 байта
Принимает
[]
строки. Объяснение:источник
Mathematica, 337 байт
Не для того, чтобы получить очки для игры в гольф, но чтобы показать использование
Permutations
иDistribute
в этой проблеме. Хотя могут быть и лучшие подходы.(
seq
: последовательность,:alt
альтернативы)Возьмите ввод как строку, используя фигурные скобки
{
и}
. Выведите многострочную строку.источник