(Can I) Add parentheses to make this true

Question

I saw this recent Puzzling question:

Add parentheses to make this true

And saw that one answer used a Python script to try all possibilities.

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 *.

Answer 1

Python 2, 286 285 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:

1. Partitioning function

2. Alternating zip

_{Saved 3 bytes thanks to Felipe Nardi Batista}