Konwertuj wyrażenie na notację Panfix

19

Przeglądałem esolangi i trafiłem na ten język: https://github.com/catseye/Quylthulg .

Jedną interesującą rzeczą w tym języku jest to, że nie używa on przedrostka, postfiksa ani poprawki, używa wszystkich trzech , nazywając to notacją „panfix”.

Oto przykład. Do reprezentowania normalnej Infix 1+2w panfix, staje się: +1+2+. Zauważ, że operator jest zarówno przed, jak i po operandach. Innym przykładem jest (1+2)*3. To się staje *+1+2+*3*. Zauważ ponownie, jak *jest we wszystkich trzech miejscach w odniesieniu do operandów +1+2+i 3.

Wyzwanie

Jak zapewne zgadłeś, Twoim zadaniem w tym wyzwaniu jest konwersja wyrażenia z infix na panfix.

Kilka wyjaśnień:

  • Musisz tylko poradzić sobie z czterema podstawowymi operacjami: +-*/
  • Nie będziesz musiał radzić sobie z pojedynczymi wersjami tych, tylko binarnymi
  • Musisz poradzić sobie z nawiasami
  • Zakładamy normalnych zasad pierwszeństwa */wtedy +-i lewo skojarzenie dla nich wszystkich.
  • Liczby będą liczbami całkowitymi nieujemnymi
  • Opcjonalnie możesz mieć spacje na wejściu i wyjściu

Przypadki testowe

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-*

To jest golf golfowy , więc wygrywa najkrótszy kod w bajtach !

code-golf parsing conversion Maltysen
źródło

Odpowiedzi:

3

JavaScript (ES6), 160 bajtów

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)

Prace cytowanie wszystkich operatorów (co daje im kody znak przed *), a potem szuka dostępny '*'lub '/'operacji '+'lub '-'operacji lub ()S, i zastępując pierwszy z notacją panfix. Przykład:

(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-*
Neil
źródło
3

JavaScript (ES6) 285 282 281 267 251 243 241 238 234 232 231 bajtów

~ 15 bajtów dzięki Neilowi .

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))

W JavaScript jest to nieco trudniejsze niż w Mathematica. Jest to w zasadzie nadmiernie wyspecjalizowany analizator składający się z priorytetów operatora .

Powoduje przepełnienie stosu przy nieprawidłowych danych wejściowych.

Próbny

Pokaż fragment kodu

Nie golfił

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
źródło
S.split``powinno być [...S], chociaż może faktycznie pomóc z góry dopasować /\d+|./gi pracować nad tym.
Neil
@Neil Thanks. Zajrzę do tego.
PurkkaKoodari
2

Matematyka, 203 195 bajtów

Jest to prawdopodobnie mniej niż wydajne, ale wydaje się, że wykonuje swoją pracę.

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]

Jest to anonimowa funkcja, która przyjmuje rzeczywiste wyrażenie i zwraca ciąg znaków z notacją panfix. Mathematica odróżnia pierwszeństwo operatorów w czasie analizy, a nie w czasie oceny, więc zagnieżdżanie powinno być automagicznie poprawne. Przynajmniej przypadki testowe działają zgodnie z oczekiwaniami.

Objaśnienie: Łatwo jest zinterpretować całe wyrażenie jako drzewo, na przykład:

drzewo

Na tym etapie operatory (każdy węzeł, który nie jest liściem) nie są już operatorami, w rzeczywistości zostały przekonwertowane na ciągi znaków, takie jak "+" . Liczby całkowite są również rzutowane na ciągi. Następnie reguła powtarzanej zamiany konwertuje każdy węzeł, który ma dokładnie dwa liście do panfix parent-leaf1-parent-leaf2-parent. Po kilku iteracjach drzewo zmniejsza się do jednego ciągu.

Główną stratą w liczbie bajtów jest to, że Mathematica interpretuje

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

Dzieje się tak również w czasie analizy.

Grałem nieco w golfa, ponieważ wzór a_/b_jest również interpretowany jako a_ * (b_)^(-1). Także drobne optymalizacje w innych miejscach.

LLAMAMYP
źródło
1

Prolog, 87 bajtów

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

Jest to funkcja (głównie dlatego, że napisanie pełnego programu ma koszmarne poziomy bojlera w Prologu; normalnie, nawet jeśli kompilujesz program, po uruchomieniu generuje REPL), wywoływanep . Pobiera dane wejściowe ze standardowego wejścia i wyjścia na standardowe wyjście. Zauważ, że musisz dodać kropkę do wejścia, co jest niefortunną konsekwencją sposobu, w jaki działają procedury wprowadzania Prologa (używają kropek w danych w taki sam sposób, jak inne języki używają znaków nowej linii); które mogą dyskwalifikować odpowiedź.

Wyjaśnienie

Operatory arytmetyczne w Prologu są zwykle interpretowane jako konstruktory krotkowe . Jednak przestrzegają tych samych reguł pierwszeństwa, co rzeczywiste operatory arytmetyczne, na których się opierają; możesz tworzyć krotki z zapisem infiksowym +i -wiązać mniej ściśle niż, *i /z pierwszeństwem od lewej do prawej w grupie. Właśnie o to pyta pytanie; w ten sposób możemy odczytać całą zagnieżdżoną krotkę z wejścia i ma ona już odpowiednią strukturę. Właśnie top robi.

Następnie musimy przekonwertować go na notację panfixową. xkonwertuje wejście do panfixed listy konstruktorów i całkowitymi i mogą być odczytywane jako zdaniu angielskim prawie bezpośrednio: „ xo Tto: czy Tjest krotką z konstruktora Oi argumentów A, B, a następnie O, xz A, O, xz B, O, inny T”. Na koniec musimy po prostu wydrukować listę bez żadnych separatorów (tj. Za pomocą maplistwywoływania writekażdego elementu listy).

Użyłem SWI-Prolog do testowania tego, ponieważ moja wersja GNU Prolog maplistjeszcze nie ma (najwyraźniej została dodana do nowszej wersji), ale ogólnie powinna być dość przenośna między implementacjami Prolog.

Społeczność
źródło