Anda diberi string yang disusun dengan karakter 0123456789+*(). Anda dapat mengasumsikan bahwa string selalu merupakan ekspresi matematika yang valid.

Tugas Anda adalah menghapus tanda kurung yang tidak perlu, dengan anggapan multiplikasi memiliki prioritas lebih tinggi daripada penambahan.

Tanda kurung harus dihapus hanya ketika mereka tidak diperlukan secara struktural :

• karena penggandaan prioritas lebih tinggi: 3+(4*5)=>3+4*5
• karena multiplikasi atau penambahan asosiatif: 3*(4*5)=>3*4*5
• ketika mereka redundan di sekitar ekspresi: 3*((4+5))=>3*(4+5)

Kurung harus disimpan ketika dapat disederhanakan karena nilai angka tertentu:

• 1*(2+3) seharusnya tidak disederhanakan 1*2+3
• 0*(1+0) seharusnya tidak disederhanakan 0*1+0

Contoh:

(4*12)+11         ==>    4*12+11
(1+2)*3           ==>    (1+2)*3
3*(4*5)           ==>    3*4*5
((((523))))       ==>    523
(1+1)             ==>    1+1
1*(2*(3+4)*5)*6   ==>    1*2*(3+4)*5*6
1*(2+3)           ==>    1*(2+3)
0*(1+0)           ==>    0*(1+0)


(((2+92+82)*46*70*(24*62)+(94+25))+6)    ==>    (2+92+82)*46*70*24*62+94+25+6

Mathematica, 105 97 91 byte

^{-6 byte terima kasih kepada Roman !}

a=StringReplace;ToString@ToExpression@a[#,{"*"->"**","+"->"~~"}]~a~{" ** "->"*","~~"->"+"}&

Mengganti +dan *dengan ~~( StringExpression) dan **( NonCommutativeMultiply) masing-masing, mengevaluasinya, mengencangkannya, dan mengganti kembali operator.

JavaScript (ES6) 163 178

Edit 15 byte yang disimpan thx @IsmaelMiguel

a=>eval(`s=[]${_=';for(b=0;a!=b;a=b.replace(/'}\\(([^()]*)\\)(?=(.?))/,(x,y,z,p)=>~y.indexOf('+')?-s.push(b[p-1]=='*'|z=='*'?x:y):y))b=a;${_}-\\d+/,x=>s[~x]))b=a`)

Kurang golf

a=>{
  for(s=[],b='';
      a!=b;
      a=b.replace(/\(([^()]*)\)(?=(.?))/,(x,y,z,p)=>y.indexOf('+')<0?y:-s.push(b[p-1]=='*'|z=='*'?x:y)))
    b=a;
  for(b=0;
      a!=b;
      a=b.replace(/-\d+/,x=>s[~x]))
    b=a;
  return a
}

Uji

f=a=>eval(`s=[]${_=';for(b=0;a!=b;a=b.replace(/'}\\(([^()]*)\\)(?=(.?))/,(x,y,z,p)=>~y.indexOf('+')
?-s.push(b[p-1]=='*'|z=='*'?x:y)
:y))b=a;${_}-\\d+/,x=>s[~x]))b=a`)

console.log=x=>O.textContent+=x+'\n'

test=`(4*12)+11         ==>    4*12+11
(1+2)*3           ==>    (1+2)*3
3*(4*5)           ==>    3*4*5
((((523))))       ==>    523
(1+1)             ==>    1+1
1*(2*(3+4)*5)*6   ==>    1*2*(3+4)*5*6
1*(2+3)           ==>    1*(2+3)
0*(1+0)           ==>    0*(1+0)
(((2+92+82)*46*70*(24*62)+(94+25))+6)    ==>    (2+92+82)*46*70*24*62+94+25+6`

test.split`\n`.forEach(r=>{
  var t,k,x
  [t,,k]=r.match(/\S+/g)
  x=f(t)
  console.log((x==k?'OK ':'KO ')+t+' -> '+x+(x==k?'':' expected '+k))
})

<pre id=O></pre>

Implementasi Python3 + PEG dalam Python , 271 byte

import peg
e=lambda o,m=0:o.choice and str(o)or(m and o[1][1]and"("+e(o[1])+")"or e(o[1]))if hasattr(o,"choice")else o[1]and e(o[0],1)+"".join(str(x[0])+e(x[1],1)for x in o[1])or e(o[0])
print(e(peg.compile_grammar('e=f("+"f)*f=p("*"p)*p="("e")"/[0-9]+').parse(input())))

Beberapa waktu yang lalu saya membuat implementasi PEG dengan Python . Saya kira saya bisa menggunakannya di sini.

Mengurai ekspresi menjadi pohon, dan hanya menyimpan tanda kurung jika anak adalah tambahan, dan orang tua adalah perkalian.

Perl, 132 byte

129 sumber byte + 3 untuk -pbendera:

#!perl -p
0while s!\(([^\(\)]+)\)!$f{++$i}=$1,"_$i"!e;s!_$i!($v=$f{$i})=~/[+]/&&($l.$r)=~/[*]/?"($v)":$v!e
while($l,$i,$r)=/(.?)_(\d+)(.?)/

Menggunakan:

echo "1*(2*(3+4)*5)*6" | perl script.pl

Rubi, 140 130 byte

Sumber 127 byte + 3 untuk -p bendera:

t={}
r=?%
0while$_.gsub!(/\(([^()]+)\)/){t[r+=r]=$1;r}
0while$_.gsub!(/%+/){|m|(s=t[m])[?+]&&($'[0]==?*||$`[/\*$/])??(+s+?):s}

Dan ungolfed:

tokens = Hash.new
key = '%'

# convert tokens to token keys in the original string, innermost first
0 while $_.gsub!(/\(([^()]+)\)/) { # find the innermost parenthetical
  key += key # make a unique key for this token
  tokens[key] = $1
  key # replace the parenthetical with the token key in the original string
}

# uncomment to see what's going on here
# require 'pp'
# pp $_
# pp tokens

# convert token keys back to tokens, outermost first
0 while $_.gsub!(/%+/) {|key|
  str = tokens[key]
  if str['+'] and ($'[0]=='*' or $`[/\*$/]) # test if token needs parens
    '(' + str + ')'
  else
    str
  end
}
# -p flag implicity prints $_

Retina, 155 byte

{`\(((\d+|\((((\()|(?<-5>\))|[^()])*(?(5)^))\))(\*(\d+|\((((\()|(?<-10>\))|[^()])*(?(10)^))\)))*)\)
$1
(?<!\*)\((((\()|(?<-3>\))|[^()])*(?(3)^))\)(?!\*)
$1

Cobalah online!

Verifikasi semua testcans sekaligus.

Penjelasan

Yang utama adalah kode ini:

(((\()|(?<-3>\))|[^()])*(?(3)^)

Regex ini dapat cocok dengan string apa pun di mana tanda kurung seimbang, misalnya 1+(2+(3))+4atau2+3 .

Untuk memudahkan penjelasan, biarkan regex ini B.

Juga, mari kita gunakan <dan >bukan untuk kurung, serta pdan muntuk \+dan \*.

Kode tersebut menjadi:

{`<((\d+|<B>)(m(\d+|<B>))*)>
$1
(?<!m)<B>(?!m)
$1

Dua baris pertama cocok untuk tanda kurung yang hanya terdiri dari perkalian, misalnya (1*2*3)atau genap (1*(2+3)*4). Mereka digantikan oleh konten mereka di dalam.

Dua baris terakhir cocok untuk tanda kurung yang tidak didahului dan yang tidak diikuti oleh perkalian. Mereka digantikan oleh konten mereka di dalam.

Awal {`berarti "ganti sampai idempoten", yang berarti bahwa penggantian dilakukan sampai mereka tidak lagi cocok atau mereka diganti dengan diri mereka sendiri.

Dalam hal ini, penggantian dilakukan hingga tidak cocok lagi.

Python 3, 274 269 359 337 336 byte

Metode ini pada dasarnya menghapus setiap pasangan kurung dan memeriksa untuk melihat apakah masih mengevaluasi sama.

from re import *
def f(x):
    *n,=sub('\D','',x);x=sub('\d','9',x);v,i,r,l=eval(x),0,lambda d,a,s:d.replace(s,"?",a).replace(s,"",1).replace("?",s),lambda:len(findall('\(',x))
    while i<l():
        j=0
        while j<l():
            h=r(r(x,i,"("),j,")")
            try:
                if eval(h)==v:i=j=-1;x=h;break
            except:0
            j+=1
        i+=1
    return sub('9','%s',x)%tuple(n)

Uji Harness

print(f("(4*12)+11")=="4*12+11")
print(f("(1+2)*3") =="(1+2)*3")
print(f("3*(4*5)")=="3*4*5")
print(f("((((523))))")=="523")
print(f("(1+1)")=="1+1")
print(f("1*(2*(3+4)*5)*6")=="1*2*(3+4)*5*6")
print(f("(((2+92+82)*46*70*(24*62)+(94+25))+6)")=="(2+92+82)*46*70*24*62+94+25+6")
print(f("1*(2+3)")=="1*(2+3)")
print(f("0*(1+0)")=="0*(1+0)")

Pembaruan

• -1 [16-10-04] Ruang ekstra dihapus
• -22 [16-05-07] Memanfaatkan relib
• +90 [16-05-07] Diperbarui untuk menangani kasus uji baru
• -5 [16-05-07] Parameter yang dihapus dari panjang ( l) lambda

PHP, 358 byte

function a($a){static$c=[];$d=count($c);while($g=strpos($a,')',$g)){$f=$a;$e=0;for($j=$g;$j;--$j){switch($a[$j]){case')':++$e;break;case'(':--$e;if(!$e)break 2;}}$f[$g++]=$f[$j]=' ';if(eval("return $f;")==eval("return $a;"))$c[str_replace(' ', '', $f)]=1;}if(count($c)>$d){foreach($c as$k=>$v){a($k);}}return$c;}$t=a($argv[1]);krsort($t);echo key($t);

Bukan panjang yang mengesankan, itulah yang saya dapatkan untuk mengambil pendekatan yang kurang optimal (dan menggunakan bahasa yang kurang optimal).

Lepaskan sepasang tanda kurung, lalu hasilkan ekspresi yang dihasilkan. Jika hasilnya sama dengan aslinya, ia menambahkannya ke peta ekspresi dan pengulangan yang valid sampai tidak ada ekspresi baru yang ditemukan. Kemudian cetak ekspresi valid terpendek.

Terobosan ketika hasil dari ekspresi menjadi besar dan dilemparkan ke notasi eksponen ganda muncul.

Prolog (SWI) , 122 118 byte

T+S:-term_string(T,S).
I/O:-X+I,X-Y,Y+O.
E-O:-E=A+(B+C),A+B+C-O;E=A*(B*C),A*B*C-O;E=..[P,A,B],A-X,B-Y,O=..[P,X,Y];E=O.

Cobalah online!

Mendefinisikan predikat //2yang menghilangkan tanda kurung dari nilai string argumen pertama dan menghasilkan string melalui argumen kedua. Jika input bisa dalam istilah Prolog, ini hanya akan menjadi 81 77 byte yang ditentukan +/2tanpa harus berurusan dengan verbose term_string/2, tetapi banyak tanda kurung yang tidak perlu sama sekali tidak ada untuk memulai dengan cara itu sehingga akan cukup dekat dengan kecurangan, karena semua yang +/2dilakukan adalah menangani asosiatif.

Saya mencoba menggunakan =../2untuk semua itu, tetapi keluar jauh lebih lama, karena operator tiga byte yang bekerja dengan daftar tidak persis singkat:

Prolog (SWI) , 124 byte

T+S:-term_string(T,S).
I/O:-X+I,X-Y,Y+O.
X-Y:-X=..[O,A,B],(B=..[O,C,D],E=..[O,A,C],F=..[O,E,D],F-Y;A-C,B-D,Y=..[O,C,D]);X=Y.

Cobalah online!