Jujukan kurungan biasa terdiri daripada kurungan buka dan tutup satu atau lebih jenis, dengan setiap kurungan bukaan mempunyai kurungan penutup dan (dalam kes berbilang jenis) jenis kurungan itu tidak bertindih.
SP yang betul:
( ( ) ) ( ) ( )
{ } [ ( ) ] ( )
{ [ ( { } ) ] }
SP tidak sah:
) ) ( ( ) ) ( (
{ [ ( ] ) }
( ( ] }
Untuk menyemak sama ada urutan kurungan kurungan adalah daripada jenis yang sama, cuma semak baki.
Iaitu, kita memulakan pembolehubah sama dengan sifar (baki). Kemudian kita berlari melalui rentetan (jika anda tidak tahu bagaimana untuk melakukan ini - RUN, BODOH!), meningkatkan baki apabila ia bertemu dengan pendakap pembukaan dan mengurangkannya apabila ia bertemu dengan penutup. Jika pada mana-mana peringkat baki menjadi negatif atau pada akhirnya ia tidak sama dengan sifar, maka urutannya adalah salah.
|
Dalam kes kehadiran kurungan beberapa jenis, semuanya menjadi sedikit lebih rumit. Kami mencipta tindanan untuk bertindak sebagai pembolehubah keseimbangan itu. Ini perlu kerana kurungan tidak boleh bertindih. Apabila kami berjalan melalui garisan dan menemui kurungan pembukaan, kami menolaknya ke atas timbunan. Apabila kami menemui pendakap penutup, kami cuba mengeluarkan pendakap bukaan jenis itu daripada timbunan. Jika pendakap daripada jenis yang berbeza berada pada tindanan, jujukan itu tidak sah. Jika tindanan tidak kosong pada penghujungnya, jujukan itu juga tidak sah.
|
Penjanaan urutan kurungan yang betul mengikut terus daripada cara semakan dilakukan - kita hanya perlu menambah kurungan baharu tanpa melanggar ketepatan. Ini dilakukan dengan lelaran rekursif. Jika anda tidak mengenalinya - BE... ah, tidak, anda boleh cuba memahami dengan membaca lebih lanjut. Berikut ialah contoh kod untuk satu jenis kurungan:
#include <vector>
#include <iostream>
menggunakan ruang nama std;
int n; // Separuh panjang
vektor<char> ans; // Jawapan kami
kosong rec(int baki) {
jika (ans.size() == 2 * n) { // Jika ia berlaku, maka kita selesai
untuk (int i = 0; i < 2 * n; i++)
cout << ans[i] << " ";
cout << "\n";
}
jika (ans.size() + baki + 2 <= n * 2) { // Semak, kami Akan berjaya kami menutup pendakap pembukaan baharu
// Sekarang perhatikan tangan anda: kita tidak perlu membuat vektor berasingan untuk setiap jujukan
ans.push_back('(');
rec(baki + 1);
ans.pop_back(); // Untuk memahami perkara ini, anda perlu sedar tentang rekursi. Mula-mula, kami menambah kurungan pada vektor, dan kemudian kami melaksanakan semua kod ini sekali lagi.
// Iaitu, tambahkan kurungan sekali lagi, jika kita boleh.
// Dan ini akan berlaku sehingga kita mula meninggalkan rekursi - iaitu, sehingga kita mencapai panjang yang dikehendaki.
// Kemudian kurungan akan mula dialih keluar. Jika anda memahami perkara ini - saya mengucapkan tahniah kepada anda, anda hebat.
}
jika (baki > 0) { // Jika kami boleh menutup kurungan, kami menutupnya.
ans.push_back(')');
rec(baki - 1);
ans.pop_back();
}
}
int main()
{
cin>> n;
rec(0);
kembali 0;
}
Dan kini masa kesukaran - anda perlu menulis algoritma untuk beberapa jenis kurungan SENDIRI! Muahahahahahahahahahahah!
|