Introducción

Llega un punto en la infancia cuando crees que has dominado la suma y la multiplicación, luego aparece alguien y te informa que:

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

y que no fue un proceso tan simple o lineal como se le enseñó anteriormente. Aprendes que existe algo llamado orden de operaciones . Esta es una forma muy importante de mantener cierto nivel de consistencia y expresión, sin que los paréntesis se interpongan en el camino de todo.

Argumento genérico

Un día, te despiertas con el sonido del pánico en las calles. Un grupo extremista bajo el nombre de " The 2560 " (abreviatura de "Organización contra el orden de las operaciones", con un torpe giro hexadecimal) ha utilizado sus métodos malvados para tomar el control de todas las armas nucleares en el mundo. Están reteniendo a todo el planeta como rehenes, y tienen una simple demanda: invertir el orden aceptado de operaciones o enfrentar la erradicación (los paréntesis deben mantener su prioridad). El nuevo sistema se llama PSADME (paréntesis, resta / suma, división / multiplicación, exponentes), y las expresiones evalúan de derecha a izquierda:

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

Pasan los días y la transición está en progreso. Mientras que los matemáticos y físicos están ocupados reescribiendo sus ecuaciones, los informáticos se enfrentan a la tarea de cambiar la forma en que las computadoras interpretan las expresiones matemáticas. Perteneces a un grupo secreto de programación rebelde que tiene como objetivo causar tanto tormento a los nuevos señores mundiales, y, por casualidad, The 2560 te selecciona al azar y te encargará de producir el programa de cálculo de referencia.

Tu misión

Escriba un programa (o función) que tome una expresión matemática (numérica) como entrada, calcule la expresión usando PSADME como el orden de las operaciones y genere el resultado. Las expresiones deben evaluar de derecha a izquierda, por lo que

Para simplificar, todos los números proporcionados serán enteros, y los cálculos producirán resultados enteros.

Reglas y puntaje

• El programa debe aceptar entradas de hasta 128 caracteres de longitud; si su idioma / plataforma tiene una longitud máxima de entrada más baja, esa es una excusa aceptable.
• Las lagunas estándar están prohibidas.
• El código ganador se elegirá el 18 de noviembre (4 semanas a partir de esta fecha de publicación).
• Siéntase libre de publicar un código que no se consideraría digno de golf. Esto se trata de diversión. Si tiene una forma interesante de hacerlo pero no puede jugarlo usted mismo (o por la naturaleza de su método), puede publicarlo de todos modos.

Como de costumbre, el código ganador es el que tiene el menor número de bytes, con algunos bonos de valor de entretenimiento:

• -5 para evitar el uso de los caracteres en la expresión proporcionada: + , - , ( , ) , ^ , * , /
• -5 para realizar los cálculos toma más de 5 minutos (pero no más de 10 minutos) para calcular en una computadora estándar, sin que el método sea obvio (usando el reloj o bucles innecesarios); El objetivo es convencer a los nuevos señores de que no estás tratando de interrumpir sus cálculos de fatalidad.
• - (5 + N) para un mensaje ofensivo directo (de longitud N, sin incluir espacios en blanco iniciales / finales) sobre los miembros de The 2560 que se escribirán a la vista dentro de su código, con alguna explicación ridícula de por qué debe ser allí. Si se elimina, el código no debe funcionar correctamente. Sí, puntos gratis por valor de entretenimiento.

Ejemplos y explicaciones.

[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 bytes

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

Redefiniendo los operadores matemáticos con nuevas fijaciones y prioridades. Ahora:

*Main> 32 / 8 * 3 - 1
2

GNU sed -r con extensión 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

No es especialmente corto, pero hace el trabajo.

sed está bien para analizar la precedencia pero no hace aritmética. Entonces usamos la extensión GNU sed exec paras comando para externalizar la aritmética necesaria al shell.

Por ahora asume todos los operadores, con la excepción de ^tener exactamente un espacio delante y detrás.

Prueba de salida:

$ 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

Editar error corregido (solo un error tipográfico, 6 debería haber sido 4) - Se agregó una explicación completa al final del fragmento

Editar 2 Encontramos alguna mejora trabajando en otro desafío

Otra portada del mismo analizador con solo una mínima diferencia. (comparar con esto )

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>