Otrzymujesz ciąg złożony ze znaków 0123456789+*(). Możesz założyć, że ciąg jest zawsze prawidłowym wyrażeniem matematycznym.

Twoim zadaniem jest usunięcie niepotrzebnych nawiasów, zakładając, że mnożenie ma wyższy priorytet niż dodawanie.

Nawiasy należy usuwać tylko wtedy, gdy nie są potrzebne strukturalnie :

• z powodu zwielokrotnienia wyższy priorytet: 3+(4*5)=>3+4*5
• z powodu asocjacji mnożenia lub dodawania: 3*(4*5)=>3*4*5
• gdy są zbędne wokół wyrażenia: 3*((4+5))=>3*(4+5)

Nawiasy należy przechowywać, gdy można je uprościć ze względu na określone wartości liczbowe:

• 1*(2+3) nie należy tego upraszczać 1*2+3
• 0*(1+0) nie należy tego upraszczać 0*1+0

Przykłady:

(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 bajtów

^{-6 bajtów dzięki Romanowi !}

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

Zastępuje +oraz *z ~~( StringExpression) i **( NonCommutativeMultiply), odpowiednio, ocenia je, stringifies ją i zastępuje operatorów powrotem.

JavaScript (ES6) 163 178

Edytuj 15 bajtów zapisanych dzięki @ 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`)

Mniej golfa

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
}

Test

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>

Implementacja Python3 + PEG w Pythonie , 271 bajtów

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())))

Jakiś czas temu zrobiłem implementację PEG w Pythonie . Chyba mogę tego tutaj użyć.

Przetwarza wyrażenie na drzewo i zachowuje nawiasy tylko wtedy, gdy dziecko jest dodawaniem, a rodzic jest mnożeniem.

Perl, 132 bajty

Źródło 129 bajtów + 3 dla -pflagi:

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

Za pomocą:

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

Rubinowy, 140 130 bajtów

Źródło 127 bajtów + 3 dla -pflagi:

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

I bez golfa:

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 $_

Siatkówka, 155 bajtów

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

Wypróbuj online!

Zweryfikuj wszystkie przypadki testowe jednocześnie.

Wyjaśnienie

Najważniejsze jest ten kod:

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

Ten regex może pasować do dowolnego łańcucha, w którym nawiasy są zrównoważone, np . 1+(2+(3))+4Lub 2+3.

Dla ułatwienia wyjaśnienia niech to wyrażenie regularne będzie B.

Użyjmy <i >zamiast tego w nawiasach, a także pi mdla \+i \*.

Kod staje się:

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

Pierwsze dwie linie pasują do nawiasów, które składają się tylko z mnożenia, np. (1*2*3)Lub nawet (1*(2+3)*4). Są one zastępowane przez ich zawartość w środku.

Ostatnie dwa wiersze pasują do nawiasów, które nie są poprzedzone i po których nie następuje mnożenie. Są one zastępowane przez ich zawartość w środku.

Początkowy {`oznacza „zamień aż do idempotent”, co oznacza, że ​​zamiany są wykonywane, dopóki nie będą już pasować lub zostaną zastąpione przez siebie.

W takim przypadku zamiany są wykonywane, dopóki nie będą już pasować.

Python 3, 274 269 359 337 336 bajtów

Ta metoda zasadniczo usuwa każdą możliwą parę nawiasów i sprawdza, czy nadal ocenia to samo.

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)

Uprząż testowa

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)")

Aktualizacje

• -1 [16-10-04] Usunięto dodatkowe miejsce
• -22 [16-05-07] Wykorzystał relib
• +90 [16-05-07] Zaktualizowano, aby obsługiwał nowe przypadki testowe
• -5 [16-05-07] Usunięto parametr z llambda length ( )

PHP, 358 bajtów

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);

Nie imponująca długość, to właśnie otrzymuję za przyjęcie mniej niż optymalnego podejścia (i użycie mniej niż optymalnego języka).

Usuwa parę nawiasów, a następnie analizuje wynikowe wyrażenie. Jeśli wynik jest taki sam jak oryginał, dodaje go do mapy prawidłowych wyrażeń i powtarza się, dopóki nie można znaleźć nowych wyrażeń. Następnie drukuje najkrótsze prawidłowe wyrażenie.

Łamie się, gdy wynik wyrażenia staje się duży i wyświetla się rzut notacji podwójnej / wykładniczej.

Prolog (SWI) , 122 118 bajtów

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.

Wypróbuj online!

Definiuje predykat, //2który usuwa nawiasy z wartości ciągu pierwszego argumentu i wysyła ciąg znaków przez drugi argument. Gdyby dane wejściowe mogły być wyrażone w kategoriach Prolog, byłoby to tylko 81 77 bajtów definiujących +/2bez konieczności zajmowania się gadatliwością term_string/2, ale wiele niepotrzebnych nawiasów po prostu nie istniałoby od tego momentu, więc byłoby to bardzo bliskie oszustwa, ponieważ wszystko, co +/2robi, to radzenie sobie ze stowarzyszeniem.

Próbowałem użyć tego =../2wszystkiego, ale wyszło ono znacznie dłużej, ponieważ trzy bajtowy operator, który działa z listami, nie jest zbyt zwięzły:

Prolog (SWI) , 124 bajty

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.

Wypróbuj online!