Kurung Normal ( ()
, []
, <>
dan {}
) bagus dan tidak ambigu, namun seseorang berpikir itu akan menjadi ide yang baik untuk menggunakan karakter non bracket sebagai tanda kurung. Karakter-karakter ini, |
dan "
, bersifat ambigu. Misalnya tidak
""""
sesuai dengan
(())
atau
()()
Tidak mungkin dikatakan.
Hal-hal mulai menjadi menarik ketika Anda mencampur jenis kurung ambigu, misalnya
"|""||""|"
Bisa salah satu dari yang berikut ini
([(([]))]),([()[]()]),([()][()])
Tugas
Tugas Anda adalah mengambil string yang terbuat dari karakter yang ambigu dan menghasilkan semua string seimbang yang mungkin dimaksudkan penulis.
Lebih konkret Anda keluaran semua string yang seimbang yang dapat dibuat mengganti |
dengan baik [
atau ]
dan "
dengan baik (
atau )
. Anda seharusnya tidak menghasilkan string seimbang dua kali.
IO
Sebagai input, Anda harus mengambil string yang terdiri dari |
dan "
. Jika Anda ingin memilih dua karakter berbeda selain |
dan "
berfungsi sebagai pengganti, Anda dapat melakukannya. Anda harus menghasilkan wadah string yang seimbang. Anda dapat memilih untuk mengganti []
dan ()
di output dengan dua pasang braket lainnya ( ()
, []
, <>
atau {}
) yang Anda inginkan. Format output Anda harus konsisten di seluruh proses.
Mencetak gol
Ini adalah kode-golf sehingga jawaban akan dicetak dalam byte dengan lebih sedikit byte yang lebih baik.
Uji kasus
"" -> ["()"]
"|"| -> []
||| -> []
"""" -> ["(())","()()"]
""|| -> ["()[]"]
"|"||"|" -> ["([([])])"]
"|""||""|" -> ["([(([]))])","([()[]()])","([()][()])"]
sumber
Jawaban:
Python 2 , 135 byte
Cobalah online!
Mengharapkan input seperti
2002
bukan"||"
, dan dibungkus dengan tanda kutip.Iterasikan semua 2 N kemungkinan penugasan "buka" dan "tutup" ke string, buat string
c
seperti:Jika
eval
-ing string ini melempar pengecualian, itu tidak cocok. Jika tidak, kami mencetakc[::2]
, memberikan:sumber
Retina ,
595655 byteCobalah online! Sayangnya pengujian untuk dua set tanda kurung yang melebihi golfiness dari satu .NET regex, sehingga menghemat 15 byte untuk diperiksa secara manual. Sunting: Disimpan
34 byte berkat @ H.PWiz. Penjelasan:Temukan
"
dan buat dua salinan garis, satu dengan a<
dan satu dengan a>
. Lakukan ini satu"
per satu, sehingga masing-masing"
menggandakan jumlah garis.Demikian pula dengan
'
,{
dan}
. Kemudian, terus ganti sampai semua"
dan'
semua salinan sudah diganti.Buat duplikat kurung, dipisahkan dengan a
_
.Dalam duplikat, berulang kali hapus tanda kurung yang cocok, sampai tidak ada yang tersisa, dalam hal ini hapus
_
juga tanda kurung .Hapus semua baris yang masih memiliki a
_
.Retina ,
747170 byteCobalah online! Penjelasan: Dua tahap pertama adalah seperti di atas. Tahap ketiga langsung mencetak hasil pencocokan dua set tanda kurung yang cocok. Ini menggunakan grup penyeimbang .NET. Pada setiap tahap dalam pertandingan, regex mencoba untuk mencocokkan karakter, kemudian mencari kembali sepasang tanda kurung yang cocok, lalu periksa bahwa bagian atas tumpukan cocok dengan braket terbuka. Jika dapat melakukan ini, itu berarti braket menyeimbangkan, dan braket terbuka akan muncul dari tumpukan. Kalau tidak, asumsinya adalah kita berada di braket terbuka yang perlu didorong ke tumpukan. Jika asumsi ini tidak berlaku maka tumpukan tidak akan kosong di akhir dan pertandingan akan gagal.
Pendekatan alternatif, juga
7471 byte:Di sini, kita melihat ke depan untuk
<
...>
atau{
...}
, lalu melihat ke belakang untuk mendorong braket penutup ke tumpukan. Kalau tidak, kita harus mencocokkan dan membuka braket penutup yang sudah kita tangkap sebelumnya. Dalam versi ini regex bahkan mungkin tidak sampai ke akhir string, tetapi beberapa string seperti<<<>
akan menyelinap melalui jaring jika kita tidak memeriksa tumpukan kosong.sumber
|
inputSekam , 19 byte
Cobalah online! Menggunakan karakter
ds
dalam input, dan pasangan braket yang sesuaide
danst
dalam output.Penjelasan
Idenya adalah untuk menghasilkan semua tanda kurung yang mungkin dari input dan menjaga mereka yang mengurangi ke string kosong ketika kita berulang kali menghapus tanda kurung yang berdekatan. Ini
¨÷₂¨
adalah string terkompresi yang mengembang ke"dest"
, yang dipilih karena memiliki bentuk terkompresi pendek dan terdiri dari pasangan karakter dengan codepoint yang berdekatan. Dengan demikian program ini setara dengan yang berikut ini.sumber
Perl,
565553 byteTermasuk
+1
untukn
digunakan
[
untuk[]
dan{
untuk{}
Menghasilkan semua 2 ^ N kemungkinan, kemudian menggunakan perl
eval
untuk memeriksa apakah string seperti '+ [+ {}]' adalah kode yang valid dan jika demikian hapus+
dan cetak hasilnyasumber
APL (Dyalog Classic) ,
5553 byteCobalah online!
sumber
Bersih ,
203186179 byteCobalah online!
Hanya menggunakan pencocokan pola dan pemahaman.
sumber
Perl, 56 byte
Termasuk
+
untukn
Menggunakan input
[
untuk output[
atau]
Menggunakan input
{
untuk output{
atau}
Menggunakan regex diperpanjang perl untuk mencocokkan kawat gigi sambil melacak pilihan yang dibuat selama backtracking. Ini bisa menjadi jauh lebih efisien daripada menghasilkan semua kandidat 2 ^ N karena sudah menolak banyak tugas yang tidak mungkin saat setengah jalan melalui string input
sumber
Kotlin ,
240236234 byteYg diperindahkan
Uji
Suntingan
true
->1>0
dan== 0
->< 1
sumber
C (gcc) , 315 byte
Cobalah online!
C (gcc) , 334 byte (versi lama)
Cobalah online!
Penjelasan (versi lama)
Cobalah online!
sumber
*s++
di beberapa tempat.char S[n],*s=S
masih lebih pendek darichars*s=calloc(n,1)