13
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ 1 - 3 + 4 = 1 - 7? Right to left would suggest so, but that's putting addition ahead of subtraction, contrary to PSADME, no? \$\endgroup\$ – LLlAMnYP Oct 21 '15 at 12:24
  • 1
    \$\begingroup\$ @LLlAMnYP Addition and subtraction are in the same "group", just like in PEMDAS, so they happen right to left. Same with multiply/divide. It's more like P(SA)(DM)E. \$\endgroup\$ – Geobits Oct 21 '15 at 12:33
  • 2
    \$\begingroup\$ The statement isn't meant to be processed right-to-left - rather, operations of equal precedence are evaluated right-first. So 4/2 = 2, 2-1 = 1, but a/bc = a/(bc) rather than the usual (a/b)*c. I hope this clears things up. \$\endgroup\$ – JArkinstall Oct 21 '15 at 13:10
  • \$\begingroup\$ Probably the easiest way to do this is to write up a flex/bison or lex/yacc grammar. \$\endgroup\$ – user15259 Oct 21 '15 at 18:47
  • 5
    \$\begingroup\$ You should change the acronym to PADME, since members of such an evil organisation would most certainly like the newer Star Wars trilogy more than the originals. It's also easier to remember. \$\endgroup\$ – mbomb007 Oct 21 '15 at 22:00
9
\$\begingroup\$

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
\$\endgroup\$
  • 1
    \$\begingroup\$ Wow. Just, wow. Is this even possible in any other language? +1 \$\endgroup\$ – ETHproductions Oct 22 '15 at 1:16
  • \$\begingroup\$ I was quite sure, it was possible in Mathematica, or at least a similar approach, but quickly realized, I lack the knowledge to make it. \$\endgroup\$ – LLlAMnYP Oct 22 '15 at 7:36
  • 1
    \$\begingroup\$ I am new enough here to be unsure as to whether the following suggestion is usually acceptable on this forum. It is based entirely on your code, but is a bash script which uses Perl to generate the Haskell file and pass it to GHCi. By doing so, I save a WHOLE BYTE. perl -e'$_="import qualified Prelude as Pl 6^r 8+r 8-r 7*r 7/";s/(. \d(.))/\ninfix\1\n(\2)=(P.\2)/g;s~\./~.div~;print'>a.hs;ghci a.hs Unfortunately, a typo made the generated code lack a space between the digit and the symbol, but still runs fine. This means your code can lose 5 bytes, and beats my 'improvement'. \$\endgroup\$ – JArkinstall Oct 22 '15 at 15:34
  • \$\begingroup\$ @JArkinstall For what its worth, my answer is effectively using sed to generate and evaluate shell code. Probably a good meta question. \$\endgroup\$ – Digital Trauma Oct 22 '15 at 16:39
  • \$\begingroup\$ That is true, and I really like your approach - however, using a tool (perl or sed) to generate a file in a language which is then read into another language seems one step further. I wouldn't be overly surprised if there exists a way of producing the above code via another generator (although the method isn't obvious to me!), and we would find ourselves in parse-ception. If this is allowable, one could even apply this approach to your code (and a few examples I have seen in some of the more readable-language answers to some challenges on this board). \$\endgroup\$ – JArkinstall Oct 22 '15 at 16:46
2
\$\begingroup\$

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
$ 
\$\endgroup\$
  • \$\begingroup\$ Nice profile picture. xD \$\endgroup\$ – Oliver Ni Oct 24 '15 at 1:18
1
\$\begingroup\$

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>

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.