[Question]
  [
You are given a string composed with the characters `0123456789+*()`. You can assume that string is always a valid mathematical expression.
Your task is to remove the unnecessary parentheses, assuming multiplication has higher priority than addition.
The parentheses should be removed only when they are not needed *structurally*:
* because of multiplication higher priority: `3+(4*5)` => `3+4*5`
* because of multiplication or addition associativity: `3*(4*5)` => `3*4*5`
* when they are redundant around an expression: `3*((4+5))` => `3*(4+5)`
Parentheses *should be kept* when they could be simplified because of specific number values:
* `1*(2+3)` should not be simplified to `1*2+3`
* `0*(1+0)` should not be simplified to `0*1+0`
Examples:
```
(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
```
  
[Answer]
# Mathematica, ~~105~~ ~~97~~ 91 bytes
*-6 bytes thanks to [Roman](https://codegolf.stackexchange.com/users/87058)!*
```
a=StringReplace;ToString@ToExpression@a[#,{"*"->"**","+"->"~~"}]~a~{" ** "->"*","~~"->"+"}&
```
Replaces `+` and `*` with `~~` (`StringExpression`) and `**` (`NonCommutativeMultiply`) respectively, evaluates it, stringifies it, and replaces the operators back.
[Answer]
# JavaScript (ES6) 163 ~~178~~
**Edit** 15 bytes saved 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`)
```
*Less golfed*
```
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>
```
[Answer]
# Python3 + [PEG implementation in Python](https://gist.github.com/orlp/363a4261f6a884311cbbe6a146a3052b), 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())))
```
A while back I made a [PEG implementation in Python](https://gist.github.com/orlp/363a4261f6a884311cbbe6a146a3052b). I guess I can use that here.
Parses the expression into a tree, and only keeps parenthesis if the child is addition, and the parent is multiplication.
[Answer]
# Perl, 132 bytes
129 bytes source + 3 for `-p` flag:
```
#!perl -p
0while s!\(([^\(\)]+)\)!$f{++$i}=$1,"_$i"!e;s!_$i!($v=$f{$i})=~/[+]/&&($l.$r)=~/[*]/?"($v)":$v!e
while($l,$i,$r)=/(.?)_(\d+)(.?)/
```
Using:
```
echo "1*(2*(3+4)*5)*6" | perl script.pl
```
[Answer]
# Ruby, ~~140~~ 130 bytes
127 bytes source + 3 for  `-p` flag:
```
t={}
r=?%
0while$_.gsub!(/\(([^()]+)\)/){t[r+=r]=$1;r}
0while$_.gsub!(/%+/){|m|(s=t[m])[?+]&&($'[0]==?*||$`[/\*$/])??(+s+?):s}
```
And 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 $_
```
[Answer]
# Retina, 155 bytes
```
{`\(((\d+|\((((\()|(?<-5>\))|[^()])*(?(5)^))\))(\*(\d+|\((((\()|(?<-10>\))|[^()])*(?(10)^))\)))*)\)
$1
(?<!\*)\((((\()|(?<-3>\))|[^()])*(?(3)^))\)(?!\*)
$1
```
[Try it online!](http://retina.tryitonline.net/#code=e2BcKCgoXGQrfFwoKCgoXCgpfCg_PC01PlwpKXxbXigpXSkrKD8oNSleKSlcKSkoXCooXGQrfFwoKCgoXCgpfCg_PC0xMD5cKSl8W14oKV0pKyg_KDEwKV4pKVwpKSkqKVwpCiQxCig_PCFcKilcKCgoKFwoKXwoPzwtMz5cKSl8W14oKV0pKyg_KDMpXikpXCkoPyFcKikKJDE&input=KDEqKDIrMykrNCkqNQ)
[Verify all testcases at once.](http://retina.tryitonline.net/#code=JXtgXCgoKFxkK3xcKCgoKFwoKXwoPzwtNT5cKSl8W14oKV0pKyg_KDUpXikpXCkpKFwqKFxkK3xcKCgoKFwoKXwoPzwtMTA-XCkpfFteKCldKSsoPygxMCleKSlcKSkpKilcKQokMQooPzwhXCopXCgoKChcKCl8KD88LTM-XCkpfFteKCldKSsoPygzKV4pKVwpKD8hXCopCiQx&input=KDQqMTIpKzExCigxKzIpKjMKMyooNCo1KQooKCgoNTIzKSkpKQooKDErMikpKzMKKDErMSkKKCgoMis5Mis4MikqNDYqNzAqKDI0KjYyKSsoOTQrMjUpKSs2KQoxKigyKigzKzQpKjUpKjYKKDEqKDIrMykrNCkqNQ&debug=on)
### Explanation
The main thing is this code:
```
(((\()|(?<-3>\))|[^()])*(?(3)^)
```
This regex can match any string in which the brackets are balanced, e.g. `1+(2+(3))+4` or `2+3`.
For the ease of explanation, let this regex be `B`.
Also, let us use `<` and `>` instead for the brackets, as well as `p` and `m` for `\+` and `\*`.
The code becomes:
```
{`<((\d+|<B>)(m(\d+|<B>))*)>
$1
(?<!m)<B>(?!m)
$1
```
The first two lines match for brackets which consist of only multiplication, e.g. `(1*2*3)` or even `(1*(2+3)*4)`. They are replaced by their content inside.
The last two lines match for brackets which are not preceded and which are not followed by multiplication. They are replaced by their content inside.
The initial `{`` means "replace until idempotent", meaning that the replacements are done until they either no longer match or they are replaced with themselves.
In this case, the replacements are done until they no longer match.
[Answer]
# Python 3, ~~274~~ ~~269~~ ~~359~~ ~~337~~ 336 bytes
This method basically removes every possible pair of parentheses and checks to see if it still evaluates the same.
```
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)
```
**Test 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)")
```
**Updates**
* **-1** [16-10-04] Removed extra space
* **-22** [16-05-07] Made use of the `re` lib
* **+90** [16-05-07] Updated to handle the new test cases
* **-5** [16-05-07] Removed parameter from the length (`l`) lambda
[Answer]
**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);
```
Not an impressive length, that's what I get for taking a less than optimal approach (and using a less than optimal language).
Strips a pair of brackets out, then evals the resulting expression. If the result is the same as the original it adds it to a map of valid expressions and recurses until no new expressions can be found. Then prints the shortest valid expression.
Breaks when the result of the expression gets large and casts to double / exponent notation show up.
[Answer]
# [Prolog (SWI)](http://www.swi-prolog.org), ~~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.
```
[Try it online!](https://tio.run/##bY9Pa4NAEMXP8VOIp92dXZNd/7SxtEWLh5wsTQ5KkBCKDYFEw2qwJ7@6HRMIFN3LLL/35vHmoqtTdRB1e@z7DawD0RT6vKsbfSwPZMPX1DZW8yQQKax4KjKeQWIbsUASv4ZAIvigPAQcInlBwkjEBsJw3Ihtbz95yKOchyLlESYkd5byLEc9sXt9LXff@7og8e9FUzMQxmz4zb@K@npquDH7qfR53xCra03xZnZtV3alxbeDid9NOdY03oX5iLKIy6SiIKWF0n9FgqLMGXGH4Y5Hx358nnIovqksOaaSEcWIAy7FPOZP6uCM9xYM8xaTDRQsFTxjb9dnT@hTLvPxPLJ0QXmUgk@n74RbDdT6Pw "Prolog (SWI) – Try It Online")
Defines a predicate `//2` which removes parentheses from its first argument's string value and outputs a string through its second argument. If input could be in Prolog terms, this would only be ~~81~~ 77 bytes defining `+/2` without having to deal with the verbose `term_string/2`, but a lot of unnecessary parentheses would simply not have existed to begin with that way so it would be pretty close to cheating, since all that `+/2` does is handle associativity.
I tried to use `=../2` for all of it, but it came out far longer, because a three-byte operator that works with lists isn't exactly terse:
# [Prolog (SWI)](http://www.swi-prolog.org), 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.
```
[Try it online!](https://tio.run/##bU9Na4NQEDzHXyGe3sc@E58fbQxpicZATkKTgxIkhGJDINGgBnvyr9u10paie5qdmR1m70V@zc@irC9tu@c7V1RpcTuWVXHJzmQPO6or22noiohvIRIxxDzUFQTILHX9EMIKvASI1y8@rBMIfgQ/gU2Pg47fiHixEj54Yg3xn58uomWst8UjO76fypQEn/eCqq5QJh2avqXl41qBMvnIi9upIlpTq@JFbeomazINDp0JelOCZZVXof5GacRihqTcMDSU/isGl5SZA95keGPToR/HlibFGcsyhqzBiGTE5BbFPOaM6twc3s0Y5s1GG0g@l/wZe1sOe0KftJiD75G5xaVNKXfo@J/8uwZq7Rc "Prolog (SWI) – Try It Online")
]