32
\$\begingroup\$

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
\$\endgroup\$
  • 1
    \$\begingroup\$ More testcases please? \$\endgroup\$ – Leaky Nun May 5 '16 at 10:20
  • 2
    \$\begingroup\$ 1*(2*(3+4)*5)*6 should be an interesting testcase (which my solution currently fails for). \$\endgroup\$ – Leaky Nun May 5 '16 at 10:46
  • 8
    \$\begingroup\$ Is "unnecessary" defined structurally or on a per-case basis? In other words, are the parentheses unnecessary here? (2+2)*1 \$\endgroup\$ – Luis Mendo May 5 '16 at 14:00
  • 2
    \$\begingroup\$ @LuisMendo I think it's fair to interpret it in either way \$\endgroup\$ – anatolyg May 5 '16 at 16:49
  • 2
    \$\begingroup\$ @anatolyg I don't think that'd be fair, because the approaches for the two would be very different. It would be good if we got some clarification. \$\endgroup\$ – Sp3000 May 6 '16 at 23:23
14
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ What? Mathematica doesn't have a built-in? \$\endgroup\$ – Erik the Outgolfer Oct 6 '16 at 8:20
  • \$\begingroup\$ @EriktheGolfer It basically does; I'm trying to make it not evaluate the operators. \$\endgroup\$ – LegionMammal978 Oct 6 '16 at 10:25
  • \$\begingroup\$ That's why Mathematica is so-advertised and so-expensive... because of the built-ins I think. But, Mathematica hasn't got a change over other languages if the puzzle is tough enough, yet "other languages" don't compete at all here. \$\endgroup\$ – Erik the Outgolfer Oct 6 '16 at 10:30
  • \$\begingroup\$ 91 bytes by using StringExpression instead of Dot, and removing the " "->"" clause: a=StringReplace;ToString@ToExpression@a[#,{"*"->"**","+"->"~~"}]~a~{" ** "->"*","~~"->"+"}& \$\endgroup\$ – Roman Jun 16 at 19:30
  • \$\begingroup\$ @Roman Thanks! It seems you found another good associative non-commutative unevaluated operator that doesn't combine with numbers. \$\endgroup\$ – LegionMammal978 Jun 17 at 16:35
7
\$\begingroup\$

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>

\$\endgroup\$
  • \$\begingroup\$ Why did you wrote y.indexOf('+') instead of y.indexOf`+`[...]? ([...] added to avoid tripping the formatting) Was it bugging out that way? \$\endgroup\$ – Ismael Miguel May 6 '16 at 8:32
  • 1
    \$\begingroup\$ Here you go, 170 bytes: a=>eval(`for(b=s=[]${_=';a!=b;a=b.replace(/'}\\(([^()]*)\\)(?=(.?))/,(x,y,z,p)=>~y.indexOf('+')<0?-s.push(b[p-1]=='*'|z=='*'?x:y):y))b=a;for(b=0${_}-\\d+/,x=>s[~x]))b=a`) \$\endgroup\$ – Ismael Miguel May 6 '16 at 8:46
  • \$\begingroup\$ @IsmaelMiguel that's really clever, thanks! Lesson learned: when passing to eval, rethink it all again \$\endgroup\$ – edc65 May 6 '16 at 9:19
  • \$\begingroup\$ I'm glad you liked my simple solution to reduce your code. I wish I could do something about for(b=, =='*' and other repeated bits. Also, isn't ~y.indexOf('+')<0 the same as ~y.indexOf('+')? Since the only value that indexOf() returns that evaluates to a falsy value is -1, the <0 seems redundant. Or, if I got it wrong, you could do y.indexOf('+')>1 \$\endgroup\$ – Ismael Miguel May 6 '16 at 9:40
  • \$\begingroup\$ @IsmaelMiguel 1: yes, the <0 is crap remaining from the ungolfed version and should be removed. 2: thinking again, the for can be revised to be included in the repeated part. Thanks again \$\endgroup\$ – edc65 May 7 '16 at 15:02
5
\$\begingroup\$

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.

\$\endgroup\$
4
\$\begingroup\$

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
\$\endgroup\$
4
\$\begingroup\$

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 $_
\$\endgroup\$
  • \$\begingroup\$ very nice answer. what is happening with the 0 while syntax? \$\endgroup\$ – Jonah Jun 17 at 1:52
  • 1
    \$\begingroup\$ @Jonah In Ruby, expr while cond is equivalent to while cond; expr; end. Here, I only want to perform cond repeatedly and don't actually have a loop body. Usually one would write this as while cond; end or perhaps loop{ break unless cond } but 0 while cond is fewer bytes. The 0 doesn't do anything; it's just there because the short form of the while loop requires a body. \$\endgroup\$ – ezrast Jun 17 at 22:04
2
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Fails for 1*(2*(3+4)*5)*6. \$\endgroup\$ – orlp May 5 '16 at 10:47
  • \$\begingroup\$ @orlp Thanks, fixed. \$\endgroup\$ – Leaky Nun May 5 '16 at 10:56
  • \$\begingroup\$ Fails for (1*(2+3)+4)*5 \$\endgroup\$ – Sp3000 May 5 '16 at 11:34
  • \$\begingroup\$ @Sp3000 Thanks, fixed. \$\endgroup\$ – Leaky Nun May 5 '16 at 11:46
2
\$\begingroup\$

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
\$\endgroup\$
  • 1
    \$\begingroup\$ This fails the test case 1*(2+3), because OP said not to simplify for special number cases. Good answer though; this has my upvote. \$\endgroup\$ – HyperNeutrino May 7 '16 at 14:03
  • 1
    \$\begingroup\$ @AlexL. Thanks for catching that! I didn't update my test cases D: But it is fixed now. \$\endgroup\$ – NonlinearFruit May 7 '16 at 14:39
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.