Anda adalah manajer proyek. Suatu hari, salah satu programmer Anda menjadi gila ( bukan kesalahan Anda ) dan mengambil semua ekspresi dalam basis kode dan menambahkan tanda kurung acak kepada mereka, sebelum berhenti di tempat, mengomel tentang ketidakmampuan Anda ( juga bukan kesalahan Anda ). Ini akan menjadi perbaikan yang mudah, namun, untuk beberapa alasan Anda tidak menggunakan kontrol revisi ( sama sekali bukan kesalahan Anda ). Dan untuk beberapa alasan, tidak ada programmer lain yang ingin melalui setiap ekspresi untuk memperbaiki tanda kurung yang tidak cocok ( omong-omong, itu bukan salah Anda ). Pemrogram hari ini, Anda berpikir untuk diri sendiri. Anda harus melakukannya sendiri. Menyeramkan! Tugas semacam itu seharusnya ada di bawahmu ...
Input akan berupa satu baris, yang akan berisi sejumlah tanda kurung kiri ( ( [ {
) dan tanda kurung kanan ( ) ] }
). Ini juga dapat, tetapi tidak selalu, berisi komentar ( /* */
) dan string literal ( " "
atau ' '
) dan berbagai angka, huruf, atau simbol.
Akan ada setidaknya satu braket (di luar komentar atau string literal) yang tidak memiliki lawan yang berlawanan (di luar komentar atau string literal). Misalnya, bandel }
tanpa pendahuluan {
. Contoh lain: (
yang tidak memiliki )
setelahnya. Program Anda akan menggantikan dengan kurung jumlah kurung minimum yang diperlukan untuk membuat kurung cocok.
Contoh:
(4 + (2 + 3))]
==> (4 + (2 + 3))
(braket persegi di akhir)
][][[]]
==> [][[]]
(braket persegi di awal)
("Hel(o!"))
==> ("Hel(o!")
(tanda kurung di akhir)
( /* )]*/
==> /* )]*/
(tanda kurung di awal)
{()]
==> ()
(braket keriting dan braket persegi)
- Input dapat diambil dari cara mana yang paling nyaman (STDIN, argumen baris perintah, membaca dari file, dll.)
- Jika ada lebih dari satu cara untuk menyelesaikan ketidakcocokan dengan jumlah pemindahan yang sama, keduanya dapat diterima.
- Hanya akan ada ketidakcocokan dalam tanda kurung. Literal string dan komentar akan selalu terbentuk dengan benar.
- Judul berasal dari utas SO ini
- Tidak akan pernah ada kutipan dalam komentar, kutipan dalam kutipan, komentar dalam komentar, atau komentar dalam kutipan.
Ini adalah kode golf, jadi jumlah minimum byte menang. Ajukan pertanyaan dalam komentar jika spesifikasinya tidak jelas.
sumber
("foo (\") bar")
)?{{(})
harus{ }
atau setara, karena skenario pembukaan menyiratkan bahwa kode bekerja untuk memulai, dan{(})
dianggap sebagai kurung yang tidak cocok dalam setiap bahasa pemrograman yang saya tahu (yaitu "menyebabkan stasis" ??). Tapi, kemudian, saya sudah menulis jawaban, jadi saya bias.Jawaban:
Ruby, 223 karakter
Yang ini ternyata agak lama.
Apa yang dilakukan adalah mengeluarkan string dan komentar terlebih dahulu, sehingga mereka tidak dihitung (dan memasukkannya kembali nanti).
Kemudian, ia melewati karakter string dengan karakter. Ketika menemukan penyangga pembuka, ia menyimpan posisinya. Ketika menemukan kurung kurawal, itu muncul dari masing-masing susunan kurung kurawal terbuka.
Jika
pop
kembalinil
(yaitu tidak ada kawat gigi pembuka yang cukup), itu akan menghapus kurung kurawal. Setelah semua ini selesai, itu menghapus sisa kawat pembukaan tambahan (yaitu tidak ada kawat penutup cukup).Pada akhir program, ini mengembalikan semua string dan komentar serta mengeluarkannya.
Tidak Disatukan:
sumber
(("string"/*comment*/)"string"
? Jika saya membaca (versi yang tidak di-serigala) dengan benar, Anda mengganti string dan komentar dengan indeks mereka dalamunparsed
array, yang akan mengarah ke substitusi seperti((12)3
dan kemudian mencari indeks yang tidak ada12
(atau11
). Saya melihat versi golf hanya menggunakanshift
, tetapi mungkinkah itu masih memiliki masalah yang sama?Python 3,
410322317Mencoba setiap set penghapusan yang mungkin, mulai dari yang lebih kecil, sampai menemukan satu tempat kawat gigi seimbang. (Maksud saya seimbang sepenuhnya benar:
{{(})
menghasilkan( )
, tidak{(})
.)Versi pertama menggunakan fungsi generator rekursif, yang sangat keren tetapi juga sangat panjang. Versi ini melakukan pencarian pertama yang sederhana menggunakan antrian. (Ya, ini adalah algoritma waktu faktorial. Apa masalahnya?: ^ D)
sumber
C - 406
Percobaan dalam C tanpa menggunakan ekspresi reguler.
Untuk mengkompilasi dan menjalankan (pada mesin linux):
gcc -o brackets.c
./brackets "[(])"
Dalam kasus yang tidak ditentukan seperti [(]) ia mengembalikan pasangan braket yang valid terakhir ()
sumber
Python 3, 320
Seperti solusi DLosc, ini menyelidiki setiap penghapusan yang mungkin, tetapi menggunakan eksplorasi rekursif dan strategi mundur yang jauh lebih cepat. Saya tahu bahwa kecepatan bukanlah kriteria dalam kode golf, dan pencarian lengkap dalam hal apa pun adalah eksponensial, tetapi yang ini dapat menangani input seperti
({({({({({({({({(}}}}}}}}
dalam beberapa detik.sumber
O(n!!)
solusi, bukanO(n!)
. (Golf sayaO(n*2^n)
bukanO(2^n)
, karenao
benar-benar menghasilkan semua pola hinggar
kepindahan, bukanr
kepindahan yang tepat . Mudah diperbaiki, tetapi akan membutuhkan biaya beberapa karakter.)