Vi esta reciente pregunta desconcertante:

Agrega paréntesis para hacer esto realidad

Y vi que una respuesta usaba un script de Python para probar todas las posibilidades .

Su desafío es, dada una expresión (como una cadena) y un número entero, es hacer un programa que pueda decir si puede agregar parens para que la expresión sea igual al número entero.

Por ejemplo, si la expresión es 1 + 2 * 3y el entero es 9, entonces puede agregar parens como (1 + 2) * 3, que es igual a 9, por lo que la salida debería ser verdadera. Pero si la expresión es 1 + 2 - 3 * 4 / 5y el entero es 9999999999999, no puede agregar ninguna cantidad de parens para que sea igual 9999999999999, por lo que la salida debería ser falsa.

Tenga en cuenta que la entrada de enteros puede ser positiva o negativa, pero la expresión solo contendrá enteros positivos. De hecho, la expresión siempre coincidirá (\d+ [+*/-] )+ \d(regex). En otras palabras, no hay parens, no hay exponentes, simplemente +, -, *y /. Orden estándar del operador ( *y /, luego, +y -).

Más casos de prueba:

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

¿Alguna pregunta?

Puede generar la expresión entre paréntesis si es posible, por ejemplo, (10 + (9 - 8)) * 7 + (6 - 5) * 4 + 3 - 2 * 1para el último caso de prueba. Preferiría esto sobre un valor verdadero, pero depende de usted. El uso 2(5)para la multiplicación no está permitido, solo *.

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

Pruébalo en línea

Explicación:

Esta versión imprimirá todas las expresiones de trabajo (con los Fractionobjetos).

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

Pruébalo en línea

Referencias

1. Función de partición

2. Cremallera alterna

_{Guardado 3 bytes gracias a Felipe Nardi Batista}