String seimbang adalah string tanda kurung ()
sehingga setiap tanda kurung dapat dicocokkan dengan yang lain. Lebih tepatnya mereka adalah string yang direntang oleh tata bahasa ini:
S → (S)S | ε
Kita dapat mengubah string "dalam ke luar" dengan:
Mengganti semua kejadian dari
(
dan)
dengan satu sama lainMemindahkan karakter dari depan string ke belakang hingga string seimbang kembali.
Mari kita lakukan sebuah contoh.
Kami mulai dengan string seimbang:
(()(())())
Kami kemudian beralih ke parens untuk membuat
))())(()((
Kemudian pindahkan karakter dari depan string ke belakang string sampai string seimbang.
))())(()((
)())(()(()
())(()(())
))(()(())(
)(()(())()
(()(())())
Itulah hasil kami!
Perhatikan bahwa beberapa string dapat dibalik keluar dengan berbagai cara, misalnya string
(()())
Ketika dibalik-balik bisa berupa:
()(())
atau
(())()
Namun setiap string memiliki setidaknya satu solusi .
Tugas
Tulis sebuah program untuk mengambil string seimbang sebagai input dan output string yang terbalik. Dalam kasus di mana mungkin ada beberapa output yang valid, Anda hanya perlu menampilkan salah satu dari mereka. Anda dapat menggunakan jenis kurung yang berbeda ( <>
, []
atau {}
) jika diinginkan.
Ini adalah kompetisi kode-golf sehingga Anda harus berusaha meminimalkan ukuran kode sumber Anda, yang diukur dengan byte.
Uji Kasus
(()()) -> ()(()), (())()
(()(())()) -> (()(())())
((())())() -> (()(()()))
sumber
Jawaban:
Haskell ,
12412011911711311010910610510410198 byte4 byte disimpan berkat bartavelle!
3 byte disimpan berkat Zgarb
1 byte disimpan berkat Peter Taylor
Inilah solusi yang saya kerjakan di Haskell. Tidak
apa-apa sekarangcukup baik berkat bantuan yang saya terima, tapi saya ingin membuat ini lebih pendek, jadi umpan balik / saran sangat dihargai.Cobalah online!
Penjelasan
Program ini mendefinisikan 4 fungsi, yang pertama
(!)
menentukan apakah string seimbang. Yang didefinisikan sebagai berikut:Pemeriksaan ini mengasumsikan bahwa input memiliki jumlah paren buka dan tutup yang sama berkat saran dari Peter Taylor.
Selanjutnya
g
akan memutar string sekali.Kemudian kita memiliki
d
yang hanya mengambil paren dan mencerminkannyaAkhirnya kita memiliki fungsi yang menjadi perhatian kita. Di sini kami menggunakan representasi pointfree yang
until(!0)g
dibuat denganmap d
, yang memetakand
ke input dan berlakug
hingga hasilnya seimbang. Ini adalah proses persis yang dijelaskan dalam pertanyaan.sumber
g x@(a:b)|x!0=x|1>0=g$b++[a]
dan menghapus parens untukd '('=')'
.d
menyebabkan kesalahan kompiler, percayalah, saya sudah mencoba. Tapi saran pertama diterima. Terima kasih!!
karena Anda tidak perlu menangani case di mana string memiliki jumlah tanda kurung buka dan tutup yang tidak sama, sehingga Anda dapat menukar dua case pertama dan memilikinya_!1=1<0
[]!_=0<1
until
untuk mempersingkatg
: TIOd
peta'('
ke(-1)
dan apa pun yang lain1
, dan kemudian dua kasus terpanjang!
dapat digabungkan(i:a)!x=a!(x+i)
. Struktur tingkat atas kemudian perlu dikerjakan ulang untuk mendorongmap d
ke dalamuntil
kondisi, dan saya harus berlari sehingga saya tidak punya waktu sekarang untuk mencari tahu apa yang diperlukan kombinator untuk merekatkan semuanya.SOGL V0.12 ,
1211 byteCoba Di Sini!
Penjelasan:
Catatan:
l{
dapat diganti dengan ( untuk 10 byte, tetapi, sayangnya, itu tidak diterapkan.sumber
CJam (20 karakter)
Demo online
atau untuk jumlah char yang sama
Demo online
Pembedahan
Kedua versi memiliki header dan footer yang sama
Kemudian bit di tengah jelas menghitung seberapa jauh perlu diputar. Keduanya menggunakan evaluasi dan mengandalkan
(
menjadi operator penurunan CJam dan)
menjadi operator kenaikan.vs.
sumber
JavaScript (ES6),
111105 byte(Disimpan 2 byte berkat @CraigAyre, 2 byte terima kasih kepada @PeterTaylor, 2 byte terima kasih kepada @Shaggy.)
Tidak Disatukan:
Kasus uji:
Tampilkan cuplikan kode
sumber
Retina ,
4638 byteCobalah online! Tautan termasuk kasus uji. Sunting: Disimpan 8 byte dengan bantuan dari @MartinEnder. Tahap pertama hanya mentranspos kurung, sedangkan tahap kedua mencari sufiks terpanjang yang merupakan awalan seimbang yang valid, yang tampaknya merupakan kondisi yang cukup untuk rotasi agar sepenuhnya seimbang. Penyeimbangan terdeteksi menggunakan kelompok penyeimbang. Konstruk
((\()|(?<-4>\)))+
cocok dengan sejumlah(
s ditambah jumlah)
s selama kita sudah (<-4>
) melihat banyak(
s. Karena kami hanya mencari awalan yang valid, kami tidak harus mencocokkan sisanya)
.sumber
((\()|(?<-2>\)))
. Tapi upaya Anda hanya mengilhami saya untuk menemukan pendekatan yang sama sekali baru yang menyimpan dua lain:(?<-1>(\()*\))+
. Ini tentu akan berguna di masa depan, jadi terima kasih. :)(?<-1>(\()*\))+
bahkan bekerja, karena tampaknya ingin muncul dari1
tumpukan sebelum benar-benar cocok dengan apa pun ...\(*
sekalipun.PHP,
110108 byteJalankan sebagai pipa dengan
-nR
atau uji secara online .kerusakan
sumber
Python 3 ,
112103101 byte-2 byte terima kasih kepada @ Mr.Xcoder
Cobalah online!
sumber
Oktaf, 62 byte
Cobalah online!
Fungsi yang mengambil string sebagai input dan mencetak semua hasil.
Penjelasan:
sumber
Mathematica, 78 byte
sumber
JavaScript (ES6), 97 byte
Bekerja dengan memutar string input secara rekursif hingga transposnya seimbang, lalu mentransposasinya.
sumber
APL (Dyalog Unicode) ,
3530 byteGolf pendekatan baru berkat @ Adám
Cobalah online!
Golf sedang berlangsung.
Penjelasan
sumber
Python 2 , 99 byte
Cobalah online!
Dalam bentuk fungsi untuk kasus uji mudah:
Python 2 , 108 byte
Cobalah online!
Ini menggunakan pendekatan yang sedikit berbeda - alih-alih memutar string secara rekursif, jika kita menganggap parens sebagai penambahan dan penurunan beberapa penghitung keseimbangan, maka string yang seimbang tidak boleh memiliki jumlah total penambahan - pengurangan yang kurang dari 0.
Jadi kami ambil
membalikkan parens:
dan mengonversinya menjadi daftar jumlah kenaikan / penurunan:
-3 adalah minimum pada indeks 4 (berbasis nol); jadi kami ingin beralih dengan indeks itu +1. Ini menjamin bahwa kenaikan / penurunan kumulatif tidak akan pernah kurang dari 0; dan akan berjumlah 0.
sumber
r=0,
bukanr=[0]
?r+=[r[-1]+2*b-1]
denganr+=r[-1]+2*b-1,
sertaClojure, 118 byte
Mengembalikan urutan karakter, jadi saya akan menyebutnya seperti ini:
Pertama-tama membalik kurung, kemudian loop selama jumlah kumulatif jumlah braket menjadi negatif di beberapa titik urutan.
sumber
brainfuck , 82 byte
Cobalah online!
Penjelasan
Dengan setiap karakter dibaca, penghitung diubah sebagai berikut:
)
, penghitung meningkat sebesar 1.(
, penghitung berkurang sebesar 1, kecuali penghitung adalah 0, dalam hal ini penghitung tidak berubah.Setiap awalan adalah akhiran valid dari string seimbang (setelah inversi) jika dan hanya jika penghitung ini adalah 0. Kode ini menggunakan awalan terlama untuk membentuk output.
sumber