Ekspresi kurung sepenuhnya

11

Hari ini tantangan Anda adalah menghasilkan semua tanda kurung penuh ekspresi yang mungkin.

Input Anda adalah satu baris ASCII yang dapat dicetak yang berisi satu atau lebih istilah yang dipisahkan oleh operator. Input mungkin juga mengandung spasi - Anda harus mengabaikannya. Istilahnya adalah [a-zA-Z0-9], operator [^ ()a-zA-Z0-9]. Anda dapat mengasumsikan bahwa input selalu valid.

Keluarkan semua cara yang mungkin untuk sepenuhnya mengurung ekspresi yang diberikan, dipisahkan oleh baris baru dengan baris tambahan opsional.

Apakah tidak :

  • Istilah kurung - hanya kurung di sekitar operator.
  • Susun ulang persyaratan.
  • Keluarkan spasi apa saja.

Contoh input / output:

N
N

a * b
(a*b)

x_x_0
(x_(x_0))
((x_x)_0)

a * b|c|d
(a*(b|(c|d)))
(a*((b|c)|d))
((a*b)|(c|d))
((a*(b|c))|d)
(((a*b)|c)|d)

Kode terkecil dalam byte menang.

orlp
sumber
Anda harus mencantumkan operator persis yang harus kita pertimbangkan. Apakah !seorang operator? Bagaimana dengan ?
Pengoptimal
@Optimizer Saya mencantumkan ekspresi reguler yang tepat dari apa yang dianggap operator. !cocok dengan regex, demikian juga , namun tidak dapat menjadi bagian dari input karena ASCII tidak dapat dicetak.
orlp
Ah baiklah. Jadi apa pun kecuali istilah adalah operator ...
Pengoptimal
Jadi baik istilah dan operator selalu satu karakter?
user81655
1
masukkan permainan wajib terkait LISP wajib di sini
kucing

Jawaban:

2

Pyth, 38 byte

L?tbsmmjj@bdk"()"*y<bdy>bhd:1lb2bjy-zd

Cobalah online.

Ini mendefinisikan fungsi rekursif yang:

  • mengembalikan input jika panjangnya adalah 1
  • mengambil semua dua-split input pada operator, dan untuk setiap pemisahan:
    • menyebut dirinya secara rekursif pada setiap bagian
    • mengambil produk Cartesian dari hasil masing-masing setengah
    • bergabung dengan setiap hasil oleh operator di split
    • kurung hasil yang bergabung
  • dan akhirnya menggabungkan array yang dihasilkan.

Fungsi ini kemudian dipanggil dengan string input dengan spasi dihapus dan hasilnya digabungkan oleh baris baru.

PurkkaKoodari
sumber
3

JavaScript (ES6), 208 197 byte

s=>((q=x=>x.map((_,i)=>(a=[...x.slice(0,i*=2),p="("+x[i]+x[++i]+x[++i]+")",...x.slice(i+1)],x[i]?a[1]?q(a):r.push(p):0)))([...s.replace(/ /g,o="")],r=[]),r.map((l,i)=>r.indexOf(l)<i?0:o+=l+`
`),o)

Penjelasan

Menggunakan fungsi rekursif yang mengambil array [ t, o, t, o, etc... ]dan kurung setiap pasangan berturut-turut dari dua istilah bersama-sama suka [ (tot), o, etc... ]dan mengulangi proses ini sampai hanya ada satu elemen dalam array, kemudian menyaring nilai duplikat.

s=>(                                  // s = input string
  (q=x=>                              // q = parenthesise array function
    x.map((_,i)=>(
      a=[                             // a = p with parenthesised pair of terms
        ...x.slice(0,i*=2),
        p="("+x[i]+x[++i]+x[++i]+")", // parenthesise and join 2 terms and an operator
        ...x.slice(i+1)
      ],
      x[i]?a[1]                       // make sure the loop is not over
        ?q(a)                         // check next level of permutations
        :r.push(p)                    // add the permutation to the results
      :0
    ))
  )([...s.replace(/ /g,               // remove spaces and parenthesise all expressions
    o="")],                           // o = output string
    r=[]),                            // r = array of result strings
  r.map(                              // filter out duplicates
    (l,i)=>r.indexOf(l)<i?0:o+=l+`
`
  ),o)                                // return o

Uji

pengguna81655
sumber