Parenthesize an expression
JavaScript (ES6) 179 (263 -20% -5% -10%)
(x,W=[],Q=['('],z=1,w=v='',h=p=>'*/+-))('.indexOf(p)|1,C=n=>{for(;h(q=Q.pop())<=h(n);)W[0]=`(${W[1]+q+W.shift()})`;z&&Q.push(q,n)})=>(x+')').replace(/[\d.]+|\S/g,t=>t>'('?t>')'?~h(t)?z?(w+='('+t,v+=')'):C(t,z=1):W=[w+t+v,...W,z=w=v='']:C(t,z=0):z=Q.push(t))&&W[0]
As the other two answers are currently both wrong, I'll post mine. It's a variation of the expression parser that I used here and here and somewhere else. Look there for more detailed algorithm explanations.
It's quite bulky but it should work.
Test snippet
f=(x,W=[],Q=['('],z=1,w=v='',h=p=>'*/+-))('.indexOf(p)|1,C=n=>{for(;h(q=Q.pop())<=h(n);)W[0]=`(${W[1]+q+W.shift()})`;z&&Q.push(q,n)})=>(x+')').replace(/[\d.]+|\S/g,t=>t>'('?t>')'?~h(t)?z?(w+='('+t,v+=')'):C(t,z=1):W=[w+t+v,...W,z=w=v='']:C(t,z=0):z=Q.push(t))&&W[0]
// More readable
x=(x,W=[],Q=['('],z=1,w=v='',
h=p=>'*/+-))('.indexOf(p)|1,
C=n=>{
for(;h(q=Q.pop())<=h(n);)W[0]=`(${W[1]+q+W.shift()})`;
z&&Q.push(q,n)
}
)=>(
(x+')')
.replace(/[\d.]+|\S/g,t=>
t>'('
?t>')'
?~h(t)
?z
?(w+='('+t,v+=')')
:C(t,z=1)
:W=[w+t+v,...W,z=w=v=''] // overfill W to save 2 chars ()
:C(t,z=0)
:z=Q.push(t)
),
W[0]
)
console.log=(...x)=>O.textContent+=x.join` `+'\n'
// TEST
;[
['1+2*3','(1+(2*3))'],['2*(3+4)','(2*(3+4))'],['2*3/4+3','(((2*3)/4)+3)'],['342*32/8','((342*32)/8)'],
['3+-5','(3+(-5))'],['-3+-4*7','((-3)+((-4)*7))'], // bonus 20%
['3 + 4','(3+4)'], // bonus 5%
['1+.12','(1+.12)'],['1+0.21/3','(1+(0.21/3))'] // bonus 10%
].forEach(t=>{var k=t[1],i=t[0],r=f(i); console.log(i+' : '+r+(r==k? ' OK':' Fail expecting '+k))})
<pre id=O></pre>
Python, 153 * 0.9 = 137.7 bytes
def p(e):
for o in"+-*/":
for i,c in enumerate(e):
if(c==o)*(0==sum([(d=="(")-(d==")")for d in e[:i]])):return"("+p(e[:i])+o+p(e[i+1:])+")"
return e
This program handles decimal input.
The second line begins with a space, the second begins with a tab, the third with two tabs and the third with a space. This saved one byte. Here's a hexdump (xxd
p p):
0000000: 6465 6620 7028 6529 3a0a 2066 6f72 206f def p(e):. for o
0000010: 2069 6e22 2b2d 2a2f 223a 0a09 666f 7220 in"+-*/":..for
0000020: 692c 6320 696e 2065 6e75 6d65 7261 7465 i,c in enumerate
0000030: 2865 293a 0a09 0969 6628 633d 3d6f 292a (e):...if(c==o)*
0000040: 2830 3d3d 7375 6d28 5b28 643d 3d22 2822 (0==sum([(d=="("
0000050: 292d 2864 3d3d 2229 2229 666f 7220 6420 )-(d==")")for d
0000060: 696e 2065 5b3a 695d 5d29 293a 7265 7475 in e[:i]])):retu
0000070: 726e 2228 222b 7028 655b 3a69 5d29 2b6f rn"("+p(e[:i])+o
0000080: 2b70 2865 5b69 2b31 3a5d 292b 2229 220a +p(e[i+1:])+")".
0000090: 2072 6574 7572 6e20 650a return e.
Here's a program I used for testing: (Save the program above as paren.py
)
import paren
cases = {
"2+3*4": "(2+(3*4))",
"(2+3)*4": "((2+3)*4)",
"1+2+3+4": "(1+(2+(3+4)))",
"3/2+5": "((3/2)+5)",
"1+2-3": "(1+(2-3))",
"2-1+2": "((2-1)+2)",
"3+-5": "(3+(-5))",
"1+.12": "(1+.12)",
"1+0.21/3": "(1+(0.21/3))",
}
for num, case in enumerate(cases):
print "\n\n\033[1m\033[38;5;14mCase #%d: %s" % (num + 1, case)
result = paren.p(case)
print "\033[38;5;4mParenthesize returned: %s" % (result)
solution = cases[case]
if result == solution:
print "\033[38;5;76mCorrect!"
else:
print "\033[38;5;9mNot correct!"
Make sure that your terminal uses the \033[38;5;<COL>m
escape code for colors.