Quylthulg est un langage de Chris Pressey qui tente de résoudre le problème de la notation infixe en utilisant ce qu'il appelle panfix :

comme postfix, panfix ne nécessite pas le déploiement de dispositifs arcanes tels que des parenthèses pour remplacer une priorité d'opérateur par défaut. En même temps, panfix permet de spécifier les termes dans le même ordre et la même manière que infix, une notation incontestablement naturelle et intuitive pour ceux qui s'y sont habitués.

Comment obtenez-vous la commodité de la notation infixe avec l’ambiguïté du préfixe ou du suffixe? Utilisez les trois, bien sûr!

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

Plus formellement, +soit un opérateur, et aet des bexpressions. Ensuite , (a+b)est une expression de infix valide (parenthésée), la représentation panfix de cette expression est +a+b+, où la juxtaposition représente la concaténation.

Votre objectif est de prendre une chaîne panfix et de la convertir en infixe entièrement entre parenthèses:

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

Par souci de simplicité, nous apporterons les modifications suivantes:

• Les opérateurs ne peuvent être composés que de deux caractères uniques (vous pouvez en choisir un, mais ici je vais utiliser *et +).
• Il n'y a qu'un seul littéral, qui consiste en un autre caractère distinct (vous pouvez en choisir un, mais ici je vais l'utiliser _).
• L'entrée sera une expression panfix bien formée.

Pour la complexité , nous ferons le changement suivant:

• Les opérateurs peuvent être constitués de n'importe quel nombre positif de caractères, pas d'un seul.

Cela rend le défi plus difficile car vous ne pouvez pas nécessairement déterminer comment une sous-chaîne donnée de caractères d'opérateur est partitionnée sans regarder le reste de la chaîne.

Voici une implémentation de référence pour le défi, gracieuseté de @ user202729.

Cas de test

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

J'ai utilisé ce programme pour générer des chaînes d'infixes pour ce défi (la conversion en panfix était triviale, mais pas l'inversion).

Prolog (SWI) , 194163 octets

^{Enregistré un énorme 31 octets en utilisant cette astuce de 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-[].

L'opérateur ^prend pour son argument de gauche une chaîne contenant une expression panfix et définit son argument de droite sur une chaîne contenant l'expression d'infixe entre parenthèses correspondante. Il utilise xcomme littéral à la place de _.

Essayez-le en ligne!

Explication

Puisque Prolog est un langage déclaratif, il suffit de décrire la relation entre un panfix et une expression entre parenthèses.

L'explication utilise cette version légèrement non golfée:

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

Notre production principale est parenthesize, qui prend une expression panfix Xsous forme de chaîne et envoie l'expression infixe entre parenthèses correspondante Psous forme de chaîne. Il utilise string_charspour convertir la chaîne d'entrée en une liste de caractères, puis la transmet simplement à expr.

exprprend une liste de caractères L, analyse la première expression panfix qu'il trouve Let envoie l'équivalent entre parenthèses Xet le reste de la liste de caractères R. Il existe deux types d'expressions possibles:

• Si le premier caractère de Lest x, alors l'expression est xet le reste est tout après le x.
• Sinon, analysez un opérateur O(voir operci - dessous); analyser une expression Y; analyser à Onouveau; analyser une autre expression Z; et analyser Oune troisième fois. Le reste est tout après la troisième instance de O. L'expression est le résultat de la jonction Y, Oet Z, entourée de parenthèses, en une chaîne.

operprend une liste de caractères, où le premier caractère est Cet le reste sont T; il analyse un opérateur (c'est-à-dire une séquence d'un ou plusieurs caractères d'opérateur) et envoie l'opérateur Oet le reste de la liste de caractères R. Pour former un opérateur, le caractère Cdoit être autre chose que x; aussi, soit

• un opérateur Pdoit être analysable à partir du Treste R; dans ce cas, Oest la concaténation de Cet P; ou,
• Oest le caractère unique C; dans ce cas, Rc'est juste T.

Un exemple concret

Prenons l'entrée +*+x+x++*x+*pour un exemple.

• Nous voulons analyser une expression à partir de +*+x+x++*x+*. Cela ne commence pas par x, donc nous analysons un opérateur depuis le début.
• operanalysera le plus grand opérateur possible, nous essayons donc +*+.
  • Ensuite, nous analysons une expression de x+x++*x+*. Cela doit être x.
  • Maintenant, nous essayons d'analyser le même opérateur,, à +*+partir de +x++*x+*. Cependant, cela échoue .
• Nous revenons donc en arrière et essayons d'analyser l'opérateur à la +*place.
  • Nous analysons une expression de +x+x++*x+*. Cela ne commence pas par x, nous devons donc analyser un opérateur.
  • La seule possibilité est +.
  • Analyser maintenant une sous-expression de x+x++*x+*. Cela doit être x.
  • Maintenant, analysez de +nouveau +x++*x+*.
  • Analyser maintenant une autre sous-expression de x++*x+*. Cela doit être x.
  • Enfin, analysez à +nouveau à partir de ++*x+*.
  • L'expression a été correctement analysée. Nous retournons la chaîne (x+x).
• De retour au niveau de récursivité précédent, nous analysons à +*nouveau l'opérateur à partir de +*x+*.
• Analyser maintenant une autre sous-expression de x+*. Cela doit être x.
• Enfin, analysez à +*nouveau à partir de +*.
• L'expression a été correctement analysée. Nous retournons la chaîne ((x+x)+*x).

Puisqu'il ne reste plus de caractères, nous avons réussi à traduire l'expression.

Perl, 78 60 58 57 50 octets

Comprend +1pourp

Utilise 1pour +et 2pour *(ou en fait n'importe quel chiffre fonctionne pour n'importe quel opérateur)

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

Pour des tests pratiques par rapport aux exemples donnés, vous pouvez utiliser ceci qui effectue les traductions et la suppression d'espace pour vous:

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

Clean , 200 192 189 octets

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

Essayez-le en ligne!

Définit la fonction f, en prenant Stringet en retournant un singleton [String]avec le résultat à l'intérieur.

Quelques trucs sympas:

• N'utilise pas regex
• Fonctionne avec n'importe quel caractère pour les opérateurs sauf_

Retina 0.8.2 , 138 octets

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

Essayez-le en ligne! Link inclut les cas de test les plus rapides. Explication: Le moteur d'expression régulière utilise le retour arrière pour diviser la chaîne en jetons qui sont ensuite poussés ou extraits du igroupe d'équilibrage. Il y a une série d'au moins un opérateur poussé au début avant la première variable. Après une variable, au moins un opérateur est sauté, auquel cas un opérateur poussé exécuté ou une autre variable est légal. Les opérateurs sont poussés vers le groupe en double afin qu'ils puissent être sautés correctement. Exemple:

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 *

Malheureusement, cela ne nous aide pas à capturer les résultats afin de les mettre entre parenthèses, de sorte que l'opérateur externe est mis en correspondance manuellement. Les crochets sont ajoutés de l'extérieur vers l'intérieur, donc la première étape enveloppe l'expression entière entre crochets et la dernière étape les supprime maintenant qu'ils se sont propagés jusqu'aux variables.

Haskell , 167 166 octets

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

Essayez-le en ligne! Exemple d'utilisation: head.e "**_**_**_*_****_*"rendements ((_*(_*(_*_)))*_). Tous les caractères sauf _sont interprétés comme des opérateurs, _dénote lui - même un identifiant.

Python 3, 226 octets

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

Définit une fonction anonyme nommée R .

Essayez-le en ligne!