Remove unnecessary parentheses

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 1

Mathematica, 105 97 91 bytes

^{-6 bytes thanks to Roman!}

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

Replaces + and * with ~~ (StringExpression) and ** (NonCommutativeMultiply) respectively, evaluates it, stringifies it, and replaces the operators back.

Answer 2

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 3

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

A while back I made a PEG implementation in Python. 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 4

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 5

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 6

Retina, 155 bytes

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

Try it online!

Verify all testcases at once.

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 7

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 8

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.

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), 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!

Answer 9

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.