Operations of order

Question

Introduction

There comes a point in childhood when you think you've mastered adding and multiplying, then someone comes along and informs you that:

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

and that it wasn't as simple or linear a process as you were earlier taught. You learn that there exists something called the order of operations. This is a very important way of keeping some level of consistency and in expressions, without having parentheses getting in the way of everything.

Generic storyline

One day, you wake up to the sound of panic in the streets. An extremist group under the name "The 2560" (Short for "Organisation Against the Order of Operations", with a dorky hex-ish twist) have used their evil methods to take control over all of the nuclear weapons in the world. They are holding the whole planet hostage, and they have a simple demand: reverse the accepted order of operations or face eradication (parentheses are to maintain their priority). The new system is called PSADME (parentheses, subtraction/addition, division/multiplication, exponents), and expressions evaluate right-to-left:

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

Days pass, and the transition is in progress. Whilst mathematicians and physicists are all busy rewriting their equations, the computer scientists are faced with the task of changing the fashion in which mathematical expressions are interpreted by computers. You belong to a secret rebel programming group which aims to cause as much torment for the new global overlords - and, by chance, you are randomly selected by The 2560 and tasked to produce the benchmark calculation program.

Your mission

Write a program (or function) which takes a (numerical) mathematical expression as input, calculates the expression using PSADME as the order of operations and outputs the result. Expressions should evaluate right-to-left, so $$1 - 3 + 4 = 1 - 7 = -6.$$

For simplicity, all numbers provided will be integers, and the calculations will produce integer outcomes.

Rules and scoring

• The program should accept input up to 128 characters in length - if your language/platform has a lower maximum input length, that is an acceptable excuse.
• Standard loopholes are forbidden.
• The winning code will be chosen on 18th November (4 weeks from this post date).
• Feel free to post code that would not be considered golf-worthy. This is about fun. If you have an interesting way of doing this but can't golf it yourself (or by the nature of your method), you can post it anyway.

As per usual, the winning code is the one with least number of bytes, with some entertainment-value bonuses:

• -5 for avoiding any use of the characters in the provided expression: +,-,(,),^,*,/
• -5 for making the calculations take more than 5 minutes (but no more than 10 minutes) to calculate on a standard computer, without the method being obvious (using the clock or unnecessary loops); The aim is to convince the new overlords that you are not trying to disrupt their calculations of doom.
• -(5+N) for a direct offensive message (of length N, not including leading/trailing whitespace) about the members of The 2560 to be written in plain sight within your code, with some ridiculous explanation as to why it needs to be there. If it is removed, the code must not function correctly. Yes, free points for entertainment value.

Examples and explanations

[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

Answer 1

Haskell, 134 bytes

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

Redefining the math operators with new fixities and priorities. Now:

*Main> 32 / 8 * 3 - 1
2

Answer 2

GNU sed -r with exec extension, 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

Not especially short, but gets the job done.

sed is OK for parsing out the precedence but doesn't do arithmetic. So we use the GNU sed exec extension to the s command to outsource the necessary arithmetic to the shell.

For now assumes all operators, with the exception of ^ have exactly one space in front and behind.

Test output:

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

Answer 3

JavaScript (ES6) 287 300

Edit Bug fixed (just a typo, 6 should have been 4) - Added a complete explanation at the end of the snippet

Edit 2 Found some improvement working on another challenge

Yet another porting of the same parser with just some minimal difference. (compare with this)

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>