Convertir une expression en notation Panfix

19

Je parcourais les esolangs et suis tombé sur cette langue: https://github.com/catseye/Quylthulg .

Une chose intéressante à propos de ce langage, c'est qu'il n'utilise pas de préfixe, de suffixe ou d'infixe, il utilise les trois , appelant cela la notation "panfix".

Voici un exemple. Pour représenter infix normale 1+2dans panfix, il devient: +1+2+. Remarquez comment l'opérateur est à la fois avant, entre et après les opérandes. Un autre exemple est (1+2)*3. Cela devient *+1+2+*3*. Remarquez à nouveau comment se *trouve dans les trois endroits par rapport aux opérandes +1+2+et 3.

Le défi

Comme vous l'avez peut-être deviné, votre tâche dans ce défi est de convertir une expression d'infixe en panfix.

Quelques précisions:

  • Vous n'avez qu'à gérer les quatre opérations de base: +-*/
  • Vous n'aurez pas à vous occuper des versions unaires de celles-ci, seulement binaires
  • Vous devez gérer les parenthèses
  • Supposons les règles de priorité normales d' */alors +-et d'associativité gauche pour chacun d'eux.
  • Les nombres seront des entiers non négatifs
  • Vous pouvez éventuellement avoir des espaces à la fois en entrée et en sortie

Cas de test

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

C'est le code-golf , donc le code le plus court en octets gagne!

code-golf parsing conversion Maltysen
la source

Réponses:

3

JavaScript (ES6), 160 octets

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)

Travaux en citant tous les opérateurs ( ce qui leur donne des codes de caractère avant *), alors à la recherche disponible '*'ou '/'opérations, '+'ou les '-'opérations ou ()s, et le remplacement du premier par sa notation panfix. Exemple:

(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
la source
3

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

~ 15 octets grâce à 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))

En JavaScript, c'est un peu plus difficile qu'en Mathematica. Il s'agit essentiellement d'un analyseur de priorité opérateur trop spécialisé et golfé .

Provoque des débordements de pile sur des entrées non valides.

Démo

Afficher l'extrait de code

Non golfé

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
la source
S.split``devrait être [...S], même si cela peut réellement aider à faire correspondre à l' /\d+|./gavance et à travailler à la place.
Neil
@Neil Merci. J'examinerai cela.
PurkkaKoodari
2

Mathematica, 203 195 octets

C'est probablement moins qu'efficace, mais semble faire le travail.

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]

Il s'agit d'une fonction anonyme qui prend une expression réelle et renvoie une chaîne avec la notation panfix. Mathematica trie la priorité des opérateurs au moment de l'analyse, plutôt qu'au moment de l'évaluation, donc l'imbrication doit être correcte automatiquement. Au moins, les cas de test fonctionnent comme prévu.

Explication: Il est assez facile d'interpréter l'expression entière comme un arbre, comme ceci:

arbre

À ce stade, les opérateurs (chaque nœud qui n'est pas une feuille) ne sont plus des opérateurs, ils ont en fait été convertis en chaînes telles que "+". Les entiers sont également convertis en chaînes. Ensuite, une règle de remplacement répétée convertit chaque nœud qui a exactement deux feuilles en panfix parent-leaf1-parent-leaf2-parent. Après quelques itérations, l'arborescence se réduit à une seule chaîne.

La principale perte du nombre d'octets est que Mathematica interprète

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

Et cela se produit également au moment de l'analyse.

Golfé un peu, car le motif a_/b_est également interprété comme a_ * (b_)^(-1). Quelques optimisations mineures ailleurs.

LLlAMnYP
la source
1

Prolog, 87 octets

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

C'est une fonction (principalement parce que l'écriture d'un programme complet a des niveaux cauchemardesques dans Prolog; normalement, même si vous compilez un programme, elle produit un REPL lors de son exécution), appelée p. Il prend l'entrée de stdin et les sorties sur stdout. Notez que vous devez ajouter un point à l'entrée, ce qui est une conséquence malheureuse de la façon dont les routines d'entrée de Prolog fonctionnent (elles utilisent les périodes dans l'entrée de la même manière que les autres langues utilisent les nouvelles lignes); qui pourrait ou non disqualifier la réponse.

Explication

Les opérateurs arithmétiques, dans Prolog, sont normalement interprétés comme des constructeurs de tuple . Cependant, ils obéissent aux mêmes règles de priorité que les opérateurs arithmétiques réels sur lesquels ils sont basés; vous pouvez former des tuples avec la notation infixe et +et -lier moins étroitement que *et /, avec la priorité prise de gauche à droite dans un groupe. C'est exactement ce que demande la question; ainsi, nous pouvons lire un tuple imbriqué entier à partir de l'entrée, et il a déjà la bonne structure. Voilà ce qui pfait.

Ensuite, nous devons le convertir en notation panfix. xconvertit l'entrée dans une liste panfixed des constructeurs et des entiers, et peut être lu comme une phrase en anglais presque directement: « xde Test: si Tun tuple avec le constructeur Oet les arguments A, Bpuis O, xde A, O, xde B, O, d' autre T». Enfin, il suffit d'imprimer la liste sans séparateur (c'est-à-dire en utilisant maplistpour appeler writechaque élément de la liste).

J'ai utilisé SWI-Prolog pour tester cela, parce que ma version de GNU Prolog n'a pas maplistencore (apparemment, il a été ajouté à une version plus récente), mais il devrait généralement être assez portable entre les implémentations de Prolog.

Communauté
la source