İçeriğe geç

Menü

Berk Akademi
Yorumlar Google yorumları Özel Ders Başvuru Ücretsiz ön görüşme Ana Sayfa

Stack ile Parantez Kontrolü: Dengeli Olup Olmadığı Nasıl Anlaşılır?

stack-ile-parantez-kontrolu
Bu yazıda neler var?
  1. Parantez dengesi stack ile nasıl kontrol edilir?
  2. Algoritmanın adımları ve sınır durumları nelerdir?
  3. Python listesiyle dengeli_mi fonksiyonu nasıl yazılır?
  4. Dört ifade üzerinde stack adımları nasıl izlenir?
  5. Zaman karmaşıklığı ve kontrol hataları nasıl değerlendirilir?
  6. Sık Sorulan Sorular

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?

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:

  1. Bir açılış paranteziyle karşılaştığında onu stack'in en üstüne ekle.
  2. 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.
  3. Stack boş değilse en üstteki açılış parantezini pop ile çı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.
  4. İki parantez uyuşmuyorsa ifadeyi reddet; uyuşuyorsa taramaya devam et.
  5. İ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?

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 False dö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.

Bu içerik aradığın cevabı verdi mi?
Yanıtın, hangi yazıları geliştirmemiz gerektiğini anlamamıza yardımcı olur.
Bu içeriğin üretilmesinde yapay zeka araçlarından destek alınmıştır.

Bu konudan sonra ne okuyabilirsin?

Tüm yazılar

İlgili Eğitimler

Berk Keskin, yazılım geliştirici ve eğitmen
Yazar

Berk Keskin Kimdir?

Yazılıma 12 yaşında başladı; İzmir Ekonomi Üniversitesi'ni bölüm birincisi ve yüksek şeref öğrencisi olarak tamamladı. Bugün yalnızca eğitim vermekle kalmıyor, sektörde aktif olarak yazılım projeleri geliştiriyor ve gerçek dünya deneyimini birebir derslerine taşıyor. Ezberden uzak, mühendislik zihniyetini merkeze alan sürdürülebilir öğrenme sistemleri tasarlayarak sorgulayan, üreten ve problem çözebilen yeni nesil yazılımcılar yetiştiriyor.

Sektörel Deneyim & Projeler

  • Ticarify Entegrasyon Yazılım logosu CEO Ticarify Entegrasyon YazılımPazaryerleri ve e-ticaret sitelerine otomatik e-fatura kesimi, sipariş ve kargo takibi hizmetleri sunan e-Dönüşüm platformunun API mimarisini ve yazılım ekibini yönetmektedir.
  • Benim Düğünüm logosu CEO Benim DüğünümDijital etkinlik ve anı paylaşım platformu.
  • Siberdizayn logosu Yazılım Ekibi Lideri SiberdizaynYüksek anlık oyuncu trafiğine sahip oyun kontrol panelleri ve sunucu altyapıları geliştiren yazılım ekibine liderlik etmektedir.
  • MEDYOGRAFYA 360° Dijital Çözümler logosu Dijital Strateji Lideri MEDYOGRAFYA 360° Dijital ÇözümlerŞirketlerin dijital çözümlerde uzun vadede nasıl ilerleyeceğini planlamasına ve dijital dönüşüm süreçlerini yönetmesine destek olmaktadır.
  • İzmir Ekonomi Üniversitesi logosu Danışma Kurulu Üyesi İzmir Ekonomi ÜniversitesiMezun olduğu üniversitesinde, Bilgisayar Programcılığı bölümünün akademik müfredatını güncel sektör ihtiyaçlarına göre şekillendirmek adına Danışma Kurulu'nda görev almaktadır.
WhatsApp Hemen Ara