Quylthulg ist eine Sprache von Chris Pressey, die versucht, das Problem der Infix-Notation mit dem zu lösen, was sie panfix nennt :

Ähnlich wie bei Postfix erfordert Panfix nicht die Bereitstellung geheimer Funktionen wie Klammern, um die Standardpriorität eines Operators zu überschreiben. Gleichzeitig ermöglicht panfix die Angabe von Begriffen in der gleichen Reihenfolge und Weise wie bei infix, was für diejenigen, die sich daran gewöhnt haben, eine zweifellos natürliche und intuitive Notation ist.

Wie erhalten Sie die Bequemlichkeit der Infixnotation zusammen mit der Eindeutigkeit von Präfix oder Postfix? Verwenden Sie natürlich alle drei!

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

Seien Sie formal gesehen +ein Operator aund bAusdrücke. (a+b)Ist dann ein gültiger (in Klammern stehender) Infix-Ausdruck, ist die panfix-Darstellung dieses Ausdrucks +a+b+, wobei Nebeneinanderstellung Verkettung darstellt.

Ihr Ziel ist es, einen Panfix-String zu nehmen und in ein Infix in Klammern umzuwandeln:

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

Der Einfachheit halber nehmen wir die folgenden Änderungen vor:

• Operatoren können nur aus zwei eindeutigen Zeichen bestehen (Sie können ein beliebiges Zeichen auswählen, aber hier verwende ich *und +).
• Es gibt nur ein Literal, das aus einem anderen eindeutigen Zeichen besteht (Sie können ein beliebiges auswählen, aber hier werde ich es verwenden _).
• Die Eingabe ist ein wohlgeformter Panfix-Ausdruck.

Aus Gründen der Komplexität nehmen wir die folgenden Änderungen vor:

• Operatoren können aus einer beliebigen positiven Anzahl von Zeichen bestehen, nicht nur aus einem.

Dies macht die Herausforderung schwieriger, da Sie nicht unbedingt bestimmen können, wie eine bestimmte Teilzeichenfolge von Operatorzeichen partitioniert ist, ohne den Rest der Zeichenfolge zu betrachten.

Hier ist eine Referenzimplementierung für die Herausforderung mit freundlicher Genehmigung von @ user202729.

Testfälle

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

Ich habe dieses Programm verwendet , um Infix-Strings für diese Herausforderung zu generieren (das Konvertieren in Panfix war trivial, das Umkehren jedoch nicht).

Prolog (SWI) , 194 163 Bytes

^{Hat mit diesem Tipp satte 31 Bytes von 0 ' gespeichert !}

[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-[].

Der Operator verwendet als ^linkes Argument einen String mit einem Panfix-Ausdruck und setzt sein rechtes Argument auf einen String mit dem entsprechenden Infix-Ausdruck in Klammern. Es wird xals Literal anstelle von verwendet _.

Probieren Sie es online!

Erläuterung

Da Prolog eine deklarative Sprache ist, müssen wir nur die Beziehung zwischen einem panfix und einem Ausdruck in Klammern beschreiben.

Die Erklärung verwendet diese leicht ungolfed Version:

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,[]).

Unsere Hauptproduktion ist parenthesize, einen panfix-Ausdruck Xals String aufzunehmen und den entsprechenden Infix-Ausdruck in Klammern Pals String auszusenden . Es verwendet string_charsdie Eingabezeichenfolge in eine Liste von Zeichen zu konvertieren und dann geht es einfach auf expr.

exprLNimmt eine Liste von Zeichen auf , analysiert den ersten Panfix-Ausdruck, den es findet L, und sendet das in Klammern gesetzte Äquivalent Xund den Rest der Liste von Zeichen R. Es gibt zwei mögliche Arten von Ausdrücken:

• Wenn das erste Zeichen von List x, dann ist der Ausdruck xund der Rest ist alles nach dem x.
• Analysieren Sie andernfalls einen Operator O(siehe operunten). einen Ausdruck analysieren Y; Oerneut analysieren ; einen anderen Ausdruck analysieren Z; und Oein drittes Mal analysieren . Der Rest ist alles nach der dritten Instanz von O. Der Ausdruck ist das Ergebnis der Verbindung Y, Ound Zdurch Klammern umgeben, in einen String.

opernimmt eine Liste von Zeichen auf, wobei das erste Zeichen Cund der Rest sind T; Es analysiert einen Operator (dh eine Folge von einem oder mehreren Operator-Zeichen) und sendet den Operator Ound den Rest der Liste der Zeichen R. Um einen Operator zu bilden, Cmuss das Zeichen etwas anderes sein als x; auch nicht

• Ein Operator Pmuss für den TRest syntaktisch analysierbar sein R. in diesem Fall Oist die Verkettung von Cund P; oder,
• Oist das einzelne Zeichen C; In diesem Fall Rist es einfach T.

Ein gelungenes Beispiel

Nehmen wir die Eingabe +*+x+x++*x+*als Beispiel.

• Wir wollen einen Ausdruck aus analysieren +*+x+x++*x+*. Das fängt nicht damit an x, also analysieren wir einen Operator von Anfang an.
• operwird einen Operator so groß wie möglich analysieren, also versuchen wir es +*+.
  • Als nächstes analysieren wir einen Ausdruck aus x+x++*x+*. Das muss sein x.
  • Nun versuchen wir den gleichen Operator zu analysieren +*+, von +x++*x+*. Dies schlägt jedoch fehl .
• Also gehen wir zurück und versuchen +*stattdessen, den Operator zu analysieren .
  • Wir analysieren einen Ausdruck von +x+x++*x+*. Das fängt nicht damit an x, also müssen wir einen Operator analysieren.
  • Die einzige Möglichkeit ist +.
  • Analysieren Sie jetzt einen Unterausdruck von x+x++*x+*. Das muss sein x.
  • Jetzt +nochmal parsen ab +x++*x+*.
  • Analysieren Sie jetzt einen weiteren Unterausdruck von x++*x+*. Das muss sein x.
  • Zum Schluss +nochmal parsen ab ++*x+*.
  • Der Ausdruck wurde erfolgreich analysiert. Wir geben den String zurück (x+x).
• Zurück auf der vorherigen Rekursionsebene analysieren wir den Operator +*erneut von +*x+*.
• Analysieren Sie jetzt einen weiteren Unterausdruck von x+*. Das muss sein x.
• Zum Schluss +*nochmal parsen ab +*.
• Der Ausdruck wurde erfolgreich analysiert. Wir geben den String zurück ((x+x)+*x).

Da keine Zeichen mehr übrig sind, haben wir den Ausdruck erfolgreich übersetzt.

Perl, 78 60 58 57 50 Bytes

Enthält +1fürp

Verwendet 1für +und 2für *(oder tatsächlich funktioniert jede Ziffer für jeden Operator)

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

Zum bequemen Testen im Vergleich zu den angegebenen Beispielen können Sie diese verwenden, die die Übersetzungen und das Entfernen von Leerzeichen für Sie erledigt:

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

Sauber , 200 192 189 Bytes

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

Probieren Sie es online!

Definiert die Funktion f, nimmt Stringeinen Singleton und gibt ihn [String]mit dem Ergebnis zurück.

Einige nette Sachen:

• Regex wird nicht verwendet
• Funktioniert mit allen Zeichen für Operatoren außer_

Retina 0.8.2 , 138 Bytes

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

Probieren Sie es online! Link enthält die schnelleren Testfälle. Erläuterung: Die Regex-Steuerkomponente verwendet die Rückverfolgung, um die Zeichenfolge in Token aufzuteilen, die dann in den iBilanzkreis verschoben oder aus diesem entfernt werden . Es wird immer mindestens ein Operator ausgeführt, der am Anfang vor die erste Variable gedrückt wird. Nach einer Variablen wird mindestens ein Operator eingefügt. Zu diesem Zeitpunkt ist entweder ein Push-Operator-Lauf oder eine andere Variable zulässig. Operatoren werden doppelt an die Gruppe weitergeleitet, damit sie korrekt abgerufen werden können. Beispiel:

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 *

Leider hilft uns dies nicht, die Ergebnisse zu erfassen, um sie in Klammern zu setzen, sodass der äußere Operator manuell abgeglichen wird. Die Klammern werden von außen nach innen hinzugefügt. In der ersten Stufe wird der gesamte Ausdruck in Klammern eingeschlossen, und in der letzten Stufe werden sie entfernt, nachdem sie auf die Variablen übertragen wurden.

Haskell , 167 166 Bytes

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%_=[]

Probieren Sie es online! Anwendungsbeispiel: head.e "**_**_**_*_****_*"Erträge ((_*(_*(_*_)))*_). Alle Zeichen außer _werden als Operatoren interpretiert, _selbst bezeichnet eine Kennung.

Python 3, 226 Bytes

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

Definiert eine anonyme Funktion mit dem Namen R.

Probieren Sie es online!