Sie erhalten eine Zeichenfolge, die aus den Zeichen besteht 0123456789+*(). Sie können davon ausgehen, dass die Zeichenfolge immer ein gültiger mathematischer Ausdruck ist.

Ihre Aufgabe ist es, die unnötigen Klammern zu entfernen, vorausgesetzt, die Multiplikation hat eine höhere Priorität als die Addition.

Die Klammern sollten nur entfernt werden, wenn sie strukturell nicht benötigt werden :

• wegen multiplikation höhere priorität: 3+(4*5)=>3+4*5
• wegen Multiplikation oder Addition Assoziativität: 3*(4*5)=>3*4*5
• Wenn sie um einen Ausdruck herum redundant sind: 3*((4+5))=>3*(4+5)

Klammern sollten beibehalten werden, wenn sie aufgrund bestimmter Zahlenwerte vereinfacht werden könnten:

• 1*(2+3) sollte nicht vereinfacht werden 1*2+3
• 0*(1+0) sollte nicht vereinfacht werden 0*1+0

Beispiele:

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

^{-6 Bytes dank Roman !}

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

Ersetzt +und *mit ~~( StringExpression) bzw. **( NonCommutativeMultiply), wertet es aus, fasst es zusammen und ersetzt die Operatoren zurück.

JavaScript (ES6) 163 178

Bearbeite 15 Bytes gespeichert dank @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`)

Weniger golfen

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
}

Prüfung

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>

Python3 + PEG-Implementierung in 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())))

Vor einiger Zeit habe ich eine PEG-Implementierung in Python durchgeführt . Das kann ich hier wohl nutzen.

Analysiert den Ausdruck in eine Baumstruktur und behält Klammern nur bei, wenn das untergeordnete Element eine Addition und das übergeordnete Element eine Multiplikation ist.

Perl, 132 Bytes

129 Bytes Quelle + 3 für -pFlag:

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

Verwenden von:

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

Ruby, 140-130 Bytes

127 Byte Quelle + 3 für -pFlag:

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

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

Netzhaut, 155 Bytes

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

Probieren Sie es online!

Überprüfen Sie alle Testfälle auf einmal.

Erläuterung

Die Hauptsache ist dieser Code:

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

Dieser reguläre Ausdruck kann mit jeder Zeichenfolge übereinstimmen, bei der die Klammern ausgeglichen sind, z . B. 1+(2+(3))+4oder 2+3.

Zur Erleichterung der Erklärung sei dieser reguläre Ausdruck B.

Verwenden wir stattdessen <und >für die Klammern sowie pund mfür \+und \*.

Der Code wird:

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

Die ersten beiden Zeilen stimmen mit Klammern überein, die nur aus Multiplikation bestehen, z . B. (1*2*3)oder sogar (1*(2+3)*4). Sie werden durch ihren Inhalt im Inneren ersetzt.

Die letzten beiden Zeilen stimmen für Klammern überein, die nicht vorangestellt sind und denen keine Multiplikation folgt. Sie werden durch ihren Inhalt im Inneren ersetzt.

Die Initiale {`bedeutet "Ersetzen bis idempotent", was bedeutet, dass die Ersetzungen durchgeführt werden, bis sie entweder nicht mehr übereinstimmen oder durch sich selbst ersetzt werden.

In diesem Fall werden die Ersetzungen so lange durchgeführt, bis sie nicht mehr übereinstimmen.

Python 3, 274 269 359 337 336 Bytes

Diese Methode entfernt grundsätzlich jedes mögliche Klammerpaar und prüft, ob es immer noch gleich ist.

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)

Testgeschirr

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

Aktualisierung

• -1 [16-10-04] Zusätzliches Leerzeichen entfernt
• -22 [16-05-07] Benutzt die relib
• +90 [16-05-07] Aktualisiert, um die neuen Testfälle zu behandeln
• -5 [16-05-07] Parameter aus der Länge ( l) Lambda entfernt

PHP, 358 Bytes

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

Keine beeindruckende Länge, das ist es, was ich dafür bekomme, dass ich einen weniger als optimalen Ansatz (und eine weniger als optimale Sprache) gewählt habe.

Entfernt ein Paar Klammern und wertet den resultierenden Ausdruck aus. Wenn das Ergebnis mit dem Original übereinstimmt, wird es zu einer Karte gültiger Ausdrücke hinzugefügt und solange wiederholt, bis keine neuen Ausdrücke mehr gefunden werden. Dann wird der kürzeste gültige Ausdruck gedruckt.

Bricht ab, wenn das Ergebnis des Ausdrucks groß wird und die Doppel- / Exponenten-Notation angezeigt wird.

Prolog (SWI) , 122 118 Bytes

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.

Probieren Sie es online!

Definiert ein Prädikat //2, das Klammern aus dem Zeichenfolgenwert des ersten Arguments entfernt und eine Zeichenfolge über das zweite Argument ausgibt. Wenn der Eingang in Prolog Bedingungen sein könnte, wäre dies nur sein 81 77 Bytes definieren , +/2ohne mit dem ausführlichen beschäftigen zu müssen term_string/2, aber eine Menge unnötiger Klammer einfach nicht bestanden hat mit dieser Art und Weise zu beginnen , so dass es ziemlich nah an betrügen würde, da Alles, was das +/2tut, ist die Assoziativität.

Ich habe versucht, es =../2für alles zu verwenden , aber es kam viel länger heraus, weil ein Drei-Byte-Operator, der mit Listen arbeitet, nicht gerade knapp ist:

Prolog (SWI) , 124 Bytes

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.

Probieren Sie es online!