Wprowadzenie

W dzieciństwie przychodzi moment, kiedy myślisz, że opanowałeś dodawanie i mnożenie, a potem ktoś przychodzi i informuje cię, że:

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

i że nie był to tak prosty lub liniowy proces, jak wcześniej nauczono. Dowiadujesz się, że istnieje coś o nazwie kolejność operacji . Jest to bardzo ważny sposób na zachowanie pewnego poziomu spójności i wyrażeń, bez nawiasów przeszkadzających we wszystkim.

Ogólna historia

Pewnego dnia budzisz się na tle paniki na ulicach. Ekstremistyczna grupa pod nazwą „ 2560 ” (skrót od „Organizacja przeciw porządkowi operacji”, z dziwnym zwrotem szesnastkowym) zastosowała swoje złe metody, aby przejąć kontrolę nad całą bronią nuklearną na świecie. Trzymają zakładników na całej planecie i mają proste żądanie: odwrócić przyjętą kolejność operacji lub wyeliminować twarz (nawiasy mają zachować swój priorytet). Nowy system nazywa się PSADME (nawiasy, odejmowanie / dodawanie, dzielenie / mnożenie, wykładniki), a wyrażenia oceniają od prawej do lewej:

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

Mijają dni i przejście jest w toku. Podczas gdy matematycy i fizycy są zajęci przepisywaniem swoich równań, informatycy stają przed zadaniem zmiany sposobu, w jaki wyrażenia matematyczne są interpretowane przez komputery. Należysz do tajnej grupy programistów rebeliantów, której celem jest spowodowanie tylu udręk dla nowych globalnych władców - i przypadkowo jesteś wybierany losowo przez The 2560 i ma za zadanie stworzyć program do obliczania testów porównawczych.

Twoja misja

Napisz program (lub funkcję), który pobiera (numeryczne) wyrażenie matematyczne jako dane wejściowe, oblicza wyrażenie za pomocą PSADME jako kolejności operacji i wyświetla wynik. Wyrażenia powinny oceniać od prawej do lewej, więc

Dla uproszczenia wszystkie podane liczby będą liczbami całkowitymi, a obliczenia dadzą wyniki całkowite.

Zasady i punktacja

• Program powinien akceptować wprowadzanie danych o długości do 128 znaków - jeśli Twój język / platforma ma mniejszą maksymalną długość wprowadzania, jest to dopuszczalna wymówka.
• Standardowe luki są zabronione.
• Zwycięski kod zostanie wybrany 18 listopada (4 tygodnie od tej daty ogłoszenia).
• Możesz wpisać kod pocztowy, który nie byłby warty gry w golfa. Chodzi o zabawę. Jeśli masz ciekawy sposób na zrobienie tego, ale nie możesz sam zagrać w golfa (lub z natury swojej metody), możesz mimo to opublikować.

Jak zwykle zwycięskim kodem jest ten, który ma najmniej bajtów, z pewnymi bonusami o wartości rozrywkowej:

• -5, aby uniknąć użycia znaków w podanym wyrażeniu: + , - , ( , ) , ^ , * , /
• -5 - wykonanie obliczeń zajmuje więcej niż 5 minut (ale nie więcej niż 10 minut), aby wykonać obliczenia na standardowym komputerze, przy czym metoda nie jest oczywista (przy użyciu zegara lub niepotrzebnych pętli); Celem jest przekonanie nowych władców, że nie próbujesz zakłócać obliczeń zagłady.
• - (5 + N) dla bezpośredniej ofensywnej wiadomości (o długości N, z wyłączeniem początkowych / końcowych białych znaków) na temat członków The 2560, które mają być napisane na pierwszy rzut oka w twoim kodzie, z niedorzecznym wyjaśnieniem, dlaczego musi to być tam. Jeśli zostanie usunięty, kod nie może działać poprawnie. Tak, darmowe punkty za wartość rozrywkową.

Przykłady i objaśnienia

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

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

Nowa definicja operatorów matematycznych dzięki nowym rozwiązaniom i priorytetom. Teraz:

*Main> 32 / 8 * 3 - 1
2

GNU sed -r z rozszerzeniem 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

Niezbyt krótki, ale wykonuje pracę.

sed nadaje się do analizowania pierwszeństwa, ale nie wykonuje arytmetyki. Używamy więc rozszerzenia GNU sed exec do spolecenia, aby zlecić powłoce niezbędną arytmetykę.

Na razie zakłada się, że wszyscy operatorzy, z wyjątkiem tego, ^że mają dokładnie jedno miejsce z przodu i z tyłu.

Wyjście testowe:

$ 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

Naprawiono błąd edycji (tylko literówka, 6 powinno być 4) - Dodano pełne wyjaśnienie na końcu fragmentu

Edycja 2 Znaleziono usprawnienia w pracy nad kolejnym wyzwaniem

Kolejne przeniesienie tego samego parsera z minimalną różnicą. (porównaj z tym )

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>