Свести программу стека кошек

13

Stack Cats - это обратимый, основанный на стеке язык. Его обратимый характер создает несколько странные петли. Эта проблема об условном цикле (...). Когда эти циклы вложены определенным образом, можно преобразовать код, чтобы уменьшить глубину вложенности. Вот правила (где Aи Bобозначают произвольные фрагменты):

  1. Когда один цикл начинается с другого цикла, мы можем извлечь внутренний цикл вперед: ((A)B)становится (A)(B).
  2. Когда один цикл заканчивается другим циклом, мы можем извлечь внутренний цикл до конца: (B(A))становится (B)(A).
  3. Пустые циклы ()можно полностью удалить из программы. Как следствие (в сочетании с другими правилами), ((A))эквивалентно (A).

Единственные вложенные циклы , которые останутся имеют вид (A(B)C), где A, Bи Cне пусты.

Соревнование

Вам дана действующая программа Stack Cats, и ваша задача - максимально снизить уровень вложенности циклов, не оставляя пустых циклов, используя приведенные выше преобразования.

Действительная программа Stack Cats ...

  • ... состоит только из персонажей ()/\<>[]{}!"*+-:=ITX^_|.
  • ... имеет зеркальную симметрию (например, \(]{}!{}[)/является допустимой программой, но /|/не является).
  • ... правильно подобран и вложенный ()и {}( [], <>и \/не обязательно должен быть согласована , как обычно, хотя они появляются пары в связи с требованием зеркальной симметрии).

В качестве входных данных вы можете взять строку или список символов, но выходные данные должны быть представлены в том же формате.

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

Это код-гольф , поэтому самый короткий действительный ответ - измеренный в байтах - выигрывает.

Тестовые случаи

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

(((=+|+=)))
(=+|+=)

({(=+|+=)})
({(=+|+=)})

((\)/)I(\(/))
(\)(/)I(\)(/)

(()()(())()())


((<|>((X((T)))[_]))\^/(([_](((T))X))<|>))
(<|>)(X)(T)([_])(\^/)([_])(T)(X)(<|>)
code-golf balanced-string syntax Мартин Эндер
источник
Просто чтобы быть уверенным, что циклы, которые мы должны извлечь, обозначены только круглыми скобками (), то есть входные данные {{A}B}останутся как есть и не будут извлечены {A}{B}?
Кевин Круйссен
@KevinCruijssen Да, преобразование действительно только для (...)циклов -типа.
Мартин Эндер
В последнем тесте, почему \^/внутри скобок?
Кевин Круйссен
1
@KevinCruijssen Это самые внешние скобки после того, как вы извлекли (<|>((X((T)))[_]))и (([_](((T))X))<|>).
Мартин Эндер
1
Ах я вижу. Таким образом, ((A)B(C))это станет (A)(B)(C)результатом обоих правил 1 и 2: ((A)B(C))→ (A)(B(C))(правило 1) → (A)(B)(C)(правило 2).
Кевин Круйссен

Ответы:

6

Сетчатка 0.8.2 , 113 107 67 66 байт

+`\(\)|(\()?(\(((\()|(?<-4>\))|[^()])*(?(4)@)\))(?(1)|(\)))
$5$2$1

Попробуйте онлайн! Включает 3 4 байтовых сохранения благодаря @MartinEnder. Объяснение:

+`

Повторно применять замену, пока не будет совпадений.

\(\)|

Сопоставьте пустой цикл (в этом случае ничего не захватывается, поэтому подстановка просто удаляет его) или:

(\()?

При желании соответствовать (. Это фиксируется в группе 1, если это соответствует, но не, если это не так.

(\(

Захватите основную часть матча в группе 2 и сопоставьте a (.

(
 (\()
|
 (<-4>\))
|
 [^()]
)*

Неоднократно сопоставляйте или (, захватывая его в группе 4, или a ), удаляя захват из группы 4 (неудачно, если его нет), или что-то еще.

(?(4)@)

Убедитесь, что в группе 4 не осталось лишних снимков.

\))

Завершить захват группы 2 другой ).

(?(1)|(\)))

Если группа захвата 1 была пуста, то захватить )в группе захвата 5. (Таким образом, точно одна из этих двух групп будет иметь захват).

$5$2$1

Переместите скобку, захваченную в группе 1 или группе 5, на другую сторону группы 2. Это приводит к перемещению внутренней петли вперед или в конец внешней петли в зависимости от того, с какой стороны она совпала.

Нил
источник
2

Stax v1.0.3 +, 76 65 64 62 58 байт CP437

îÜ•$o,Γ{í]Üf╒9♦╛üΣóç*\$ñ₧└ΦJ♠¥c╥jóu≥3E.╘ⁿ◄◘W₧<¶┼7úê╟┴zç↨aG

70 байт при распаковке,

{{.((:/Yc{Z{40=+_41=-c^Ci~^Fdy,,\32&jEa:{a:{a4l$c}Md}X!:Rx!:Rc.()z:rgp

Запускать и отлаживать онлайн!

объяснение

{.((:/Yc{Z{40=+_41=-c^Ci~^Fdy,,\32&jEa:{a:{a4l$c}Mdэто блок, который разделяется A((B)C)Dна четыре части и преобразует его в A(B)(C)D.

X!:Rx!:Rвыполняет блок входной строки (шаг 1), затем отражает строку (отражение строки в Stax относится к обращению строки плюс замена (перевод) (<[{/на (to) \}]>)) и выполняет блок для полученной строки, а затем отражает ее обратно (шаг 2). Шаг 2 по существу конвертируется (A(B))в (A)(B).

c.()z:r удалите все пустые петли (шаг 3).

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

Неявный вывод.

Вейцзюнь Чжоу
источник
1

Python 3 , 226 223 212 206 байт

Хорошо, вот попытка решить эту проблему на языке, который не поддерживает рекурсивное регулярное выражение.

lambda s:g(g(s,*'()'),*')(').replace('()','')
def g(s,t,u):
 m,*a={},;i=v=0
 for c in s:
  i+=1;a+=[i]*(c==t)
  if c==u:*a,x=a;m[x]=i;v=m.get(x+1)
  if v:return g(s[:x]+s[x+1:v]+t+s[v:],t,u)
 return s[::-1]

Попробуйте онлайн!

Редактирование:

  • Рефакторинг [::-1]для экономии 6 байт, благодаря Mr.Xcoder.

gФункция является основным строительным блоком, который находит вхождение ((A)B), изменяет ее (A)(B), а затем применяет себя к результату , пока не более преобразования не возможно.

Основные шаги:

  • Применитесь gк входу нормально.
  • Применить gк входу перевернул. Этот прогон находит вхождение ))A(B(в обратном вводе, который эффективно обрабатывает (A(B)).
  • Удалить любое вхождение ().

Проблема в том, что у gнего настолько плохая структура управления, что, пытаясь обойти его одной строкой, он сильно раздулся, поэтому я не думаю, что на основе этого решения возможно значительное улучшение.

фонтанчик для питья
источник