Преобразовать выражение в нотацию Panfix

19

Я просматривал esolangs и случайно наткнулся на этот язык: https://github.com/catseye/Quylthulg .

Что интересно в этом языке, так это то, что он не использует префикс, постфикс или инфикс, он использует все три из них , называя это обозначением «panfix».

Вот пример. Чтобы представить нормальный инфикс 1+2в panfix, она становится: +1+2+. Обратите внимание, как оператор находится до, между и после операндов. Еще один пример (1+2)*3. Это становится *+1+2+*3*. Еще раз обратите внимание, как *во всех трех местах относительно операндов +1+2+и 3.

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

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

Несколько уточнений:

  • Вам нужно только разобраться с четырьмя основными операциями: +-*/
  • Вам не придется иметь дело с унарными версиями, только двоичными
  • Вы должны иметь дело с круглыми скобками
  • Предположим, нормальные правила предшествования */тогда +-и оставил ассоциативность для всех из них.
  • Числа будут неотрицательными целыми числами
  • Вы можете опционально иметь пробелы как на входе, так и на выходе.

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

1+2  ->  +1+2+
1+2+3  ->  ++1+2++3+
(1+2)*3  ->  *+1+2+*3*
10/2*5  ->  */10/2/*5*
(5+3)*((9+18)/4-1)  ->  *+5+3+*-/+9+18+/4/-1-*

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

code-golf parsing conversion Maltysen
источник

Ответы:

3

JavaScript (ES6), 160 байт

f=(s,t=s.replace(/[*-/]/g,"'$&'"),u=t.replace(/^(.*?)([*-9]+)'([*/])'([*-9]+)|([*-9]+)'([+-])'([*-9]+)|\(([*-9]+)\)/,"$1$3$2$3$4$3$6$5$6$7$6$8"))=>t==u?t:f(s,u)

Работает, заключая в кавычки все операторы (которые передают им коды символов ранее *), затем ищет доступные '*'или '/'операции, '+'или '-'операции или ()s, и заменяя первый на его обозначение panfix. Пример:

(5+3)*((9+18)/4-1)
(5'+'3)'*'((9'+'18)'/'4'-'1)
(+5+3+)'*'((9'+'18)'/'4'-'1)
+5+3+'*'((9'+'18)'/'4'-'1)
+5+3+'*'((+9+18+)'/'4'-'1)
+5+3+'*'(+9+18+'/'4'-'1)
+5+3+'*'(/+9+18+/4/'-'1)
+5+3+'*'(-/+9+18+/4/-1-)
+5+3+'*'-/+9+18+/4/-1-
*+5+3+*-/+9+18+/4/-1-*
Нил
источник
3

JavaScript (ES6), 285 282 281 267 251 243 241 238 234 232 231 байт

~ 15 байтов благодаря Нейлу .

f=(I,E=I.match(/\d+|./g),i=0)=>(J=T=>T.map?T.map(J).join``:T)((R=(H,l=(P=_=>(t=E[i++])<")"?R(0):t)(),C,F)=>{for(;(C=P())>")"&&(q=C>"*"&&C<"/")*H-1;)F=q+H?l=[C,l,C,P(),C]:F?l[3]=[C,l[3],C,R(1),C]:l=R(1,l,i--)
i-=C>")"
return l})(0))

В JavaScript это немного сложнее, чем в Mathematica. Это в основном сверхспециализированный анализатор приоритетов операторов .

Вызывает переполнение стека на неверных входах.

демонстрация

Показать фрагмент кода

Ungolfed

convert = input => {
  tokens = input.match(/\d+|./g);
  i = 0;
  parse_token = () => (token = tokens[i++]) == "(" ? parse_tree(false) : token;
  parse_tree = (mul_div_mode, left = parse_token()) => {
    while ((oper = parse_token()) != ")" && !((is_plus_minus = oper == "+" || oper == "-") && mul_div_mode)) {
      if (is_plus_minus || mul_div_mode)
        left = [oper, left, oper, parse_token(), oper];
      else if (non_first)
        left[3] = [oper, left[3], oper, parse_tree(true), oper];
      else
        left = parse_tree(true, left, i--);
      non_first = true;
    }
    if (oper != ")")
      i--;
    return left;
  };
  format_tree = tree => tree.map ? tree.map(format_tree).join("") : tree;
  return format_tree(parse_tree(false));
}
PurkkaKoodari
источник
S.split``должно быть [...S], хотя на самом деле это может помочь на /\d+|./gначальном этапе и вместо этого работать над этим.
Нил
@ Нейл Спасибо. Я посмотрю на это.
PurkkaKoodari
2

Mathematica, 203 195 байтов

Это, вероятно, менее чем эффективно, но, кажется, делает работу.

Function[f,ReleaseHold[(Inactivate@f/._[Plus][a_,b_/;b<0]:>a~"-"~-b//Activate@*Hold)//.a_/b_:>a~"/"~b/.{a_Integer:>ToString@a,Plus:>"+",Times:>"*"}]//.a_String~b_~c_String:>b<>a<>b<>c<>b,HoldAll]

Это анонимная функция, которая принимает фактическое выражение и возвращает строку с обозначением Panfix. Mathematica сортирует приоритет операторов во время разбора, а не во время оценки, поэтому вложение должно быть автоматически корректным. По крайней мере, тестовые случаи работают как положено.

Объяснение: Достаточно просто интерпретировать все выражение как дерево, например так:

дерево

На этом этапе операторы (каждый узел, который не является листом) больше не являются операторами, они фактически были преобразованы в такие строки, как "+". Целые числа также приводятся к строкам. Затем правило повторной замены преобразует каждый узел, имеющий ровно два листа, в исправление parent-leaf1-parent-leaf2-parent. После нескольких итераций дерево сводится к одной строке.

Основная потеря в количестве байтов заключается в том, что Mathematica интерпретирует

5 - 4 -> 5 + (-4)
9 / 3 -> 9 * (3^(-1))

И это происходит также во время разбора.

Гольф немного вниз, так как картина a_/b_также интерпретируется как a_ * (b_)^(-1). Также некоторые незначительные оптимизации в другом месте.

LLlAMnYP
источник
1

Пролог, 87 байт

x(T)-->{T=..[O,A,B]}->[O],x(A),[O],x(B),[O];[T].
p:-read(T),x(T,L,[]),maplist(write,L).

Это функция (в основном потому, что написание полной программы имеет ночные кошмарные уровни в Prolog; обычно, даже если вы компилируете программу, она запускает REPL при запуске), вызывается p. Он принимает входные данные от стандартного ввода и выводит на стандартный вывод. Обратите внимание, что вам нужно добавить точку к входу, что является печальным следствием того, как работают подпрограммы ввода Пролога (они используют точки во входе почти так же, как другие языки используют переводы строки); это может или не может дисквалифицировать ответ.

объяснение

Арифметические операторы в Прологе обычно интерпретируются как конструкторы кортежей . Однако они подчиняются тем же правилам приоритета, что и фактические арифметические операторы, на которых они основаны; Вы можете формировать кортежи с инфиксной нотацией +и -связывать их менее плотно, чем *и /, с приоритетом внутри группы слева направо. Это именно то, что вопрос требует; таким образом, мы можем прочитать весь вложенный кортеж из входных данных, и он уже имеет правильную структуру. Вот что pделает.

Далее нам нужно преобразовать его в обозначение Panfix. xпреобразует входные данные в panfixed список конструкторов и целых чисел, и может быть прочитана как английское предложение почти прямо: « xиз T: если Tэто кортеж с конструктором Oи аргументами A, B, то O, xо A, O, xо B, O, иначе T». Наконец, мы просто должны напечатать список без каких-либо разделителей (т.е. использовать maplistдля вызова writeкаждого элемента списка).

Я использовал SWI-Prolog для тестирования этого, потому что моей версии GNU Prolog еще maplistнет (по-видимому, она была добавлена ​​в более новую версию), но она должна быть достаточно переносимой между реализациями Prolog.

Сообщество
источник