Você recebe uma sequência composta pelos caracteres 0123456789+*(). Você pode assumir que a string é sempre uma expressão matemática válida.

Sua tarefa é remover os parênteses desnecessários, assumindo que a multiplicação tenha maior prioridade que a adição.

Os parênteses devem ser removidos somente quando não forem necessários estruturalmente :

• por causa da multiplicação maior prioridade: 3+(4*5)=>3+4*5
• por causa da multiplicação ou adição de adição: 3*(4*5)=>3*4*5
• quando são redundantes em torno de uma expressão: 3*((4+5))=>3*(4+5)

Os parênteses devem ser mantidos quando puderem ser simplificados devido a valores numéricos específicos:

• 1*(2+3) não deve ser simplificado para 1*2+3
• 0*(1+0) não deve ser simplificado para 0*1+0

Exemplos:

(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 graças a Roman !}

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

Substitui +e *por ~~( StringExpression) e **( NonCommutativeMultiply), respectivamente, avalia, especifica e substitui os operadores novamente.

JavaScript (ES6) 163 178

Editar 15 bytes salvos 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`)

Menos golfe

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
}

Teste

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>

Implementação Python3 + PEG em Python , 271 bytes

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

Há um tempo atrás eu fiz uma implementação PEG em Python . Eu acho que posso usar isso aqui.

Analisa a expressão em uma árvore e só mantém parênteses se o filho for adição e o pai for multiplicação.

Perl, 132 bytes

Origem de 129 bytes + 3 para o -psinalizador:

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

Usando:

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

Ruby, 140 130 bytes

Origem de 127 bytes + 3 para o -psinalizador:

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

E não destruído:

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 bytes

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

Experimente online!

Verifique todos os casos de teste de uma só vez.

Explicação

O principal é este código:

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

Essa regex pode corresponder a qualquer sequência na qual os colchetes estejam balanceados, por exemplo, 1+(2+(3))+4ou 2+3.

Para facilitar a explicação, deixe esse regex B.

Além disso, vamos usar <e >para os colchetes, bem como pe mpara \+e \*.

O código se torna:

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

As duas primeiras linhas correspondem a colchetes que consistem apenas em multiplicação, por exemplo, (1*2*3)ou mesmo (1*(2+3)*4). Eles são substituídos pelo conteúdo interno.

As duas últimas linhas correspondem a colchetes que não são precedidos e que não são seguidos por multiplicação. Eles são substituídos pelo conteúdo interno.

O inicial {`significa "substituir até idempotente", significando que as substituições são feitas até que não correspondam mais ou sejam substituídas por elas mesmas.

Nesse caso, as substituições são feitas até que não correspondam mais.

Python 3, 274 269 359 337 336 bytes

Esse método basicamente remove todos os parênteses possíveis e verifica se ele ainda avalia o mesmo.

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)

Equipamento de teste

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

Atualizações

• -1 [16-10-04] Removido espaço extra
• -22 [16-05-07] Utilizou a relib
• +90 [16-05-07] Atualizado para lidar com os novos casos de teste
• -5 [16-05-07] Removido o parâmetro do comprimento ( l) lambda

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

Não é uma duração impressionante, é o que recebo por adotar uma abordagem menos que ótima (e usar uma linguagem que não seja ótima).

Retira um par de colchetes e avalia a expressão resultante. Se o resultado for o mesmo que o original, ele será adicionado a um mapa de expressões válidas e se repetirá até que nenhuma nova expressão seja encontrada. Em seguida, imprime a expressão válida mais curta.

Quebra quando o resultado da expressão aumenta e lança a notação de duplo / expoente.

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.

Experimente online!

Define um predicado //2que remove parênteses do valor da string do primeiro argumento e gera uma string através do segundo argumento. Se a entrada pudesse ser em termos de prólogo, isso teria apenas 81 77 bytes de definição +/2sem ter que lidar com os verbos detalhados term_string/2, mas muitos parênteses desnecessários simplesmente não existiriam para começar dessa maneira, portanto seria bem próximo de trapacear, pois tudo o que +/2faz é lidar com associatividade.

Tentei usar =../2para tudo isso, mas ficou muito mais tempo, porque um operador de três bytes que trabalha com listas não é exatamente conciso:

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.

Experimente online!