Diutamakan operator: Betapa salahnya saya?

65

Katakanlah saya memiliki ekspresi:

9 * 8 + 1 - 4

Ungkapan ini dapat ditafsirkan dalam enam cara berbeda, tergantung pada prioritas operator:

(((9 * 8) + 1) - 4) = 69 (* + -)
((9 * 8) + (1 - 4)) = 69 (* - +)
((9 * (8 + 1)) - 4) = 77 (+ * -)
(9 * ((8 + 1) - 4)) = 45 (+ - *)
((9 * 8) + (1 - 4)) = 69 (- * +)
(9 * (8 + (1 - 4))) = 45 (- + *)

Katakanlah saya seorang pengembang, dan saya tidak ingin menghafal tabel prioritas, dll., Jadi saya hanya akan menebak.

Dalam hal ini, margin kesalahan terbesar adalah 45-77, yang merupakan perbedaan 32. Ini berarti bahwa tebakan saya hanya akan dimatikan oleh maksimum 32.

Tantangan

Mengingat ekspresi yang terdiri dari angka dan +, -, *, /(pembagian integer) dan% , output perbedaan mutlak dari nilai yang mungkin terbesar dan terkecil untuk ekspresi yang, berdasarkan didahulukan dari operator.

Spesifikasi

  • Ekspresi input tidak akan mengandung tanda kurung dan setiap operator adalah asosiatif kiri.
  • Ekspresi input hanya akan mengandung bilangan bulat tidak negatif. Namun, subekspresi dapat dievaluasi menjadi negatif (misalnya 1 - 4).
  • Anda dapat mengambil ekspresi dalam format apa pun yang masuk akal. Sebagai contoh:
    • "9 * 8 + 1 - 4"
    • "9*8+1-4"
    • [9, "*", 8, "+", 1, "-", 4]
    • [9, 8, 1, 4], ["*", "+", "-"]
  • Input akan berisi setidaknya 1 dan paling banyak 10 operator.
  • Ekspresi apa pun yang berisi pembagian atau modulo dengan 0 harus diabaikan.
  • Anda dapat mengasumsikan bahwa modulo tidak akan diberikan operan negatif.

Uji Kasus

9 * 8 + 1 - 4             32
1 + 3 * 4                  3
1 + 1                      0
8 - 6 + 1 * 0              8
60 / 8 % 8 * 6 % 4 * 5    63
Buah Esolanging
sumber
1
@AndersKaseorg Sepertinya Anda memperlakukan %memiliki dua prioritas berbeda dalam contoh kedua Anda.
Buah Esolanging
1
Tiga dari 'enam' identik, seperti dua lainnya. Itu menyisakan tiga kasus aktual, bukan enam.
user207421
3
bagaimana %operator bekerja pada angka negatif? Cara seperti C atau Python atau yang lainnya?
tsh
8
Hanya dengan mengatakan, Anda tidak perlu menambahkan bagian "dan saya malas" ke deskripsi Anda. Hanya mengatakan Anda seorang pengembang sudah cukup. :)
Gryphon - Reinstate Monica
1
@ tsh Perilaku apa pun. Melakukan apapun yang Anda inginkan. Anda dapat membuat iblis terbang dari hidung saya .
Buah Esolanging

Jawaban:

27

Python 2 , 171 156 byte

lambda a:max(e(a))-min(e(a))
u=')%s('
def e(a,t=u):
 try:b=[eval(a)]
 except:b=[]
 return sum([e('(%s)'%a.replace(o,t%o),u%t)for o in"+-*/%"if' '+o in a],b)

Cobalah online!

Bagaimana itu bekerja

Kami mengelilingi setiap operator dengan jumlah berbeda dari pasangan kurung yang menghadap ke luar untuk mensimulasikan berbagai prioritas (dalam semua cara yang mungkin), dan membungkus pasangan kurung yang menghadap ke dalam di sekitar seluruh string, untuk mendapatkan ekspresi yang kami bisa eval. Misalnya dengan

+)+(
*))*((
-)))-(((

kita mendapatkan

9 * 8 + 1 - 4(((9 ))*(( 8 )+( 1 )))-((( 4)))= 77.

Anders Kaseorg
sumber
Anda dapat menyimpan 2 byte dengan menggerakkan bagian orluar sumuntuk menghapus lapisan tanda kurung: sum([...],[])or[eval(a)]bukannyasum([...]or[[eval(a)]],[])
Strigoides
@Strigoides Saya telah berpikir bahwa itu tidak setara, karena summungkin kosong tanpa argumennya kosong — namun, sebenarnya baik-baik saja karena evalharus gagal dalam kasus itu. Terima kasih.
Anders Kaseorg
8

Jelly , 126 byte

"Operator Precedence? Kurung? Pah, siapa yang butuh itu?" - Tantangan menggunakan Jelly untuk tantangan prioritas operator.

⁾[]i$€Ḥæ%3+\¬œp¹Ḋ€
ǵḟØDO%9µÐṀṪɓœṣ⁹,ṚÑj@¥/
ǵVṾµ1ĿFḟØDḟ”-Lµ?ÐL
5Ḷx@€“]“[”ż⁸j/€,@y³Fɓ³i@€Ṁ’x@“[“]”jÇ
“+_×:%”Œ!Ç€µṾL_L’ỊµÐfV€ṢIS

Cobalah online!

Input diambil sebagai string, misalnya "1 + 2_3 × 4: 5% 6". Catatan penggandaan menggunakan "×" bukan "*", pembagian menggunakan ":" alih-alih "/", dan pengurangan menggunakan "_" bukannya "-".

Bagaimana itu bekerja Program ini dibagi menjadi tiga bagian: menghasilkan semua ekspresi dari prioritas operator yang berbeda, mengevaluasinya, dan mengembalikan perbedaan antara maksimum dan minimum.

Semua ekspresi dihasilkan dengan kode:

5Ḷx@€“]“[”ż⁸j/€,@y³Fɓ³i@€Ṁ’x@“[“]”jÇ (4) helper link: returns all outputs given a permutation. Input e.g. "_+:×%"
5Ḷx@€“]“[”           - repeat outer brackets to get ["",""],["]","["],["]]","[["],["]]]","[[["],["]]]]","[[[["]
          ż⁸j/€      - insert the operations in to get "_","]+[","]]:[[","]]]×[[[","]]]]%[[[["
               ,@    - turn this into a mapping equivalent to "_"↦"_","+"↦"]+[",":"↦"]]:[[","×"↦"]]]×[[[","%"↦"]]]]%[[[["
                 y³F - use this mapping to get the right number of outward brackets on each operation. e.g. "1]+[3]]]×[[[4"
ɓ³i@€Ṁ’x@“[“]”j      - add the right number of brackets to the end to get e.g."[[[1]+[3]]]×[[[4]]]"
               Ç     - this calls the link which evaluates the expression
“+_×:%”Œ!Ç€                          (5a) main link. Input e.g. "1+3×4"
“+_×:%”                                 - the string "+_×:%"
       Œ!                               - all permutations
         ǀ                             - apply link (4) to each permutation

Tautan dievaluasi dengan ini (saya mungkin bisa memperbaiki dengan struktur yang berbeda):

⁾[]i$€Ḥæ%3+\¬œp¹Ḋ€      (1) Helper link: Outputs a list of expressions within brackets, e.g. "[[[1]+[3]]]×[[[4]]]"↦"[[1]+[3]]","[[4]]"
⁾[]i$€Ḥæ%3                 - map "[" to 2, "]" to -2, and any other character to 0.
          +\¬              - cumulative sum negated: 1s at characters not in brackets (includes opening brackets), 0s otherwise (includes closing brackets)
             œp¹           - partition the input, not including borders, based on the sum to get "[[[1]+[3]]","[[[4]]"
                Ḋ€         - remove opening brackets
ǵḟØDO%9µÐṀṪɓœṣ⁹,ṚÑj@¥/ (2) Return the input to this link with one of the expressions from (1) evaluated
ǵVṾµ1ĿFḟØDḟ”-Lµ?ÐL     (3) link called from part 1: Evaluates expressions
 µ  µ          µ?          - if:
     1ĿFḟØDḟ”-L            - the input contains no operators within brackets:         
  VṾ                         - evaluate this one expression with normal Jelly calculation and return to string
                           - otherwise:
Ç                            - evaluate one subexpression using link (2)
                  ÐL       - repeat this until a single output is determined

Perbedaan antara maksimum dan minimum dihitung dengan kode dalam tautan (5):

µṾL_L’ỊµÐfV€ṢIS (5b) determine difference between minimum and maximum
µ      µÐf        - filter out outputs involving division or modulo by 0. Determined with:
 ṾL_L’Ị           - actual numbers have their unevaled form Ṿ no more than one byte longer than the non-unevaled form.
          V€      - evaluate each of these valid numbers to get integers from strings
            Ṣ     - sort
             IS   - return the sum of all difference between consecutive elements.
fireflame241
sumber
4
Mungkin jawaban Jelly terpanjang (tanpa data yang disematkan) yang pernah saya lihat. Sudah selesai dilakukan dengan baik!
Keyu Gan
@KeyuGan Jika Anda ingin jawaban Jelly lebih lama, lihat jawaban ini . Saya tidak bisa memikirkan jawaban Jelly panjang lainnya tanpa kompresi.
fireflame241
6

Python 2 , 235 234 233 226 byte

-1 byte (dan perbaikan) berkat Anders Kaseorg !

-7 byte berkat Langkah Hen !

from itertools import*
def f(e,a=()):
 for o in permutations("+-*/%"):
	l=e[:]
	for c in o:
	 for i in range(len(l),0,-1):
		if l[i-1]==c:l[i-2:i+1]=["("+l[i-2]+l[i-1]+l[i]+")"]
	try:a+=eval(*l),
	except:0
 print max(a)-min(a)

Cobalah online!

notjagan
sumber
1
Pengajuan fungsi harus dapat digunakan kembali . Anda dapat memperbaiki masalah itu dengan membiarkan amenjadi tuple bukan daftar, dan bahkan menyimpan 1 byte dengan melakukannya ( a=(), a+=eval(*l),).
Anders Kaseorg
Hah, TIL. Terima kasih atas tipnya!
notjagan
1
Karena Anda menggunakan Python 2, Anda dapat menyimpan beberapa byte dengan mengganti spasi dan tab untuk indentasi (dalam hal ini, 2 spasi -> tab, tiga spasi -> tab + spasi, empat spasi -> dua tab) Cobalah secara online!
Stephen
4

Haskell 582 byte

Ini tidak berjalan hampir sebaik yang saya harapkan ...

import Data.List
f x=case x of '+'->(+);'-'->(-);'*'->(*);'/'->div;_->rem
e _ s[]=s
e 1 s(')':x:a)|0<-(read$e 0""a),(x=='%'||x=='/')=""|""<-(e 0""s)=""|""<-(e 0""a)=""|0<3=show$(f x)(read$e 0""s)$read$e 0""a
e 1 s")"=e 0""s
e n s(')':a)=e(n-1)(s++")")a
e 0 s('(':a)=e 1 s a
e n s('(':a)=e(n+1)(s++"(")a
e n s(x:a)=e n(s++[x])a
n?s=take n$cycle s
a!b=e 0""(9?"("++(concat$zipWith(++)a(b++[[]]))++9?")")
c#b|l<-[read x|x<-map(c!)(a b),x/=""]=maximum l-minimum l
a c=transpose$map(\x->map((\(Just q)->q).lookup x)$map(\a->zipWith(\x y->(y,x?")"++y:x?"("))[1..5]a)$permutations"+-*%/")c

Cobalah secara Online!

Mencoba bermain golf dengan program panjang hanya membuat saya menulis kode yang buruk :(

Saya mencoba menggunakan algoritma Anders di Haskell, tetapi itu keluar dari kendali saya

Fungsi e seperti kasus eval tertentu. (#) mengambil daftar string yang mewakili bilangan bulat dan serangkaian operator dan mengembalikan perbedaan antara nilai maksimum dan minimum yang mungkin. misalnya

(#) ["9","8","1","4"] "*+-" => 32
H.Piz
sumber
1
Jika Anda berganti nama #menjadi ##, Anda dapat mengubah nama emenjadi (#), seperti:(n#s)(x:a)=...
Esolanging Fruit
Jika Anda alias tiga fungsi berikut yang umum digunakan, Anda dapat menyimpan 6 byte lebih lanjut. r=read;j=zipWith;o=mapdan kemudian ganti fungsi-fungsi itu dengan huruf alias.
maple_shaft
Saya juga menghitung 594 byte, bukan
582.
3

Pyth, 45 byte

KS.nm.x.vj\ u.nm+*H/kHckHGd]s.iFQY.p_{eQ-eKhK

Saya yakin bahwa lebih banyak optimasi dapat dilakukan, tetapi saya sangat menyukainya sejauh ini.

Mengambil input seperti ini: [9, 8, 1, 4], ["*", "+", "-"].

Cobalah online!

Trebuchette
sumber
2
Bisakah Anda menambahkan penjelasan?
Jim
2

Mathematica, 186 164 159 byte

eMax@#-Min@#&[Fold[#//.{m___,x_,#2[[0]],y_,n___}:>{m,x~Last@#2~y,n}&,e,#]&/@Permutations@{"+"@Plus,"-"[#-#2&],"*"@Times,"/"@Quotient,"%"@Mod}/. 0/0|1/0->{}]

\[Function] membutuhkan 3 byte.

Beberapa alternatif (tetap bytecount sama)

#2-#&@MinMax[...] untuk menggantikan Max@#-Min@#&[...]

Head@#2 untuk menggantikan #2[[0]]

Cobalah online di http://sandbox.open.wolframcloud.com : masukkan ( .... )[{60, "/", 8, "%", 8, "*", 6, "%", 4, "*", 5}]dengan ....diganti dengan kode di atas untuk test case 60 / 8 % 8 * 6 % 4 * 5. Tekan Shift + enteruntuk mengevaluasi.

pengguna202729
sumber
2

Javascript, 280 byte

Catatan : Putaran pembagian bilangan bulat menggunakan fungsi lantai, yang berarti bahwa angka negatif membulatkan dari nol.

Solusi ini didasarkan pada jawaban ini .

b=>(Math.max(...(f=(a,h="(",i=")",r=[...a[d="replace"](/[^-+*/%]|(.)(?=.*\1)/g,"")])=>(r[0]?(r.map((c,j)=>s=s.concat(f(h+a[d](RegExp("\\"+(n=r.concat()).splice(j,1),"g"),i+c+h)+i,h+"(",i+")",n)),s=[]),s):(a=eval(`(${a})`[d](/\(/g,"Math.floor(")))==a&&1/a?a:r))(b))-Math.min(...f(b)))

Cuplikan kode contoh:

g=

b=>(Math.max(...(f=(a,h="(",i=")",r=[...a[d="replace"](/[^-+*/%]|(.)(?=.*\1)/g,"")])=>(r[0]?(r.map((c,j)=>s=s.concat(f(h+a[d](RegExp("\\"+(n=r.concat()).splice(j,1),"g"),i+c+h)+i,h+"(",i+")",n)),s=[]),s):(a=eval(`(${a})`[d](/\(/g,"Math.floor(")))==a&&1/a?a:r))(b))-Math.min(...f(b)))

for(k=0;k<5;k++)
  v=["9*8+1-4","1+3*4","1+1","8-6+1*0","60/8%8*6%4*5"][k],
  console.log(`g(${v}) = ${g(v)}`)

Herman L.
sumber
Seberapa sulit untuk membuatnya sesuai dengan mengganti a / b case dengan a / b | 0?
trlkly
@trlkly a/b|0menghentikan pemeriksaan kesalahan divide / modulo 0, tetapi Math.floor(a/b)berhasil
Herman L
2

Haskell , 254 byte

import Data.List.Split
import Data.List
f s=(-)<$>maximum<*>minimum$permutations(zip"+-*/%"[p(+),p(-),p(*),c$div,c$mod])>>=(s!)
p=((pure.).)
c o a b=[o a b|b/=0]
s![]=[read s]
s!((x,o):y)=case splitOn[x]s>>=(!y)of[]->[];l->l?o
[a]?_=[a]
(a:b)?o=b?o>>=o a

Cobalah online!

Input adalah seluruh string, seperti 4 + 5 * 2. Ini menghasilkan semua permutasi operasi, dan untuk setiap permutasi membagi string secara rekursif. Ini memfilter divisi dengan 0 dengan daftar monad.

bartavelle
sumber
(%)adalah operator modulus. Ini adalah sisa dari operasi pembagian antara argumen kiri dan argumen kanan.
maple_shaft
1

Python 2 , 262 256 254 byte

from itertools import*
def r(s,o):
 try:
  while o in s:i=s.index(o)-1;s[i:i+3]=[`eval(''.join(s[i:i+3]))`]
  return s
 except:0
def f(s):
 u=[int(v[0])for v in [reduce(r,O,s.split(' '))for O in permutations('*/%+-')]if v!=None];return abs(max(u)-min(u))

Cobalah online!

Chas Brown
sumber
Simpan beberapa byte dengan juga menggunakan tab: Coba online!
Stephen
1
Simpan satu byte dengan mengubah in [ke in[(space tidak diperlukan)
Zacharý
1

PHP , 316 byte

<?for(;$t++<54322;)count_chars($t,3)!=12345?:$p[]=$t;foreach($p as$x){for(list($z,$q)=$_GET,$b=1,$i=0;$y=strtr($x,12345,"/%*+-")[$i++];)while(-1<$k=array_flip($q)[$y]){$n=$k+1;if($b&=$z[$n]||ord($y)%10<6)eval("\$z[$k]=$z[$k]$y$z[$n]^0;");($s=array_splice)($z,$n,1);$s($q,$k,1);}$b?$r[]=$z[0]:0;}echo max($r)-min($r);

Cobalah online!

Expanded
for(;$t++<54322;)
  count_chars($t,3)!=12345?:$p[]=$t;
foreach($p as$x){
  for(list($z,$q)=$_GET,$b=1,$i=0;$y=strtr($x,12345,"/%*+-")[$i++];)
    while(-1<$k=array_flip($q)[$y]){
      $n=$k+1;
      if($b&=$z[$n]||ord($y)%10<6)
        eval("\$z[$k]=$z[$k]$y$z[$n]^0;");
      ($s=array_splice)($z,$n,1);
      $s($q,$k,1);
    }
  $b?$r[]=$z[0]:0;
}
echo max($r)-min($r);
Jörg Hülsermann
sumber
Kasing kasus adalah 63. Kesalahan Anda karena memberikan operator yang sama diutamakan di bagian yang berbeda dari satu ekspresi
H.PWiz
0

Python 3 , 284 byte

Sunting: sepertinya ada yang salah dengan mengevaluasi contoh terakhir. Saya akan memeriksanya besok.

Jawaban Python lainnya. Tidak bisa mengungguli orang lain, tapi saya menghabiskan terlalu lama dalam hal ini untuk tidak memasangnya.

from itertools import*
def f(n,o):
 z=[]
 for p in permutations("+-*/%"):
  try:
   p,x,a=[*p],n[:],o[:]
   while(p):
    for i,d in enumerate(a):
     if d==p[0]:x[i+1]=str(eval(x[i]+d+x[i+1]));x.pop(i);a.pop(i)
    p.pop(0)
   z+=x
  except:0
 z=[*map(float,z)];return max(z)-min(z)

Cobalah online!

tukang sihir
sumber
1
while(p)dapat menjadi while puntuk satu byte yang disimpan.
Zacharý
0

Clojure (+ kombinatorik), 342 377 + 41 = 418 byte

+35 byte karena bug.

(fn[x y](let[l filter s first z #(l(fn[y]y)%)r(sort(z(for[e(q/permutations[+ - * quot mod])](try(loop[t e m y a x](if(=[]t)(s a)(let[j(s t)i(reverse(keep-indexed #(if(= j %2)%)m))](recur(rest t)(l #(not= j %)m)(loop[d 0 h a](if(=(count i)d)h(let[c(nth i d)f(inc c)](recur(inc d)(vec(z(assoc h c(j(nth h c)(nth h f))f nil)))))))))))(catch Exception _ nil)))))](-(last r)(s r))))

Cobalah online!

Untuk fungsi ini untuk bekerja, Anda harus usedengan clojure.math.combinatoricsperpustakaan (41 bytes):

(use '[clojure.math.combinatorics :as q])

Nuansa:

Fungsi ini adalah fungsi anonim, yang berarti Anda harus melakukan ini untuk menggunakannya:

((fn[x y]...) numbers operators)

Juga, saya menggunakan kata quotbukan /(karena Clojure melakukan pembagian fraksi secara default), dan modbukannya% .

Program tidak digabungkan:

(defn precedence [numbers operators]
  (let [results
        (sort
          (for [permute (c/permutations [+ - * / mod])]
            (loop [p-temp permute
                  o-temp operators
                  n-temp numbers]
              (if (empty? o-temp) (first n-temp)
                (let [first-p (first p-temp)
                      indices (reverse (keep-indexed #(when (= first-p %2) %) o-temp))]
                  (recur
                    (rest p-temp)
                    (filter #(not= first-p %) o-temp)
                    (loop [ind 0
                          n-through n-temp]
                      (if (= ind (count indices)) n-through
                        (let [current-ind (nth indices ind)]
                          (recur
                            (inc ind)
                            (vec
                              (filter #(not (nil? %))
                                (assoc n-through
                                  current-ind (first-p (nth n-through current-ind) (nth n-through (inc current-ind)))
                                  (inc current-ind) nil)))))))))))))]
    (- (last results) (first results))))
clismique
sumber
Saya pikir Anda bisa mengatakan "Penutupan + Combinatorics" dan tidak harus mencetak usepernyataan.
Buah Esolanging
@ Challenger5 Saya yakin Anda sebaiknya menuliskannya dalam deskripsi, karena secara default, The characters used to import the library will likely be counted codegolf.meta.stackexchange.com/questions/10225/…
Keyu Gan
@ Kaneyan Anda benar - saya salah mengerti konsensus Meta. Saya pikir requireperlu dimasukkan dalam kode dan panjangnya harus ditambahkan ke jumlah byte.
Buah Esolanging
@ Challenger5 Jadi saya perlu menambahkan 41 byte ke dalam bytecount saya, bukan? BAIK.
clismique
@ Qwerp-Derp Ya, tetapi impor merupakan bagian dari kode Anda, dan Anda dapat menggunakannya.
Buah Esolanging
0

JavaScript (ES6), 210 byte

Input sebagai array angka dan operator

k=>(m=n=-k,r=(o,k,j=0)=>{for(o||(m=m>k?m:k,n=n<k?n:k);q=o[j++];(q>'%'&q<'/'||z)&&r(o.slice(0,j-1)+o.slice(j),h))for(h=[...k],z=1;i=h.indexOf(q)+1;h.splice(i-2,3,eval(a=h[i-2]+q+h[i])|0))z*=h[i]})('+-*/%',k)|m-n

Kurang golf

k=>(
  m = n = NaN,
  r =(o, k, j=0) => {
    // try all operators in o
    for(;q = o[j]; j++)
    {  
      // q : current operator, 
      // look for q inside the expression to evaluate
      for(h = [...k], z = 1; i = h.indexOf(q) + 1;)
      {
        a = h[i - 2]
        b = h[i]
        z *= b // trace if any second operand is zero
        // subst subexpression with its value
        h.splice(i - 2, 3, eval(a + q + b) | 0)
      }
      // now all subexp involving current operator are evaluated
      // the result is ok if current operator is not % or /
      //  OR if no second operand was zero
      (q > '%' & q < '/' || z) && 
        // try again recursively
        // using the remaining operators and the remaining expression
        r(o.slice(0, j) + o.slice(j+1), h) 
    }
    // if no more operators to try, check max and min
    // k is an array with 1 element, can be used like a single number
    o || (
      m = m > k ? m : k, 
      n = n < k ? n : k
    )
  },
  r('+-*/%', k),
  m-n
)

Uji

var F=
k=>(m=n=-k,r=(o,k,j=0)=>{for(o||(m=m>k?m:k,n=n<k?n:k);q=o[j++];(q>'%'&q<'/'||z)&&r(o.slice(0,j-1)+o.slice(j),h))for(h=[...k],z=1;i=h.indexOf(q)+1;h.splice(i-2,3,eval(a=h[i-2]+q+h[i])|0))z*=h[i]})('+-*/%',k)|m-n

function update() {
  var input = I.value.match(/\d+|\S/g)
  var result = F(input)
  O.textContent = I.value + ' -> ' + result + ' (max:'+m+' min:'+n+')'
}

update()
<input id=I value="60 / 8 % 8 * 6 % 4 * 5" oninput='update()'>
<pre id=O></pre>

edc65
sumber