introduction

Il arrive un moment dans l'enfance où vous pensez avoir maîtrisé l'ajout et la multiplication, puis quelqu'un arrive et vous informe que:

a * b + c = (a * b) + c! = a * (b + c),

et que ce n'était pas un processus aussi simple ou linéaire que vous l'avez appris plus tôt. Vous apprenez qu'il existe quelque chose appelé l' ordre des opérations . C'est un moyen très important de conserver un certain niveau de cohérence et d'expressions, sans que les parenthèses ne gênent tout.

Storyline générique

Un jour, vous vous réveillez au son de la panique dans les rues. Un groupe extrémiste sous le nom de " The 2560 " (abréviation de "Organisation Against the Order of Operations", avec une tournure hexagonale stupide) a utilisé ses méthodes diaboliques pour prendre le contrôle de toutes les armes nucléaires dans le monde. Ils tiennent la planète entière en otage, et ils ont une simple demande: inverser l'ordre des opérations accepté ou faire face à l'éradication (les parenthèses doivent maintenir leur priorité). Le nouveau système est appelé PSADME (parenthèses, soustraction / addition, division / multiplication, exposants), et les expressions évaluent de droite à gauche:

a - b - c = a - (b - c) = a + c - b

Les jours passent et la transition est en cours. Alors que les mathématiciens et les physiciens sont tous occupés à réécrire leurs équations, les informaticiens sont confrontés à la tâche de changer la façon dont les expressions mathématiques sont interprétées par les ordinateurs. Vous appartenez à un groupe de programmation rebelle secret qui vise à causer autant de tourments aux nouveaux suzerains mondiaux - et, par hasard, vous êtes sélectionné au hasard par le 2560 et chargé de produire le programme de calcul de référence.

Votre mission

Écrivez un programme (ou une fonction) qui prend une expression mathématique (numérique) en entrée, calcule l'expression en utilisant PSADME comme ordre d'opérations et sort le résultat. Les expressions doivent évaluer de droite à gauche, donc

Par souci de simplicité, tous les nombres fournis seront des nombres entiers et les calculs produiront des résultats entiers.

Règles et notation

• Le programme doit accepter la saisie d'une longueur maximale de 128 caractères - si votre langue / plate-forme a une longueur d'entrée maximale inférieure, c'est une excuse acceptable.
• Les failles standard sont interdites.
• Le code gagnant sera choisi le 18 novembre (4 semaines à compter de cette date de publication).
• N'hésitez pas à publier un code qui ne serait pas considéré comme digne du golf. C'est amusant. Si vous avez une façon intéressante de le faire mais que vous ne pouvez pas la jouer vous-même (ou par la nature de votre méthode), vous pouvez quand même la publier.

Comme d'habitude, le code gagnant est celui avec le moins d'octets, avec quelques bonus de valeur de divertissement:

• -5 pour éviter toute utilisation des caractères dans l'expression fournie: + , - , ( , ) , ^ , * , /
• -5 pour que les calculs prennent plus de 5 minutes (mais pas plus de 10 minutes) pour calculer sur un ordinateur standard, sans que la méthode soit évidente (en utilisant l'horloge ou des boucles inutiles); L'objectif est de convaincre les nouveaux suzerains que vous n'êtes pas essayer de perturber leurs calculs de malheur.
• - (5 + N) pour un message offensif direct (de longueur N, sans inclure les espaces blancs de début / fin) sur les membres du 2560 à écrire à la vue de votre code, avec une explication ridicule pour expliquer pourquoi il doit être Là. S'il est supprimé, le code ne doit pas fonctionner correctement. Oui, des points gratuits pour la valeur de divertissement.

Exemples et explications

[program] 2 - 2 - 2
2

2 - (2 - 2) = 2

[program] (2 + 2 * 3 + 3) / 3 + 3
4

(4 * 6) / (3 + 3) = 4

[program] 3 + 2 + 1 ^ 3
216

(3 + 2 + 1) ^ 3 = 216

[program] -5^2
25

(-5) ^ 2 = 25

[program] 32 / 8 * 3 - 1
2

32 / (8 * (3 - 1)) = 32/16 = 2

Haskell, 134 octets

import qualified Prelude as P
infixl 6 ^
(^)=(P.^)
infixr 8 + 
(+)=(P.+)
infixr 8 - 
(-)=(P.-)
infixr 7 /
(/)=P.div
infixr 7 *
(*)=(P.*)

Redéfinir les opérateurs mathématiques avec de nouvelles fixités et priorités. Maintenant:

*Main> 32 / 8 * 3 - 1
2

GNU sed -r avec extension exec, 398

s@ *\^ *@ ** @
:
s@\((-?[0-9]+)\)@\1@
t
s@(-?[0-9]+ - )+(-?[0-9]+ - -?[0-9]+)@\1(\2)@
t
s@(.*(^| |\())(-?[0-9]+ [-+] -?[0-9]+)(.*)@echo '\1'$((\3))'\4'@e
t
s@(-?[0-9]+ / )+(-?[0-9]+ / -?[0-9]+)@\1(\2)@
t
s@(.*(^| |\())(-?[0-9]+ [*/] -?[0-9]+)(.*)@echo '\1'$((\3))'\4'@e
t
s@(-?[0-9]+ \*\* )+(-?[0-9]+ \*\* -?[0-9]+)@\1(\2)@
t
s@(.*(^| |\())(-?[0-9]+ \*\* -?[0-9]+)(.*)@bash -c 'echo \1$[\3]\4'@e
t

Pas particulièrement court, mais fait le travail.

sed est OK pour analyser la priorité mais ne fait pas d'arithmétique. Nous utilisons donc l'extension GNU sed exec pour les commande pour sous-traiter l'arithmétique nécessaire au shell.

Pour l'instant suppose tous les opérateurs, à l'exception d' ^avoir exactement un espace devant et derrière.

Sortie de test:

$ cat psadme.txt 
2 - 2 - 2
(2 + 2 * 3 + 3) / 3 + 3
3 + 2 + 1 ^ 3
-5^2
32 / 8 * 3 - 1
$ sed -rf psadme.sed psadme.txt 
2
4
216
25
2
$ 

JavaScript (ES6) 287 300

Modifier le bug corrigé (juste une faute de frappe, 6 aurait dû être 4) - Ajout d'une explication complète à la fin de l'extrait

Edit 2 Trouvé une amélioration en travaillant sur un autre défi

Encore un autre portage du même analyseur avec juste une différence minime. (comparer avec cela )

f=(x,W=[],Q=['('],z=1,h=p=>'+-*/^^))('.indexOf(p)>>1,C=n=>{for(;h(q=Q.pop())<h(n);W.push(q=='^'?Math.pow(a,b):eval(`a${q}b`)))a=W.pop(b=W.pop());z&&Q.push(q,n)})=>((x+')').replace(/\d+|\S/g,t=>t>'('?t>'('?~h(t)?z&&t=='-'?z=-z:C(t,z=1):(W.push(z*t),z=0):C(t,z=0):(Q.push(t),z=1)),W.pop())

// More readable
U=(x,W=[],Q=['('],z=1,
  h=p=>'+-*/^^))('.indexOf(p)>>1,
  C=n=>{
    for(;h(q=Q.pop())<h(n);
        W.push(q=='^'?Math.pow(a,b):eval(`a${q}b`)))
      a=W.pop(b=W.pop());
    z&&Q.push(q,n)
  }
)=>(
  (x+')')
  .replace(/\d+|\S/g,t=> 
       t>'('
       ?t>'('
       ?~h(t)
       ?z&&t=='-'?z=-z:C(t,z=1)
       :(W.push(z*t),z=0)
       :C(t,z=0)
       :(Q.push(t),z=1)
  ),
  W.pop()
)

// TEST
console.log=(...x)=>O.innerHTML+=x.join` `+'\n'

console.log(f('1 - 3 + 4')) // -6
console.log(f('2-2-2')) // 2
console.log(f('(2 + 2 * 3 + 3) / 3 + 3')) // 4
console.log(f('3 + 2 + 1 ^ 3')) // 216
console.log(f('-5^2')) // 25
console.log(f('32 / 8 * 3 - 1')) // 2

// Explained
X=(x,W=[],Q=['('],z=1,
  h=p=> // operator priority '+-:1, */:3, ^:5, ):7, (:9. If an operand then -1
     '+-*/^^))('.indexOf(p)>>1,
  C=n=>{ // Evaluate operators present on stack if they have upper priority, then push new operator on stack
    //console.log('Operand '+n)
    while( h(q = Q.pop()) < h(n) ) // pop operator from op stack and compare priority with current
    {
      // Pop operands from stack and push result
      b = W.pop();
      a = W.pop();
      r = q=='^' ? Math.pow(a,b) : eval('a'+q+'b')
      // console.log('Evaluate '+a+q+b+'='+r)
      W.push(r);
    }
    // if z == 0 do nothing, because the current operands are '(' and ')' that must be discarded
    // else Push again the last operator popped and the current one
    z && Q.push(q, n) // 
  }
)=>(
  (x+')')
  .replace(/[\d.]+|\S/g,t=> {
    //console.log('Q:'+Q,'W:'+W,'T:'+t,'U:'+h(t),'Z:'+z), // display status
    if (t == '(') 
    { // open parenthesis
      z = 1
      Q.push(t) // push a operator, its the highest priority
    }
    else if (t == ')')
    { //close parenthesis
      z = 0
      C(t) 
    }
    else if (h(t) < 0)
    { // operand
      W.push(z*t) // push operand with right sign
      z = 0 // set z to 0 to mark that we just pushed an operand, so next '-' (if present) is a binary operator 
    }
    else
    { // operator
      if (z && t=='-') // the minus is an unary operator (the only unary operator allowed is '-', '+' will not work)
        z =-z // change the sign
      else
        z = 1, // no unary minus
        C(t)
    }    
  }),
  W.pop() // return the value at top of operand stack
)

<pre id=O></pre>