Konvertieren Sie einen Ausdruck in die Panfix-Notation

19

Ich habe Esolangs durchsucht und diese Sprache gefunden: https://github.com/catseye/Quylthulg .

Eine interessante Sache an dieser Sprache ist, dass sie kein Präfix, Postfix oder Infix verwendet. Sie verwendet alle drei und nennt es "Panfix" -Notation.

Hier ist ein Beispiel. Zur Darstellung von normaler Infix 1+2in panfix, wird es: +1+2+. Beachten Sie, wie sich der Operator vor, zwischen und nach den Operanden befindet. Ein anderes Beispiel ist (1+2)*3. Das wird *+1+2+*3*. Beachten Sie noch einmal, wie *es an allen drei Stellen in Bezug auf die Operanden +1+2+und ist 3.

Die Herausforderung

Wie Sie vielleicht erraten haben, besteht Ihre Aufgabe in dieser Herausforderung darin, einen Ausdruck von infix nach panfix zu konvertieren.

Einige Klarstellungen:

  • Sie müssen sich nur mit den vier Grundoperationen befassen: +-*/
  • Sie müssen sich nicht mit den unären Versionen davon befassen, sondern nur mit Binärdateien
  • Sie müssen mit Klammern umgehen
  • Nehmen Sie die normalen Prioritätsregeln von */damals an +-und lassen Sie für alle Assoziativität übrig.
  • Die Zahlen sind nichtnegative Ganzzahlen
  • Optional können Sie sowohl in der Eingabe als auch in der Ausgabe Leerzeichen einfügen

Testfälle

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

Das ist Code-Golf , also gewinnt der kürzeste Code in Bytes !

code-golf parsing conversion Maltysen
quelle

Antworten:

3

JavaScript (ES6), 160 Byte

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)

Arbeiten Sie, indem Sie alle Operatoren (die ihnen vorher Zeichencodes geben *) in Anführungszeichen setzen , dann nach verfügbaren '*'oder '/'Operationen '+'oder '-'Operationen oder ()s suchen und die erste durch die Panfix-Notation ersetzen. Beispiel:

(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
quelle
3

JavaScript (ES6), 285 282 281 267 251 243 241 238 234 232 231 Byte

~ 15 Bytes dank Neil .

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

In JavaScript ist dies etwas schwieriger als in Mathematica. Dies ist im Grunde ein überspezialisierter und vorrangiger Parser für Operatoren .

Verursacht Stapelüberläufe bei ungültigen Eingaben.

Demo

Code-Snippet anzeigen

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
quelle
S.split``sollte es sein [...S], obwohl es tatsächlich hilfreich sein kann, im Voraus zu passen /\d+|./gund stattdessen daran zu arbeiten.
Neil
@ Neil Danke. Ich werde das untersuchen.
PurkkaKoodari
2

Mathematica, 203 195 Bytes

Dies ist wahrscheinlich weniger effizient, scheint aber den Job zu erledigen.

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]

Dies ist eine anonyme Funktion, die einen tatsächlichen Ausdruck verwendet und eine Zeichenfolge mit Panfix-Notation zurückgibt. Mathematica sortiert die Priorität der Operatoren zum Zeitpunkt der Analyse und nicht zum Zeitpunkt der Auswertung, sodass die Verschachtelung automatisch korrekt sein sollte. Zumindest die Testfälle funktionieren wie erwartet.

Erklärung: Es ist einfach genug, den gesamten Ausdruck als Baum zu interpretieren:

Baum

Zu diesem Zeitpunkt sind die Operatoren (jeder Knoten, der kein Blatt ist) keine Operatoren mehr, sondern wurden in Zeichenfolgen wie konvertiert "+". Die ganzen Zahlen werden auch in Strings umgewandelt. Dann konvertiert eine wiederholte Ersetzungsregel jeden Knoten, der genau zwei Blätter hat, in den Panfix parent-leaf1-parent-leaf2-parent. Nach einigen Iterationen wird der Baum auf eine einzelne Zeichenfolge reduziert.

Der Hauptverlust bei der Byteanzahl ist, dass Mathematica interpretiert

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

Und das passiert auch beim Parsen.

Golfed down ein bisschen, da das Muster a_/b_auch als interpretiert wird a_ * (b_)^(-1). Auch einige kleinere Optimierungen an anderer Stelle.

LLlAMnYP
quelle
1

Prolog, 87 Bytes

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

Dies ist eine Funktion (meistens, weil das Schreiben eines vollständigen Programms in Prolog ein alptraumhaftes Level an Boilerplate hat; normalerweise wird, selbst wenn Sie ein Programm kompilieren , beim Ausführen eine REPL erzeugt), die aufgerufen wird p. Es nimmt Eingaben von stdin und Ausgaben von stdout entgegen. Beachten Sie, dass Sie einen Punkt an die Eingabe anhängen müssen. Dies ist eine unglückliche Folge der Funktionsweise der Prolog-Eingaberoutinen (sie verwenden Punkte in der Eingabe ähnlich wie andere Sprachen Zeilenumbrüche). das könnte oder könnte nicht die Antwort disqualifizieren.

Erläuterung

Arithmetische Operatoren werden in Prolog normalerweise als Tupelkonstruktoren interpretiert . Sie befolgen jedoch dieselben Vorrangregeln wie die eigentlichen arithmetischen Operatoren, auf denen sie basieren. Sie können Tupel mit Infixschreibweise und bilden +und -als binden weniger dicht *und /mit Vorrang innerhalb einer Gruppe links nach rechts gemacht. Genau das verlangt die Frage; Auf diese Weise können wir ein ganzes verschachteltes Tupel von der Eingabe lesen, und es hat bereits die richtige Struktur. Das ist was ptut.

Als nächstes müssen wir es in Panfix-Notation konvertieren. xwandelt die Eingabe in eine panfixed Liste von Konstrukteuren und ganze Zahlen sind , und können fast direkt als ein englischer Satz lesen: „ xder Tist: Wenn Tein Tupel mit Konstruktor Ound Argumente A, Bund dann O, xvon A, O, xder B, O, sonst T“. Schließlich müssen wir nur noch die Liste ohne Trennzeichen drucken (dh jedes Element der Liste mit maplistaufrufen write).

Ich habe SWI-Prolog verwendet, um dies zu testen, da meine Version von GNU Prolog noch nicht maplistvorhanden ist (anscheinend wurde sie einer neueren Version hinzugefügt), sie sollte jedoch im Allgemeinen zwischen Prolog-Implementierungen ziemlich portabel sein.

Gemeinschaft
quelle