Düzenli parantez dizileri, bir veya daha fazla türün açılış ve kapanış parantezlerinden oluşur; her bir açılış dirseğinin bir kapatma dirseği vardır ve (birden fazla tür olması durumunda) türleri çakışmaz.
Doğru SP:
( ( ) ) ( ) ( )
{ } [ ( ) ] ( )
{ [ ( { } ) ] }
Geçersiz SP:
) ) ( ( ) ) ( (
{ [ ( ] ) }
( ( ] }
Bir parantez dizisinin aynı türden olup olmadığını kontrol etmek için dengeyi kontrol etmeniz yeterlidir.
Yani sıfıra eşit bir değişken başlatıyoruz (bakiye). Sonra ipin üzerinden geçiyoruz (bunu nasıl yapacağınızı bilmiyorsanız - ÇALIŞTIR, APTAL!), açılış dirseğiyle karşılaştığında dengeyi artırıp kapanış dirseğiyle karşılaştığında dengeyi azaltıyoruz. Herhangi bir aşamada bakiye negatif olursa veya sonunda sıfıra eşit değilse sıralama yanlıştır.
|
Birkaç tür parantez olması durumunda, her şey biraz daha karmaşık hale gelir. Bu denge değişkeni olarak işlev görecek bir yığın oluşturuyoruz. Bu gereklidir çünkü parantezler üst üste gelemez. Bir satır boyunca yürüdüğümüzde ve açılan bir parantez ile karşılaştığımızda onu yığının üzerine itiyoruz. Bir kapanış paranteziyle karşılaştığımızda, o türdeki açılış ayracı yığından çıkarmaya çalışırız. Yığın üzerinde farklı türde bir ayraç varsa, sıra geçersizdir. Yığın sonunda boş değilse sıra da geçersizdir.
|
Doğru parantez dizilerinin oluşturulması, kontrolün yapılma şeklini doğrudan takip eder - doğruluğu bozmadan yeni parantezler eklememiz yeterlidir. Bu özyinelemeli yineleme ile yapılır. Onu tanımıyorsanız - BE... ah, hayır, daha fazla okuyarak anlamaya çalışabilirsiniz. İşte bir parantez türü için bir kod örneği:
#include <vector>
#include <iostream>
kullanarak ad alanı std;
int n; // Yarım uzunluk
vektör<char> cevap; // Cevabımız
void rec(int bakiye) {
if (ans.size() == 2 * n) { // Varsa, biz bitti
için (int i = 0; i < 2 * n; i++)
cout " ";
cout "\n";
}
if (ans.size() + balance + 2 <= n * 2) { // Kontrol edin, biz yeni açılış parantezini kapatmamızı sağlayacağız
// Şimdi dikkat edin: her sekans için ayrı bir vektör yapmamıza gerek yok
ans.push_back('(');
rec(bakiye + 1);
ans.pop_back(); // Bunu anlamak için özyinelemeye dikkat etmeniz gerekir. Önce vektöre bir parantez ekliyoruz ve ardından tüm bu kodu tekrar çalıştırıyoruz.
// Yani, eğer yapabilirsek tekrar bir parantez ekleyin.
// Ve bu, özyinelemeden ayrılmaya başlayana, yani istenen uzunluğa ulaşana kadar devam edecek.
// Ardından parantezler kaldırılmaya başlayacak. Bunu anlıyorsan - seni tebrik ediyorum, harikasın.
}
if (balance > 0) { // Bir parantezi kapatabilirsek kapatıyoruz.
ans.push_back(')');
rec(bakiye - 1);
ans.pop_back();
}
}
int ana()
{
cin>> N;
tavsiye(0);
dönüş 0;
}
Ve şimdi zorluklar zamanı - birkaç parantez türü için algoritmayı KENDİNİZE yazmanız gerekecek! Muahahahahahahahahahahahaha!
|