Parenthesize sebuah ekspresi

20

Baru-baru ini saya telah menulis bahasa baru , untuk menghindari keharusan menangani urutan operasi , saya cukup menyisipkan setiap ekspresi dengan benar untuk menghindari ini sepenuhnya.

Karena tanda kurung ada di kode char 40-41, kode Anda harus sesingkat mungkin.


Contohnya

1+2*3
(1+(2*3))

2*(3+4)
(2*(3+4))

2*3/4+3
(((2*3)/4)+3)

342*32/8
((342*32)/8)

Aturan

Satu-satunya operasi yang perlu Anda tangani adalah: *(penggandaan), /(pembagian), +(penjumlahan), dan -(pengurangan).

  • The urutan operasi adalah:
    • Kurung
    • Perkalian, Divisi
    • Adition, Subtraction
  • Anda sebaiknya memilih ke kiri-kanan
  • Nomor input akan selalu berupa bilangan bulat positif (lihat bonus)

Bonus

-20% jika Anda menangani negasi:

3+-5
(3+(-5))

-5% jika Anda membiarkan spasi ditempatkan di dalam input:

3  + 4
(3+4)

-10% jika Anda dapat menangani desimal dalam input:

1+.12
(1+.12)
1+0.21/3
(1+(0.21/3))

500 bounty: jika Anda berhasil menulis jawaban dalam Unnamed / Blocks

Downgoat
sumber
25
"Karena tanda kurung ada di kode char 40-41, kode kamu harus sesingkat mungkin." OKE, sekarang kamu benar-benar konyol. ; P
ETHproduksi
3
Dan ini lebih mudah daripada notasi awalan (Polandia) karena?
wizzwizz4
3
Kemungkinan duplikat .
flawr
8
@ flawr Saya melihat itu tetapi sangat berbeda dalam kenyataan bahwa pertanyaan itu membuat Anda mengeluarkan semua cara untuk mengekstraksi ekspresi. Di sini Anda harus mempertimbangkan urutan operasi yang menurut saya merupakan perbedaan yang signifikan karena kode tidak dapat diubah secara sepele untuk tantangan ini
Downgoat
3
Kasing uji penting: 1+2+3+4(solusi mana yang mungkin sebagai kurung ((1+2)+(3+4)))
Martin Ender

Jawaban:

2

Python, 153 * 0,9 = 137,7 byte

def p(e):
 for o in"+-*/":
    for i,c in enumerate(e):
        if(c==o)*(0==sum([(d=="(")-(d==")")for d in e[:i]])):return"("+p(e[:i])+o+p(e[i+1:])+")"
 return e

Program ini menangani input desimal.

Baris kedua dimulai dengan spasi, yang kedua dimulai dengan tab, yang ketiga dengan dua tab dan yang ketiga dengan spasi. Ini menyimpan satu byte. Ini hexdump ( xxdpp):

0000000: 6465 6620 7028 6529 3a0a 2066 6f72 206f  def p(e):. for o
0000010: 2069 6e22 2b2d 2a2f 223a 0a09 666f 7220   in"+-*/":..for 
0000020: 692c 6320 696e 2065 6e75 6d65 7261 7465  i,c in enumerate
0000030: 2865 293a 0a09 0969 6628 633d 3d6f 292a  (e):...if(c==o)*
0000040: 2830 3d3d 7375 6d28 5b28 643d 3d22 2822  (0==sum([(d=="("
0000050: 292d 2864 3d3d 2229 2229 666f 7220 6420  )-(d==")")for d 
0000060: 696e 2065 5b3a 695d 5d29 293a 7265 7475  in e[:i]])):retu
0000070: 726e 2228 222b 7028 655b 3a69 5d29 2b6f  rn"("+p(e[:i])+o
0000080: 2b70 2865 5b69 2b31 3a5d 292b 2229 220a  +p(e[i+1:])+")".
0000090: 2072 6574 7572 6e20 650a                  return e.

Berikut adalah program yang saya gunakan untuk pengujian: (Simpan program di atas sebagai paren.py)

import paren

cases = {
        "2+3*4": "(2+(3*4))", 
        "(2+3)*4": "((2+3)*4)", 
        "1+2+3+4": "(1+(2+(3+4)))", 
        "3/2+5": "((3/2)+5)", 
        "1+2-3": "(1+(2-3))", 
        "2-1+2": "((2-1)+2)",
        "3+-5": "(3+(-5))",
        "1+.12": "(1+.12)",
        "1+0.21/3": "(1+(0.21/3))",
}


for num, case in enumerate(cases):
    print "\n\n\033[1m\033[38;5;14mCase #%d: %s" % (num + 1, case)
    result = paren.p(case)
    print "\033[38;5;4mParenthesize returned: %s" % (result)
    solution = cases[case]
    if result == solution:
        print "\033[38;5;76mCorrect!"
    else:
        print "\033[38;5;9mNot correct!"

Pastikan terminal Anda menggunakan \033[38;5;<COL>mkode pelarian untuk warna.

Loovjo
sumber
* keempat dengan spasi?
Element118
1
Program ini tidak prefer to go left-right. Coba test case 3 di OP, hasil Anda tidak benar. Ini bisa menjadi masalah nyata misalnya dengan aritmatika integer ((2*(3/4))+3)(((2*3)/4)+3)
:!
1
@ user12365 Tidak menggunakan bilangan bulat aritmatika (dalam C atau C ++ misalnya) 3/4 == 0, jadi ((2 * (3/4)) + 3) adalah 3, sedangkan (((2 * 3) / 4) + 3) adalah 4
edc65
3

JavaScript (ES6) 179 (263 -20% -5% -10%)

(x,W=[],Q=['('],z=1,w=v='',h=p=>'*/+-))('.indexOf(p)|1,C=n=>{for(;h(q=Q.pop())<=h(n);)W[0]=`(${W[1]+q+W.shift()})`;z&&Q.push(q,n)})=>(x+')').replace(/[\d.]+|\S/g,t=>t>'('?t>')'?~h(t)?z?(w+='('+t,v+=')'):C(t,z=1):W=[w+t+v,...W,z=w=v='']:C(t,z=0):z=Q.push(t))&&W[0]

Karena dua jawaban lainnya saat ini keduanya salah, saya akan memposting milik saya. Ini adalah variasi dari pengurai ekspresi yang saya gunakan di sini dan di sini dan di tempat lain. Lihat di sana untuk penjelasan algoritma yang lebih rinci.

Cukup besar tetapi harus bekerja.

Cuplikan tes

f=(x,W=[],Q=['('],z=1,w=v='',h=p=>'*/+-))('.indexOf(p)|1,C=n=>{for(;h(q=Q.pop())<=h(n);)W[0]=`(${W[1]+q+W.shift()})`;z&&Q.push(q,n)})=>(x+')').replace(/[\d.]+|\S/g,t=>t>'('?t>')'?~h(t)?z?(w+='('+t,v+=')'):C(t,z=1):W=[w+t+v,...W,z=w=v='']:C(t,z=0):z=Q.push(t))&&W[0]

// More readable
x=(x,W=[],Q=['('],z=1,w=v='',
  h=p=>'*/+-))('.indexOf(p)|1,
  C=n=>{
    for(;h(q=Q.pop())<=h(n);)W[0]=`(${W[1]+q+W.shift()})`;
    z&&Q.push(q,n)
  }
)=>(
  (x+')')
  .replace(/[\d.]+|\S/g,t=> 
       t>'('    
       ?t>')'
       ?~h(t)
       ?z
       ?(w+='('+t,v+=')')
       :C(t,z=1)
       :W=[w+t+v,...W,z=w=v=''] // overfill W to save 2 chars ()
       :C(t,z=0)
       :z=Q.push(t)
  ),
  W[0]
)

console.log=(...x)=>O.textContent+=x.join` `+'\n'

// TEST
;[
  ['1+2*3','(1+(2*3))'],['2*(3+4)','(2*(3+4))'],['2*3/4+3','(((2*3)/4)+3)'],['342*32/8','((342*32)/8)'],
  ['3+-5','(3+(-5))'],['-3+-4*7','((-3)+((-4)*7))'], // bonus 20%
  ['3  + 4','(3+4)'], // bonus 5%
  ['1+.12','(1+.12)'],['1+0.21/3','(1+(0.21/3))'] // bonus 10%
].forEach(t=>{var k=t[1],i=t[0],r=f(i); console.log(i+' : '+r+(r==k? ' OK':' Fail expecting '+k))})
<pre id=O></pre>

edc65
sumber
1

Python, 241 * 0.8 * 0.95 * 0.9 = 164.84 karakter

Saya menggunakan perpustakaan ast (Abstract Syntax Trees) , dan dict pengganti string homebrew. Penggantian string banyak biaya, tetapi bonus membantu menjaga skor agak rendah. Mungkin (bagian pengganti dawai) bisa di mainkan lebih jauh.

Perhatikan bahwa solusi ini menambahkan seperangkat tanda kurung tambahan di sekitar setiap angka, tapi saya pikir itu sesuai dengan semangat pertanyaan

import ast;def p(e):
 r,s={"Module([":"",")])":"","Expr(":"","BinOp":"","Num":"",", Add(), ":"+",", Sub(), ":"-",", Div(), ":"/",", Mult(), ":"*"},ast.dump(ast.parse(e),annotate_fields=False)
 for f,t in r.iteritems():s=s.replace(f,t)
 return s

Test suite:

cases = {
    "2+3*4", 
    "(2+3)*4", 
    "1+2+3+4", 
    "3/2+5", 
    "1+2-3", 
    "2-1+2",
    "3+-5",
    "1+.12",
    "1+0.21/3"
}

for num,case in enumerate(cases):
    result = p(case)
    print "Case {}: {:<16} evaluates to: {}".format(num+1,case,result)

Output dari suite tes:

Case 1: 3+-5             evaluates to: ((3)+(-5))
Case 2: 3/2+5            evaluates to: (((3)/(2))+(5))
Case 3: 2+3*4            evaluates to: ((2)+((3)*(4)))
Case 4: 1+2+3+4          evaluates to: ((((1)+(2))+(3))+(4))
Case 5: 1+0.21/3         evaluates to: ((1)+((0.21)/(3)))
Case 6: (2+3)*4          evaluates to: (((2)+(3))*(4))
Case 7: 2-1+2            evaluates to: (((2)-(1))+(2))
Case 8: 1+.12            evaluates to: ((1)+(0.12))
Case 9: 1+2-3            evaluates to: (((1)+(2))-(3))
agtoever
sumber
Tidak ada import astdalam kode Anda
edc65
Dan itu bukan cara yang tepat untuk menghitung bonus persen. Jika Anda mendapatkan diskon 50% dan di atas yang lain 50%, Anda tidak membayar 0. Skor Anda harus 157,32 (sesuatu yang lebih setelah menambahkan garis impor). Itu adalah skor yang bagus - saya akan angkat suara jika Anda memperbaikinya
edc65
Poin bagus. Menambahkan impor. 241 karakter sekarang. Tidak yakin bagaimana cara menghitung bonus. Jika saya memahami komentar Anda dengan benar, urutan di mana bonus dikurangkan penting ...
agtoever
Bonus tidak dikurangi (ini adalah perkalian) dan urutannya tidak masalah. 241 * (1-20%) * (1-5%) * (1-10%) => 241 * 0.8 * 0.95 * 0.9 => 164.84
edc65
@ edc65 Ah. Kanan. Tidak berpikir jernih. Terima kasih.
agtoever