Stack ile parantez kontrolü yaparken ifade soldan sağa taranır ve açılan parantezler stack'e eklenir. Kapanan bir parantez geldiğinde stack'in en üstündeki açılış parantezi çıkarılır ve ikisinin eşleşip eşleşmediği kontrol edilir. Tarama boyunca her kapanış doğru parantezle eşleşiyorsa ve sonunda stack boş kalıyorsa ifade dengelidir.
Parantez dengesi stack ile nasıl kontrol edilir?
Stack, son eklenen elemanın önce çıkarıldığı bir veri yapısıdır. Parantez kontrolünde bu sıra önemlidir, çünkü iç içe açılan parantezlerde en son açılan parantezin önce kapanması gerekir. Stack'te son giren eleman önce çıkarılırken queue yapısında ilk giren eleman önce çıkarılır.
({[]}) ifadesini soldan sağa incelerken önce (, ardından { ve [ stack'e eklenir. İlk kapanış karakteri olan ] geldiğinde en üstteki [ çıkarılır ve eşleşme doğrulanır. Ardından }, { ile; son olarak ), ( ile eşleşir. Stack boş kaldığı için ifade dengelidir.
([)] ifadesinde ise önce ( ve [ stack'e eklenir. Sıradaki ) karakteri geldiğinde en üstte [ bulunduğundan eşleşme başarısız olur. Her parantez türünden bir açılış ve bir kapanış bulunmasına rağmen kapanış sırası hatalıdır.
Algoritmanın adımları ve sınır durumları nelerdir?

Algoritma, her kapanış parantezinde stack'in boş olup olmadığını ve varsa en üstteki açılışla eşleşmeyi kontrol eder. Tarama tamamlandığında stack'te eleman kalıp kalmadığına da bakılır.
Algoritmayı kâğıt üzerinde izlemek için boş bir stack çizip ifadeyi soldan sağa şu sırayla kontrol edebilirsin:
- Bir açılış paranteziyle karşılaştığında onu stack'in en üstüne ekle.
- Bir kapanış paranteziyle karşılaştığında önce stack'in boş olup olmadığına bak. Stack boşsa eşleşecek bir açılış bulunmadığı için ifadeyi reddet.
- Stack boş değilse en üstteki açılış parantezini
popile çıkar. Kapanış parantezine karşılık gelmesi gereken açılışı eşleşme sözlüğünden bul ve çıkardığın elemanla karşılaştır. - İki parantez uyuşmuyorsa ifadeyi reddet; uyuşuyorsa taramaya devam et.
- İfadenin sonuna ulaştığında stack boşsa ifadeyi dengeli kabul et. Stack'te açılış parantezi kalmışsa bunların kapanışı eksik olduğundan ifadeyi reddet.
Parantez dışındaki karakterlerin bulunduğu bir ifadeyi incelerken bu karakterleri yok sayabilirsin. Bu yaklaşımla boş bir ifade de stack boş kaldığı için dengeli kabul edilir.
Python listesi stack olarak kullanıldığında, boş liste üzerinde pop() çağırmak IndexError oluşturur. Bu yüzden kapanış parantezini işlerken eleman çıkarmadan önce boşluk kontrolü yapılmalıdır.
Tarama sonundaki kontrolü atlamak da ([ gibi kapanışı eksik bir ifadeyi yanlışlıkla dengeli gösterebilir. Aynı şekilde yalnızca parantez sayılarını karşılaştırmak, ([)] örneğindeki sıralama hatasını yakalayamaz.
Python listesiyle dengeli_mi fonksiyonu nasıl yazılır?

Açılan parantezler stack'e eklenir, kapanan parantez geldiğinde stack'in en üstündeki elemanla eşleştirilir. En üstteki parantez beklenen türle uyuşmuyorsa ya da kapanış parantezi geldiğinde stack boşsa ifade dengeli kabul edilmez.
Python listesi, bu işlem için gerekli append() ve pop() metotlarını sağlar. Fonksiyon ayrıca her karakterden sonra yapılan işlemi ve stack'in o anki kopyasını iz listesine kaydeder. Böylece yalnızca True veya False sonucu değil, algoritmanın nasıl ilerlediği de görülebilir.
def dengeli_mi(ifade):
eslesen = {
")": "(",
"]": "[",
"}": "{"
}
acilanlar = "([{"
stack = []
iz = []
for karakter in ifade:
if karakter in acilanlar:
stack.append(karakter)
islem = karakter + " açıldı, stack'e eklendi"
iz.append((karakter, islem, stack.copy()))
elif karakter in eslesen:
if not stack:
islem = "Stack boş, kapanış eşleştirilemedi"
iz.append((karakter, islem, stack.copy()))
return False, iz
if stack[-1] != eslesen[karakter]:
islem = (
"En üstteki " + stack[-1]
+ " ile " + karakter + " eşleşmedi"
)
iz.append((karakter, islem, stack.copy()))
return False, iz
stack.pop()
islem = karakter + " eşleşti, stack'ten çıkarıldı"
iz.append((karakter, islem, stack.copy()))
sonuc = len(stack) == 0
return sonuc, iz
ifadeler = ["({[]})", "([)]", "([]", "())"]
for ifade in ifadeler:
sonuc, iz = dengeli_mi(ifade)
print(ifade, sonuc)
Fonksiyonun dört çağrıdan ürettiği sonuçlar şöyledir:
({[]}) True
([)] False
([] False
()) False
Python listelerinin stack olarak kullanımıyla ilgili temel sözdizimini ayrıca pekiştirmek için ücretsiz Sıfırdan Temel Python video eğitimi incelenebilir. Bu örnekte listeye yalnızca açılış parantezleri eklenir ve uygun kapanış bulunduğunda en son eklenen eleman çıkarılır. Queue yapısında ise ilk giren eleman önce çıkarılır; bu nedenle çalışma mantığı farklıdır.
Dört ifade üzerinde stack adımları nasıl izlenir?
Aşağıdaki tablo, fonksiyonun iz listesinde tuttuğu karakter, işlem ve stack durumlarının düzenlenmiş hâlidir. ([)] ifadesinde ilk uyuşmazlık üçüncü karakter olan ) geldiğinde görülür. Stack'in en üstünde [ vardır ve ) için beklenen parantez ( olduğu için tarama o noktada durur.
| ifade | işlenen karakter | yapılan işlem | işlem sonrası stack durumu | nihai sonuç |
|---|---|---|---|---|
({[]}) |
( |
Açıldı, stack'e eklendi | ['('] |
True |
{ | Açıldı, stack'e eklendi | ['(', '{'] | ||
[ | Açıldı, stack'e eklendi | ['(', '{', '['] | ||
] | Eşleşti, stack'ten çıkarıldı | ['(', '{'] | ||
} | Eşleşti, stack'ten çıkarıldı | ['('] | ||
) | Eşleşti, stack'ten çıkarıldı | [] | ||
([)] |
( |
Açıldı, stack'e eklendi | ['('] |
False |
[ | Açıldı, stack'e eklendi | ['(', '['] | ||
) | En üstteki [ ile eşleşmedi | ['(', '['] | ||
([] |
( |
Açıldı, stack'e eklendi | ['('] |
False |
[ | Açıldı, stack'e eklendi | ['(', '['] | ||
] | Eşleşti, stack'ten çıkarıldı | ['('] | ||
()) |
( |
Açıldı, stack'e eklendi | ['('] |
False |
) | Eşleşti, stack'ten çıkarıldı | [] | ||
) | Stack boş, kapanış eşleştirilemedi | [] |
Zaman karmaşıklığı ve kontrol hataları nasıl değerlendirilir?
Algoritma ifadeyi soldan sağa tarar ve her karakteri en fazla bir kez işler. Açılış parantezlerinde append, kapanış parantezlerinde uygunluk kontrolünden sonra pop kullanılır. Bu işlemler tarama sırasında yapıldığı için n karakter uzunluğundaki bir ifadede zaman karmaşıklığı O(n) olur. Buradaki n, ifadenin toplam karakter sayısını ifade eder.
Stack, son eklenen elemanın ilk çıkarıldığı LIFO düzeniyle çalışır. Queue yapısında ise ilk eklenen eleman önce çıkarılır. Parantez kontrolünde en son açılan parantezin önce kapanması gerektiği için stack yapısı bu probleme uygundur.
Uygulama sırasında üç hata özellikle kontrol edilmelidir:
- Boş stack'ten pop yapma: Kapanış parantezi geldiğinde stack boşsa eşleştirilecek bir açılış parantezi yoktur. Bu durumda fonksiyon hemen
Falsedöndürmelidir. - Tarama sonunda stack'te eleman bırakma: İfade tarandığında stack hâlâ eleman içeriyorsa bazı açılış parantezlerinin kapanışı eksik kalmıştır. Bu nedenle yalnızca tarama sırasında hata oluşup oluşmadığına bakmak yeterli değildir.
- Yalnızca parantez sayılarını karşılaştırma: Açılış ve kapanış parantezlerinin sayısı eşit olsa bile sıra hatalı olabilir.
([)]ifadesinde sayılar eşittir, ancak]karakteri en üstteki açılış parantezi olan(ile eşleşmez.
Bu nedenle kendi testlerinde dengeli bir ifade olan ({[]}) ile birlikte yanlış sıralı ([)], eksik kapanışlı ({[] ve fazladan kapanışlı {[]}) örneklerini ayrı ayrı denemek yararlı olur. Böylece algoritmanın hem doğru eşleşmeyi hem de farklı hata türlerini ayırt ettiği görülebilir.
Sık Sorulan Sorular
Kapanış parantezi geldiğinde stack boşsa algoritma ne yapar?
Kapanış parantezi geldiğinde stack boşsa algoritma eşleştirilecek bir açılış parantezi bulamaz ve ifadeyi dengeli kabul etmeyerek False döndürür.
Parantezlerin açılış ve kapanış sayıları eşitse ifade dengeli kabul edilir mi?
Parantezlerin sayılarının eşit olması tek başına yeterli değildir, çünkü her kapanış parantezinin stack'in en üstündeki uygun açılış paranteziyle eşleşmesi gerekir.
Python listesinde append ve pop kullanmak stack işlemlerini nasıl karşılar?
Python listesinin sonuna append ile parantez eklenir, son eleman pop ile çıkarılır ve böylece listenin son bölümü stack'in en üstünü temsil eder.
Dengeli parantez kontrolü algoritmasının zaman karmaşıklığı neden O(n) olur?
Algoritma n karakteri soldan sağa bir kez tarar ve her karakter için sabit sayıda kontrol, append veya pop işlemi gerçekleştirir.
Parantez kontrolünde doğru sonucu almak için hem eşleşme sırasını hem de tarama sonunda stack'in durumunu birlikte değerlendirmek gerekir.