(Dapatkah saya) Tambahkan tanda kurung untuk menjadikan ini benar

8

Saya melihat pertanyaan membingungkan baru-baru ini:

Tambahkan tanda kurung untuk menjadikan ini benar

Dan melihat bahwa satu jawaban menggunakan skrip Python untuk mencoba semua kemungkinan .

Tantangan Anda adalah, diberi ekspresi (sebagai string) dan integer, adalah membuat program yang dapat menentukan apakah Anda dapat menambahkan parens untuk membuat ekspresi sama dengan integer.

Misalnya, jika ekspresi adalah 1 + 2 * 3dan bilangan bulat 9, maka Anda dapat menambahkan parens seperti (1 + 2) * 3, yang sama dengan 9, sehingga hasilnya harus benar. Tetapi jika ekspresi itu 1 + 2 - 3 * 4 / 5dan bilangan bulatnya adalah 9999999999999, Anda tidak bisa menambahkan jumlah parens apa pun untuk menyamakan itu 9999999999999, jadi outputnya harus falsey.

Perhatikan bahwa input bilangan bulat mungkin positif atau negatif, tetapi ekspresi hanya akan mengandung bilangan bulat positif. Bahkan, ekspresi akan selalu cocok (\d+ [+*/-] )+ \d(regex). Dengan kata lain, tidak ada parens, ada eksponen, hanya +, -, *dan /. Pesanan operator standar ( *dan /, kemudian+ dan -).

Lebih banyak kasus uji:

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

Ada pertanyaan?

Anda dapat mengeluarkan ekspresi dengan tanda kurung jika memungkinkan, misalnya (10 + (9 - 8)) * 7 + (6 - 5) * 4 + 3 - 2 * 1untuk kasus uji terakhir. Saya lebih suka ini daripada hanya nilai kebenaran, tetapi terserah Anda. Penggunaan 2(5)untuk penggandaan tidak diperbolehkan, hanya saja *.

programmer5000
sumber
/Apakah divisi float, kan?
Rod
@ Ya, benar.
programmer5000
1
Anda harus memiliki test case yang membutuhkan hasil antara non-integer untuk digunakan.
feersum
Anda harus menambahkan test case di mana pembagian dengan nol mungkin terjadi, seperti3 / 2 - 1 - 1 and 2 -> 3 / (2 - 1) - 1
mbomb007

Jawaban:

3

Python 2, 286 285 282 byte

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

Cobalah online

Penjelasan:

Versi ini akan mencetak semua ekspresi yang berfungsi (dengan Fractionobjek).

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

Cobalah online

Referensi:

  1. Fungsi partisi

  2. Zip bergantian

Disimpan 3 byte berkat Felipe Nardi Batista

mbomb007
sumber
1- Dapatkah Anda menggunakan python3 ( /adalah divisi float) dan menghapus semua fractionspenggunaan? 2 - Bagaimana dengan pembagian dengan 0?
Rod
@Rod Tidak, Anda tidak bisa. Divisi float adalah alasan diperlukan.
mbomb007
Lalu apa alasannya?
Rod
oh, masalah pembulatan
Rod
Saya memperbaiki pembagian dengan nol masalah. Itu masih bekerja untuk setiap contoh di mana solusinya datang sebelum pembagian dengan nol, tetapi saya memang menemukan test case yang memecahkannya. Ini adalah test case terakhir di test suite saya.
mbomb007