Quylthulg - это язык Криса Пресси, который пытается решить проблему инфиксной нотации, используя то, что он называет panfix :

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

Как вы получаете удобство инфиксной нотации наряду с однозначностью префикса или постфикса? Используйте все три, конечно!

=y=+*3*x*+1+=

Более формально, пусть +будет оператором и aи bбудет выражением. потом(a+b) допустимое (заключенное в скобки) инфиксное выражение, панффиксное представление этого выражения +a+b+, где сопоставление представляет конкатенацию.

Ваша цель - взять строку Panfix и преобразовать ее в полностью заключенный в скобки инфикс:

(y=((3*x)+1))

Для простоты мы внесем следующие изменения:

• Операторы могут состоять только из двух уникальных символов (вы можете выбрать любой, но здесь я буду использовать * и +).
• Существует только один литерал, который состоит из другого отдельного символа (вы можете выбрать любой, но здесь я буду использовать _).
• На входе будет правильно сформированное выражение panfix.

Для сложности сделаем следующее изменение:

• Операторы могут состоять из любого положительного числа символов, а не только одного.

Это усложняет задачу, поскольку вы не можете точно определить, как данная подстрока символов оператора разделена, не глядя на остальную часть строки.

Вот эталонная реализация для вызова, любезно предоставленная @ user202729.

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

format: input -> output
+*+_*+_*+++_+*+_*+_*+++ -> ((_*+_)+(_+(_*+_)))
**++*+***++_+_++_+*++*+***_*++*+*****_**_*_*** -> ((((_+_)+_)*++*+***_)*(_*(_*_)))
***_**_***_* -> ((_**_)*_)
+_+_+ -> (_+_)
*+*+++**+***+++++_*+*+++**+***+++++_*+*+++**+***+++++ -> (_*+*+++**+***+++++_)
*++++*+*_*_*+*+++****+_++****+_++****++*+*+++_*+++ -> (((_*_)+*+(_++****+_))*+++_)
+**+_*+_*+*_*+*_*+*_+*_+**+ -> (((_*+_)*_)+(_*(_+*_)))
+**+++++_+++++_+++++*_*+*+_++++++_+++++_+++++++* -> (((_+++++_)*_)+*(_+(_+++++_)))
+*+*+_+*+_+*+*_*+*_*+*+_+*+_+*+*+ -> (((_+*+_)*_)+(_*(_+*+_)))
**_**_**_*_****_* -> ((_*(_*(_*_)))*_)

Я использовал эту программу для генерации инфиксных строк для этой задачи (преобразование в panfix было тривиальным, но обратное - нет).

Пролог (SWI) , 194 163 байта

^{Сохраняя колоссальные 31 байт, используя этот совет от 0 ' !}

[C|T]/O/R:-C\=x,(T/P/R,concat(C,P,O);O=C,R=T).
[x|R]-x-R.
L-X-R:-L/O/A,A-Y-B,B/O/C,C-Z-D,D/O/R,atomics_to_string(['(',Y,O,Z,')'],X).
X^P:-string_chars(X,L),L-P-[].

Оператор ^принимает в качестве левого аргумента строку, содержащую выражение panfix, и устанавливает в качестве правого аргумента строку, содержащую соответствующее инфиксное выражение в скобках. Он использует xв качестве буквального вместо _.

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

объяснение

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

В объяснении используется эта слегка неутешительная версия:

oper([C|T],O,R) :- C\=x, oper(T,P,R), concat(C,P,O).
oper([C|T],C,T).

expr([x|R],x,R).
expr(L,X,R) :- oper(L,O,A), expr(A,Y,B), oper(B,O,C), expr(C,Z,D), oper(D,O,R),
               atomics_to_string(['(',Y,O,Z,')'],X).

parenthesize(X,P) :- string_chars(X,L), expr(L,P,[]).

Наше основное производство - parenthesizeэто выражение panfix Xв виде строки и отправка соответствующего инфиксного выражения Pв скобках в виде строки. Он использует string_charsдля преобразования входной строки в список символов, а затем просто передает его expr.

exprберет список символов L, анализирует первое найденное в нем выражение Panfix Lи отправляет эквивалент в скобках Xи остаток списка символов R. Есть два возможных вида выражений:

• Если первый символ L- xэто выражение, xа остаток - это все после x.
• В противном случае, синтаксический анализ оператора O(см. operНиже); разобрать выражение Y; разбор Oснова; разобрать другое выражение Z; и разобрать Oв третий раз. Остальное все после третьего экземпляра O. Выражение является результатом присоединения Y, Oи Z, в круглых скобках, в строку.

operберет список символов, где первый символ, Cа остальные T; он анализирует оператор (т.е. набор из одного или нескольких символов оператора) и отправляет оператор Oи оставшуюся часть списка символов R. Чтобы сформировать оператор, символ Cдолжен быть чем-то отличным от x; также либо

• оператор Pдолжен быть разборчив с T, с остатком R; в данном случае Oэто конкатенация Cи P; или,
• Oэто один символ C; в этом случае Rсправедливо T.

Работающий пример

Давайте возьмем вход +*+x+x++*x+*для примера.

• Мы хотим разобрать выражение из +*+x+x++*x+*. Это не начинается с x, поэтому мы анализируем оператор с самого начала.
• oper будет анализировать как можно больше оператора, поэтому мы стараемся +*+ .
  • Затем мы анализируем выражение из x+x++*x+* . Это должно быть x.
  • Теперь мы пытаемся разобрать тот же оператор +*+, с +x++*x+*. Однако это не удается .
• Поэтому мы возвращаемся назад и пытаемся разобрать оператор +* вместо этого .
  • Разбираем выражение из +x+x++*x+*. Это не начинается сx , поэтому нам нужно проанализировать оператор.
  • Единственная возможность + .
  • Теперь проанализируйте подвыражение из x+x++*x+*. Это должно бытьx .
  • Теперь +снова разбор с+x++*x+* .
  • Теперь проанализируем другое подвыражение из x++*x+*. Это должно бытьx .
  • Наконец, +снова разбор++*x+* .
  • Выражение было успешно проанализировано. Мы возвращаем строку (x+x).
• Вернувшись на предыдущий уровень рекурсии, мы +*снова анализируем оператор из +*x+*.
• Теперь проанализируем другое подвыражение из x+*. Это должно бытьx .
• Наконец, +*снова разбор с+* .
• Выражение было успешно проанализировано. Мы возвращаем строку ((x+x)+*x).

Поскольку больше не осталось символов, мы успешно перевели выражение.

Perl, 78 60 58 57 50 байт

Включает +1в себяp

Использует 1для +и 2для *(или фактически любая цифра работает для любого оператора)

perl -pe 's/\b((\d+)((?1)|_)\2((?3))\2)\b/($3 $2 $4)/&&redo' <<< 22_22_22_2_2222_2

Для удобства тестирования по сравнению с приведенными примерами вы можете использовать это, которое делает переводы и удаление места для вас:

perl -pe 'y/+*/12/;s/\b((\d+)((?1)|_)\2((?3))\2)\b/($3 $2 $4)/&&redo;y/ //d;y/12/+*/' <<< "**_**_**_*_****_*"

Чистый , 200 192 189 байт

import StdEnv,Text
f"_"=["_"]
f l=["("+a+p+b+")"\\p<-[l%(0,i)\\i<-[0..indexOf"_"l]|endsWith(l%(0,i))l],t<-[tl(init(split p l))],n<-indexList t,a<-f(join p(take n t))&b<-f(join p(drop n t))]

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

Определяет функцию f, принимая Stringи возвращая синглтон[String] с результатом внутри.

Некоторые аккуратные вещи:

• Не использует регулярные выражения
• Работает с любым символом для операторов, кроме_

Сетчатка 0.8.2 , 138 байт

.+
($&)
+`\((\d+)(_|((?<i>(?<i>\d+))|_(?<-i>\k<i>)+)+(?(i)(?!)))\1(_|((?<i>(?<i>\d+))|_(?<-i>\k<i>)+)+(?(i)(?!)))\1\)
(($2)$1($4))
\(_\)
_

Попробуйте онлайн! Ссылка включает в себя более быстрые тестовые случаи. Объяснение: Движок регулярных выражений использует обратную трассировку для разделения строки на токены, которые затем добавляются или выталкиваются из iгруппы балансировки. Всегда выполняется хотя бы один оператор, помещенный в начале перед первой переменной. После переменной извлекается, по крайней мере, один оператор, и в этот момент запускается оператор с нажатием или другая переменная является допустимой. Операторы выталкиваются в группу в двух экземплярах, чтобы их можно было правильно высовывать. Пример:

Input           Stack
Push *          * *
Push *++*+***   * * *++*+*** *++*+***
Push +          * * *++*+*** *++*+*** + +
Push +          * * *++*+*** *++*+*** + + + +
Variable _
Pop +           * * *++*+*** *++*+*** + + +
Variable _
Pop +           * * *++*+*** *++*+*** + +
Pop +           * * *++*+*** *++*+*** +
Variable _
Pop +           * * *++*+*** *++*+***
Pop *++*+***    * * *++*+***
Variable _
Pop *++*+***    * *
Pop *           *
Push *          * * *
Variable _
Pop *           * *
Push *          * * * *
Variable _
Pop *           * * *
Variable _
Pop *           * *
Pop *           *
Pop *

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

Haskell , 167 166 байт

head.e
e('_':r)=["_",r]
e(x:r)=[x]%r
e _=[]
o%t@(c:r)|[x,u]<-e t,n<-length o,[y,v]<-e$drop n u,all((==o).take n)[u,v]=['(':x++o++y++")",drop n v]|p<-o++[c]=p%r
o%_=[]

Попробуйте онлайн! Пример использования: head.e "**_**_**_*_****_*"доходность ((_*(_*(_*_)))*_). Все символы, кроме _как интерпретируются как операторы, _само по себе обозначает идентификатор.

Python 3, 226 байт

from re import*
P=r'([*+]+)'+r'(\(.+?\)|_)\1'*2;R=lambda i,J=lambda i,o:i[:o]+sub(P,lambda o:'('+o[2]+o[1]+o[3]+')',i[o:],1),s=search:s(P,i)and R([J(i,o)for o in range(len(i))if s(P,J(i,o))or J(i,o)[0]+J(i,o)[-1]=='()'][0])or i

Определяет анонимную функцию с именем R.

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