21
\$\begingroup\$

Recently I've been writing a new language, to avoid needing to handle order of operations, I simply parenthesize each expression properly to avoid this entirely.

Because parenthesis are at char-codes 40-41, your code will need to be as short as possible.


Examples

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)

Rules

The only operations you'll need to handle are: * (multiplication), / (division), + (addition), and - (subtraction).

  • The order of operations is:
    • Parenthesis
    • Multiplication, Division
    • Adition, Subtraction
  • You should prefer to go left-right
  • The input numbers will always be positive integers (see bonuses)

Bonuses

-20% if you handle negation:

3+-5
(3+(-5))

-5% if you allow spaces to be placed inside the input:

3  + 4
(3+4)

-10% if you can handle decimals in the input:

1+.12
(1+.12)
1+0.21/3
(1+(0.21/3))

500 bounty: if you manage to write an answer in Unnamed/Blocks

\$\endgroup\$
17
  • 25
    \$\begingroup\$ "Because parenthesis are at char codes 40-41, your code will need to be as short as possible." OK, now you're just being plain ridiculous. ;P \$\endgroup\$ Dec 24, 2015 at 21:06
  • 3
    \$\begingroup\$ And this is easier than prefix (Polish) notation because? \$\endgroup\$
    – wizzwizz4
    Dec 24, 2015 at 21:12
  • 3
    \$\begingroup\$ Possible duplicate. \$\endgroup\$
    – flawr
    Dec 24, 2015 at 22:02
  • 8
    \$\begingroup\$ @flawr I saw that but it's very different in the fact that that question has you output all ways parenthesizing an expression. Here you have to take into account order of operations which I think is a significant difference as code can't be trivially modified for this challenge \$\endgroup\$
    – Downgoat
    Dec 24, 2015 at 22:20
  • 3
    \$\begingroup\$ Important test case: 1+2+3+4 (which certain solutions might parenthesise as ((1+2)+(3+4))) \$\endgroup\$ Dec 24, 2015 at 23:25

3 Answers 3

3
+100
\$\begingroup\$

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>

\$\endgroup\$
2
\$\begingroup\$

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 (xxdp 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.

\$\endgroup\$
3
  • \$\begingroup\$ *fourth with a space? \$\endgroup\$
    – Element118
    Dec 28, 2015 at 23:27
  • 1
    \$\begingroup\$ This program does not prefer to go left-right. Try the test case 3 in the OP, your result is not correct. This can be a real issue for example with integer arithmetic: ((2*(3/4))+3) != (((2*3)/4)+3) \$\endgroup\$
    – edc65
    Dec 29, 2015 at 12:30
  • 1
    \$\begingroup\$ @user12365 Not using integer arithmetic (in C or C++ for example) 3/4 == 0, so ((2*(3/4))+3) is 3, while (((2*3)/4)+3) is 4 \$\endgroup\$
    – edc65
    Dec 30, 2015 at 14:01
1
\$\begingroup\$

Python, 241 * 0.8 * 0.95 * 0.9 = 164.84 characters

I'm using the ast (Abstract Syntax Trees) library, and a homebrew string replacement dict. The string replacement costs a lot, but the bonus helps in keeping the score somewhat low. Maybe (the string replacement part) can be golfed further.

Note that this solution adds an extra set of parenthesis around each number, but I think that's within the spirit of the question

import ast;def p(e):
 r,s={"Module([":"",")])":"","Expr(":"","BinOp":"","Num":"",", Add(), ":"+",", Sub(), ":"-",", Div(), ":"/",", Mult(), ":"*"},ast.dump(ast.parse(e),annotate_fields=False)
 for f,t in r.iteritems():s=s.replace(f,t)
 return s

Test suite:

cases = {
    "2+3*4", 
    "(2+3)*4", 
    "1+2+3+4", 
    "3/2+5", 
    "1+2-3", 
    "2-1+2",
    "3+-5",
    "1+.12",
    "1+0.21/3"
}

for num,case in enumerate(cases):
    result = p(case)
    print "Case {}: {:<16} evaluates to: {}".format(num+1,case,result)

Output of the test suite:

Case 1: 3+-5             evaluates to: ((3)+(-5))
Case 2: 3/2+5            evaluates to: (((3)/(2))+(5))
Case 3: 2+3*4            evaluates to: ((2)+((3)*(4)))
Case 4: 1+2+3+4          evaluates to: ((((1)+(2))+(3))+(4))
Case 5: 1+0.21/3         evaluates to: ((1)+((0.21)/(3)))
Case 6: (2+3)*4          evaluates to: (((2)+(3))*(4))
Case 7: 2-1+2            evaluates to: (((2)-(1))+(2))
Case 8: 1+.12            evaluates to: ((1)+(0.12))
Case 9: 1+2-3            evaluates to: (((1)+(2))-(3))
\$\endgroup\$
5
  • \$\begingroup\$ Missing import ast in your code \$\endgroup\$
    – edc65
    Dec 30, 2015 at 9:11
  • \$\begingroup\$ And that is not the right way to compund percent bonus. If you get a discount of 50% and on top of that another of 50%, your are not paying 0. Your score should be 157.32 (something more after adding the import line). That is a good score - I'll upvote if you make the fix \$\endgroup\$
    – edc65
    Dec 30, 2015 at 9:15
  • \$\begingroup\$ Good point. Added the import. 241 characters now. Not sure how to calculate the bonus though. If I understand your comment correctly, the order in which the bonus is subtracted matters... \$\endgroup\$
    – agtoever
    Dec 30, 2015 at 9:31
  • \$\begingroup\$ The bonus is not subtracted (it's a multiplication) and the order does not matter. 241*(1-20%)*(1-5%)*(1-10%) => 241*0.8*0.95*0.9 => 164.84 \$\endgroup\$
    – edc65
    Dec 30, 2015 at 9:57
  • \$\begingroup\$ @edc65 Ah. Right. Wasn't thinking straight. Thanks. \$\endgroup\$
    – agtoever
    Dec 30, 2015 at 13:46

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.