(Can I) Add parentheses to make this true

I saw this recent Puzzling question:

Add parentheses to make this true

Your challenge is, given an expression (as a string) and an integer, is to make a program that can tell whether you can add parens to make the expression equal the integer.

For example, if the expression is 1 + 2 * 3 and the integer is 9, than you can add parens like (1 + 2) * 3, which equals 9, so the output should be truthy. But if the expression is 1 + 2 - 3 * 4 / 5 and the integer is 9999999999999, you can't add any amount of parens to make that equal 9999999999999, so the output should be falsey.

Note that the integer input may be positive or negative, but the expression will only contain positive integers. In fact, the expression will always match (\d+ [+*/-] )+ \d (regex). In other words, no parens, no exponents, just +, -, * and /. Standard operator order (* and /, then + and -).

More test cases:

1 + 2 - 3 * 4 / 9 and -1 -> truthy, ((1 + 2) - (3 * 4)) / 9
10 - 9 * 8 - 7 * 6 - 5 * 4 - 3 * 2 - 2 * 1 and 1, falsey, see linked question
10 + 9 - 8 * 7 + 6 - 5 * 4 + 3 - 2 * 1 and 82 -> truthy, (10 + (9 - 8)) * 7 + (6 - 5) * 4 + 3 - 2 * 1
34 + 3 and 15 -> falsey
1 + 2 + 5 + 7 and 36 -> falsey
1 / 10 * 3 + 3 / 10 * 10 and 6 -> truthy, (1/10*3+3/10)*10


Any questions?

You may output the expression with parenthesis if it is possible, for instance (10 + (9 - 8)) * 7 + (6 - 5) * 4 + 3 - 2 * 1 for the last test case. I would prefer this over just a truthy value, but it is up to you. Using 2(5) for multiplication is not allowed, only *.

• / is float division , right?
– Rod
May 18, 2017 at 13:32
• @Rod yes, it is.
– user58826
May 18, 2017 at 13:32
• You should have a test case that requires a non-integer intermediate result to be used. May 18, 2017 at 13:50
• You should add a test case where division by zero might occur, like 3 / 2 - 1 - 1 and 2 -> 3 / (2 - 1) - 1 May 18, 2017 at 18:19

Python 2, 286285 282 bytes

from fractions import*
P=lambda L:[p+[L[i:]]for i in range(len(L))for p in P(L[:i])]or[L]
x,y=input()
x=x.split()
for p in P(['Fraction(%s)'%e for e in x[::2]]):
try:print 1/(eval(''.join(sum(zip(eval(p.replace("['","'(").replace("']",")'")),x[1::2]+[0]),())[:-1]))==y)
except:0


Try it online

Explanation:

This version will print all of the working expressions (with the Fraction objects).

from fractions import*
# Sublist Partitions (ref 1)
P=lambda L:[p+[L[i:]]for i in range(len(L))for p in P(L[:i])]or[L]
x,y=input()
x=x.split()
# Convert all numbers to Fractions for division to work
n=['Fraction(%s)'%e for e in x[::2]]
# Operators
o=x[1::2]
# Try each partition
for p in P(n):
# Move parens to be inside strings
n=eval(p.replace("['","'(").replace("']",")'"))
# Alternate numbers and operators (ref 2)
x=''.join(sum(zip(n,o+[0]),())[:-1])
# Prevent division by zero errors
try:
# Evaluate and check equality
if eval(x)==y:print x
except:0


Try it online

References:

Saved 3 bytes thanks to Felipe Nardi Batista

• 1- Can you use python3 (/ is float division) and drop all fractions uses? 2 - What about divisions by 0?
– Rod
May 18, 2017 at 16:41
• @Rod No, you can't. Float division is the reason it's required. May 18, 2017 at 16:44
• What's the reason then?
– Rod
May 18, 2017 at 16:46
• oh, rounding issues
– Rod
May 18, 2017 at 16:54
• I fixed the division by zero problem. It still worked for any example where the solution came before the division by zero, but I did find a test case that broke it. It's the last test case in my test suite. May 18, 2017 at 16:57