Bölüm 8: Yığın ve Kuyruk Uygulamaları

8.1Yığın ve geri izleme

Bu notun bütün yordamları tek bir yapının üzerine kurulur. Bu yüzden önce yığını kısaca hatırlayalım. Yığın (stack), öğelerin yalnız bir uçtan eklenip yine aynı uçtan çıkarıldığı doğrusal bir yapıdır. Bu uca üst (top) denir. Ekleme işlemi “üste koymak” (push), çıkarma işlemi “üstten almak” (pop) diye adlandırılır. En son konan öğe ilk çıkar. Bu kurala son giren ilk çıkar (last in, first out, LIFO) denir.

Dizi ile gerçeklemede iki sınır durumu vardır. Dizi doluyken yeni öğe konamaz; buna taşma (overflow) denir. Boş yığından öğe alınamaz; buna da alttan taşma (underflow) denir. Bu notun kısa kodları çoğu yerde bu denetimleri yazmaz. Örneğin eval yordamı iyi kurulmuş bir ifadede yığının hiç boşalmayacağını varsayar. Doğrulama programlarında kullanılan yigit_ekle ve yigit_al fonksiyonları ise her iki durumu da denetler. Gerçek bir programda bu denetimler atlanmamalıdır.

Yığının “son giren ilk çıkar” davranışı bir problem türüne doğal olarak uyar. Bir dizi karar verilerek ilerlenen ve bazen yanlış bir kararın geri alınması gereken her problemde en son verilen karar ilk geri alınır. Örneğin bir labirentte ilerlerken her yol ayrımında bir yön seçilir. Seçilen yol çıkmaza çıkarsa en yakın, yani en son geçilen yol ayrımına dönülür ve orada başka bir yön denenir. Bu yöntemin adı geri izlemedir (backtracking).

Geri izleme özyinelemeyle de yazılabilir. O durumda yığını programcı kurmaz; her özyinelemeli çağrı çağrı yığınına (call stack) bir çerçeve ekler ve çağrının dönmesi geri adımı oluşturur. Labirent yordamı ise yığını açıkça, bir dizi olarak kurar. Böylece her an yığında ne olduğu görülebilir ve izlenebilir. Bu, yığının geri izlemedeki rolünü anlamak için en iyi yoldur.

8.2Labirent problemi

Labirent problemi, yığınla geri izlemenin klasik örneğidir. Bir giriş, bir çıkış ve aralarında duvarlarla bölünmüş geçitler vardır. Girişten çıkışa giden bir yol aranır. Problem basit görünür, ama ayrıntıları öğreticidir. Yönler nasıl kodlanacak, aynı hücreye iki kez girmek nasıl önlenecek, geri dönüşte nereden devam edilecek? Bu soruların cevapları veri yapısı seçiminin önemini gösterir.

8.2.1Labirentin matrisle gösterimi

Labirent iki boyutlu bir tamsayı matrisiyle gösterilir. Matrisin her hücresi labirentin bir karesidir. 0 değeri açık yolu, 1 değeri duvarı simgeler. Şekil 8.1 notta kullanılan labirenti gösterir. Gri kareler duvar, beyaz kareler açık yoldur. Giriş [1][1] hücresidir ve G harfiyle, çıkış [6][6] hücresidir ve Ç harfiyle işaretlenmiştir. Labirentin boyutu m × p ile anılır: m satır, p sütun. Burada iç kısım 6 × 6'dır.

Şekildeki matris 8 × 8'dir, oysa labirentin kendisi 6 × 6'dır. Fazladan iki satır ve iki sütun bilinçli bir hiledir. Matrisin çevresi baştan sona 1 ile, yani duvarla çevrilir. Bunun nedeni şudur. Kenardaki bir hücreden, örneğin [1][1]'den kuzeye bakıldığında [0][1] hücresine gidilir. Çerçeve olmasaydı bu hücre matrisin dışında kalırdı: 6 × 6'lık bir dizide [-1][0] gibi geçersiz bir indis oluşurdu. C, dizi sınırını denetlemez. Dizi dışına okuma tanımsız davranıştır; program ya çöker ya da rastgele bir bellek değerini duvar ya da yol sanar.

Çerçeve olmadan her adımda “matrisin dışına çıkıyor muyum?” diye dört koşul denetlemek gerekirdi. Çerçeve bu denetimi gereksiz kılar. Dış halkadaki her hücre duvardır ve duvara asla girilmez. Bu yüzden algoritma iç kısımdan hiçbir zaman dışarı adım atmaz ve her komşu indisi geçerli kalır. Kenar durumlarını ortadan kaldıran bu tür ek hücrelere genel olarak bekçi (sentinel) denir. Bedeli çok küçüktür: (m + 2)(p + 2) hücrelik bir matris.

Hareket serbestliği de problemin bir parçasıdır. Bu labirentte yatay ve dikey hareketin yanında çapraz hareket de serbesttir. Bir hücreden sekiz komşusuna gidilebilir. Çapraz hareket, labirentteki dar köşeleri aşmayı sağlar. Örneğin [2][1]'den [3][2]'ye ancak çapraz bir adımla geçilebilir, çünkü aradaki [3][1] ve [2][2] duvardır.

Algoritmanın iki ihtiyacı daha vardır. Birincisi, aynı hücreye ikinci kez girilmemelidir. Aksi hâlde iki hücre arasında sonsuza kadar gidip gelinebilir. Bu yüzden ziyaret edilen hücreler ayrı bir gezildi matrisinde işaretlenir. İkincisi, çıkmaza girilince son yol ayrımına geri dönülmelidir. Son geçilen ayrım ilk dönülecek yerdir; bu da yığının tam tanımıdır.

8.2.2Sekiz yön ve hareket tablosu

Sekiz yön 0'dan 7'ye numaralanır. Yön 0 kuzeydir; numaralar saat yönünde artar. Yön 1 kuzeydoğu, 2 doğu, 3 güneydoğu, 4 güney, 5 güneybatı, 6 batı ve 7 kuzeybatıdır. Şekil 8.2 bir hücrenin sekiz komşusunu ve her komşunun indisini gösterir.

Bir yöne gitmek, satır ve sütun indisine birer küçük sayı eklemek demektir. Kuzeye gitmek satırı bir azaltır, sütunu değiştirmez: (−1, 0). Güneydoğuya gitmek ikisini de bir artırır: (+1, +1). Bu sekiz çift Tablo 8.1'de toplanmıştır.

Bu tabloya arama tablosu (look-up table) denir. Değeri her seferinde koşullarla hesaplamak yerine önceden hesaplanmış bir diziden okumak anlamına gelir. Tablo olmasaydı sekiz ayrı if yazılırdı: “yön 0 ise satırı bir azalt, yön 1 ise satırı azalt ve sütunu artır…” Tablo bu sekiz dalı tek bir satıra indirir:

y_satir = satir + hareket[yon].dikey;
y_sutun = sutun + hareket[yon].yatay;

Bu sayede yön sıradan bir döngü değişkenine dönüşür. Sekiz yönü denemek için yon'u 0'dan 7'ye kadar artırmak yeter. Yönlerin deneme sırasını değiştirmek de kolaylaşır: yalnız tablonun satırlarının sırası değişir, kod aynı kalır.

8.2.3Veri tanımları

Yordamın kullandığı bütün sabitler, tipler ve küresel değişkenler sunumdaki şu bildirimlerde toplanmıştır:

#define MAX_STACK_SIZE 100
#define CIKIS_SATIR 6
#define CIKIS_SUTUN 6
typedef struct { short int dikey, yatay; } yonler;
yonler hareket[8] = {{-1, 0}, {-1, 1}, {0, 1}, {1, 1},
                     {1, 0}, {1, -1}, {0, -1}, {-1, -1}};
typedef struct { short int satir, sutun, yon; } element;
element yigit[MAX_STACK_SIZE];
int top = -1;
short int gezildi[8][8];
short int labirent[8][8] = {{1,1,1,1,1,1,1,1},
    {1,0,1,0,0,0,1,1}, {1,0,1,0,1,1,1,1},
    {1,1,0,1,1,1,1,1}, {1,0,1,1,0,1,1,1},
    {1,1,0,0,1,0,1,1}, {1,1,1,1,1,1,0,1},
    {1,1,1,1,1,1,1,1}};

• MAX_STACK_SIZE yığın dizisinin boyudur. CIKIS_SATIR ve CIKIS_SUTUN çıkış hücresinin koordinatlarıdır.
• yonler yapısı bir yönün iki bileşenini tutar. hareket[8] dizisi Tablo 8.1'deki tablonun kendisidir; ilk çift {-1, 0} yön 0'a (kuzey) karşılık gelir. Değerler küçük olduğu için short int yeterlidir.
• element, yığına konan kayıttır. Üç alanı vardır: bir hücrenin satırı, sütunu ve o hücreye geri dönülürse denemeye hangi yönden devam edileceği (yon). Bu üçüncü alan çok önemlidir. Yığında yalnız konum tutulsaydı, geri dönüşte o hücrenin yönleri yeniden 0'dan denenirdi. Yön alanı “bu hücrede şu yöne kadar baktım” bilgisini saklar.
• yigit dizisi yığının kendisidir; top = -1 yığının boş olduğunu belirtir.
• gezildi ziyaret edilen hücreleri işaretler. Küresel bir dizi olduğu için C onu program başlarken sıfırla doldurur; ayrıca ilk değer vermeye gerek yoktur. Yerel bir dizi olsaydı içeriği belirsiz olurdu.
• labirent çevresi 1 ile çevrili 8 × 8 matristir. Her iç küme parantezi bir satırdır; ilk satır tümüyle 1'dir.

Yığının en fazla kaç öğe tutacağı da önceden kestirilebilir. Bir hücre yığına ancak o hücreden yeni ve ziyaret edilmemiş bir hücreye geçilirken konur. Her açık hücre en çok bir kez ziyaret edildiğine göre, yığındaki öğe sayısı açık hücre sayısını aşamaz. Bu labirentin iç kısmında 13 açık hücre vardır (doğrulama programı da 13 saydı). MAX_STACK_SIZE değeri olan 100 bu labirent için fazlasıyla yeterlidir. Genel bir m × p labirent için güvenli üst sınır m · p'dir.

8.2.4izbul yordamı

Yol bulma yordamının adı izbul'dur. Sunum kodu okunur kalsın diye iki parçada verir; aşağıda iki parça art arda gelir:

void izbul(void) {
  short int satir, sutun, y_satir, y_sutun;
  int i, yon, bulundu = FALSE;
  element konum;
  yigit[0].satir = yigit[0].sutun = 1;
  yigit[0].yon = 1;     /* ilk konum yığına */
  gezildi[1][1] = 1;  top = 0;
  while (top > -1 && !bulundu) {
    konum = yigit_al(&top);   /* yeni konum */
    satir = konum.satir;
    sutun = konum.sutun;
    yon = konum.yon;          /* hangi yöne */
    while (yon < 8 && !bulundu) {
      y_satir = satir + hareket[yon].dikey;
      y_sutun = sutun + hareket[yon].yatay;

      if (y_satir == CIKIS_SATIR &&
          y_sutun == CIKIS_SUTUN)
        bulundu = TRUE;       /* çıkış mı? */
      else if (!labirent[y_satir][y_sutun] &&
               !gezildi[y_satir][y_sutun]) {
        gezildi[y_satir][y_sutun] = 1;
        konum.satir = satir;  /* nereden */
        konum.sutun = sutun;
        konum.yon = ++yon;    /* dönüşte yön */
        yigit_ekle(&top, konum);
        satir = y_satir;  sutun = y_sutun;
        yon = 0;
      } else ++yon;           /* başka yön */
    }                         /* geri adım */
  }

Kod iki iç içe döngüden oluşur. Dıştaki döngü yığından bir konum alır; içteki döngü o konumdan ilerleyebildiği kadar ilerler. Satır satır bakalım.

• Başlangıçta giriş hücresi (1, 1) yığına konur. Yön alanı 1'dir. Yön 0 kuzeydir ve [0][1] çerçevedeki bir duvardır; denemeye gerek yoktur. Giriş hücresi gezildi matrisinde işaretlenir ve top = 0 olur.
• Dış döngü yığın boş olmadığı ve çıkış bulunmadığı sürece döner. Her turda yığından bir konum alınır. satir, sutun ve yon bu kayıttan okunur. Yani “şu hücredeyim ve şu yönden denemeye başlayacağım”.
• İç döngü yon 8'e ulaşmadığı ve çıkış bulunmadığı sürece döner. Her turda bir komşu hesaplanır: (y_satir, y_sutun).
• Komşu çıkış hücresiyse bulundu doğru olur ve iki döngü de biter.
• Komşu açık yolsa (!labirent[…]) ve daha önce ziyaret edilmemişse (!gezildi[…]) o hücreye geçilir. Önce komşu işaretlenir. Sonra şimdiki hücre yığına konur, ama yön alanına ++yon yazılır. Bu “geri dönersem bir sonraki yönden devam edeyim” demektir. Ardından satir ve sutun yeni hücreye çevrilir ve yon = 0 ile yeni hücrenin bütün yönleri baştan denenir.
• Komşu duvarsa ya da ziyaret edilmişse yalnız ++yon ile bir sonraki yöne geçilir.
• İç döngü yon == 8 ile biterse o hücrenin sekiz yönü de tükenmiştir; hücre bir çıkmazdır. Kod bu durumda hiçbir şey yapmaz. Dış döngü bir sonraki turda yığından son kaydı alır ve böylece bir önceki hücreye geri dönülür. Yorumdaki “geri adım” sözü bu anı anlatır.

Birkaç ayrıntı dikkat ister. Birincisi, çıkış denetimi duvar denetiminden önce yapılır. Bu labirentte çıkış hücresi açıktır ve sıra önemli değildir. Ama çıkış hücresi gezildi matrisinde hiçbir zaman işaretlenmez; görüldüğü anda arama biter. İkincisi, yığına konan kayıt yeni hücre değil, terk edilen hücredir. Yeni hücre satir ve sutun değişkenlerinde durur. Bu yüzden çıkış bulunduğunda tam yol üç parçadan oluşur: yığındaki konumlar (yigit[0]'dan yigit[top]'a), o anda bulunulan hücre ve çıkış hücresi. Sunumun belirttiği gibi yordamın son kısmı bu üç parçayı sırayla yazdırır; çıkış bulunamadıysa “Cikis yolu bulunamadi!” iletisi basılır. Doğrulama programında bu son kısım şöyle tamamlandı:

if (bulundu) {
  printf("satir sutun\n");
  for (i = 0; i <= top; i++)        /* yığındaki yol */
    printf("%2d%5d\n", yigit[i].satir, yigit[i].sutun);
  printf("%2d%5d\n", satir, sutun);      /* son konum */
  printf("%2d%5d\n", CIKIS_SATIR, CIKIS_SUTUN);
} else printf("Cikis yolu bulunamadi!\n");

Üçüncüsü, bulundu, TRUE ve FALSE C99'un bool tipinden önceki bir alışkanlıktır: #define FALSE 0 ve #define TRUE 1 ile tanımlanan tamsayılardır. yigit_ekle ve yigit_al ise yığın gerçeklemesinin bilinen iki fonksiyonudur; top'u adresle alırlar, çünkü onu değiştirirler. Dördüncüsü, konum.yon = ++yon satırı hem kayda yazılacak değeri hesaplar hem de yerel yon'u değiştirir. Hemen ardından yon = 0 yazıldığı için yerel değişikliğin bir etkisi kalmaz; önemli olan kayda yazılan değerdir.

Sunumun adım adım izleme slaytı, iç döngünün değişken adlarını kısaltarak (ys, yy) ve yeni kaydı tek satırda kurarak aynı mantığı daha kısa yazar:

while (top > -1 && !bulundu) {
  konum = yigit_al(&top);
  satir = konum.satir;  sutun = konum.sutun;
  yon = konum.yon;
  while (yon < 8 && !bulundu) {
    ys = satir + hareket[yon].dikey;
    yy = sutun + hareket[yon].yatay;
    if (ys == CIKIS_SATIR && yy == CIKIS_SUTUN)
      bulundu = TRUE;
    else if (!labirent[ys][yy] &&
             !gezildi[ys][yy]) {
      gezildi[ys][yy] = 1;
      konum = (element){satir, sutun, ++yon};
      yigit_ekle(&top, konum);
      satir = ys;  sutun = yy;  yon = 0;
    } else ++yon;
} }

Buradaki (element){satir, sutun, ++yon} ifadesi C99'la gelen bileşik değişmezdir (compound literal). Adı olmayan geçici bir element nesnesi kurar ve alanlarını sırayla doldurur. Üç ayrı atamanın yaptığı işi tek satırda yapar. Bu sürüm de doğrulama programında ayrı olarak çalıştırıldı ve aynı yığın hareketlerini üretti.

8.2.5Kod izleme: yığınla geri izleme

Yordamı Şekil 8.1'deki labirent üzerinde çalıştıralım. Her adımda yığının içeriği satir,sutun,yon üçlüleriyle, alttan üste doğru yazılır. Tablo 8.2 yığın işlemlerini sırasıyla verir; satırlar doğrulama programının ürettiği çıktıyla birebir aynıdır.

İlk adımlar düz ilerler. (1,1)'de yön 1, 2 ve 3 duvara çıkar; yön 4 (güney) (2,1)'e açılır. Bu geçişte (1,1) yön 5 ile yığına konur: geri dönülürse güneybatıdan aramaya devam edilecektir. (2,1)'den güneydoğuya, oradan kuzeydoğuya, oradan kuzeye çıkılır. Algoritma (1,3), (1,4) ve (1,5) hücreleriyle labirentin üst kenarındaki koridora girer.

(1,5) bir çıkmazdır. Sekiz komşusunun yedisi duvar, biri ((1,4)) ziyaret edilmiştir. İç döngü yon == 8 ile biter ve dış döngü yığından (1,4, yön 3)'ü alır. Bu, bir adım geri gitmektir. (1,4)'te yön 3'ten itibaren kalan yönler denenir: güneydoğu (2,5) ve güney (2,4) duvardır, güneybatı (2,3) ve batı (1,3) ziyaret edilmiştir, kuzeybatı duvardır. Hiçbir yön açılmaz; yeniden geri gidilir. Aynı durum (1,3) ve (2,3) için de tekrarlanır. Dört geri adımdan sonra (3,2)'ye varılır ve yön 2'den aramaya devam edilir.

Burada yön alanının değeri ortaya çıkar. (3,2)'de yön 0 ve yön 1 daha önce denenmiştir; yön 1 zaten çıkmaz koridora götürmüştü. Kayıttaki 2 değeri bu iki yönün tekrar denenmesini önler. Yön 2, 3 ve 4 duvardır; yön 5 (güneybatı) (4,1)'e açılır. Buradan sonra yol çıkışa doğru tek bir koridorla ilerler: (4,1) → (5,2) → (5,3) → (4,4) → (5,5). (5,5)'te yön 3 (güneydoğu) çıkış hücresine denk gelir ve arama biter.

Bulunan yol şudur: (1,1), (2,1), (3,2), (4,1), (5,2), (5,3), (4,4), (5,5), (6,6). Toplam 9 hücredir. İlk yedisi yığından okunur (top = 6, yani 7 kayıt), sekizincisi o anki konum, dokuzuncusu çıkıştır. Algoritma boyunca 11 kez üste koyma, 5 kez üstten alma yapıldı. Yığın en çok 7 kayda ulaştı. Çıkmaz koridordaki dört hücre ((2,3), (1,3), (1,4), (1,5)) ziyaret edildi ama yolda yer almadı. Çıkış dışında 12 açık hücrenin hepsi gezildi.

8.2.6En kötü durum

Labirent programı bir kaba kuvvet (brute force) aramasıdır. Hiçbir zekâ kullanmaz: çıkışın hangi yönde olduğuna bakmaz, yönleri hep aynı sırayla dener. Sekizli arama tablosu kodu kısaltmış ve işi kolaylaştırmıştır, ama aramanın kendisi körüdür. Böyle bir algoritmanın ne kadar iş yapacağı büyük ölçüde girdiye bağlıdır. Bazı labirentlerde çıkış birkaç adımda bulunur, bazılarında labirentin neredeyse tamamı gezilir.

Bir algoritmanın en kötü durum maliyetini söylemek için yalnız bir üst sınır hesaplamak yetmez; o sınıra gerçekten ulaşan bir girdinin var olduğunu da göstermek gerekir. Bu girdiye en kötü veri grubu denir. Labirentte en kötü veri grubunu belirleyen şey, yönlerin tarama sırasıdır. Algoritma her hücrede önce kuzeye, sonra kuzeydoğuya… bakar. Bu sırayla ilk denenen yol çok uzunsa, algoritma onu sonuna kadar izler.

Şekil 8.4 iki girdiyi karşılaştırır.

• Girdi 1: İlk denenen yol uzundur ama doğrudur; çıkışa götürür. Algoritma bu yolda hiç geri dönmez. Yalnız üste koyma yapılır, üstten alma yapılmaz. İş miktarı yolun uzunluğuyla orantılıdır.
• Girdi 2: İlk denenen yol uzundur ve yanlıştır; bir sarmal gibi labirentin içine kıvrılır ve bir çıkmazda biter. Algoritma bu yolu sonuna kadar gider ve yığın sarmalın her hücresi için bir kayıtla dolar. Çıkmaza varınca yığın bir bir boşaltılır; her geri adımda o hücrenin kalan yönleri de denenir. Ancak sarmalın tamamı tükenince başlangıca dönülür ve kısa doğru yol denenir. Doğru yol dışındaki her yer gezildikten sonra çözüme ulaşılır.

Girdi 2 en kötü veri grubudur: algoritmanın yapabileceği bütün işi yaptırır. Her açık hücre bir kez ziyaret edilir, bir kez yığına konur ve bir kez yığından alınır. Bu analiz bir ilkeyi de gösterir. Bir algoritmayı “yavaş” ya da “hızlı” diye değerlendirmeden önce onun hangi girdide nasıl davrandığı incelenmelidir. Analizi yapılmamış bir algoritma hakkında yargıya varmak doğru olmaz.

8.2.7Karmaşıklık ve kuyrukla karşılaştırma

izbul'un maliyetini sayarak bulalım. Labirentin boyutu m × p olsun.

• Zaman. Bir hücre yığına ancak ondan ziyaret edilmemiş bir hücreye geçilirken konur ve her hücre gezildi sayesinde en çok bir kez ziyaret edilir. Bu yüzden toplam üste koyma sayısı en çok açık hücre sayısı kadardır. Üstten alma sayısı da bunu aşamaz. Her hücrede iç döngü en çok sekiz yön dener; yön alanı sayesinde geri dönüşte daha önce denenmiş yönler tekrar denenmez. Bir hücre için toplam yön denemesi bu yüzden en çok 8'dir, artı her alma için bir tur. Sonuç: O(8 · m · p) = O(m · p). En kötü veri grubunda bu sınıra ulaşılır, yani en kötü durum Θ(m · p)'dir.
• Bellek. Yığın en çok açık hücre sayısı kadar büyür: O(m · p). gezildi matrisi de (m + 2)(p + 2) hücre tutar, yani O(m · p)'dir.

Yığınla yapılan bu arama, derinlik öncelikli aramanın (depth-first search, DFS) bir örneğidir. Bir yöne gidilir ve olabildiğince derine inilir; geri dönüş ancak çıkmazda olur. Bu aramanın önemli bir zayıflığı vardır: bulunan yol en kısa olmak zorunda değildir. Algoritma ilk bulduğu yolu döndürür. O yol, yönlerin deneme sırası yüzünden labirentin uzak bir köşesinden dolanıyor olabilir. Bu labirentte arama (2,3) → (1,3) → (1,4) → (1,5) çıkmazına girip döndü ve 9 hücrelik bir yol buldu.

Yığının yerine kuyruk kullanılırsa aramanın karakteri tümüyle değişir. Kuyruk “ilk giren ilk çıkar” (first in, first out, FIFO) kuralıyla çalışır. Başlangıç hücresi kuyruğa konur. Her adımda kuyruğun önünden bir hücre alınır ve onun ziyaret edilmemiş bütün açık komşuları kuyruğun arkasına eklenir. Böylece hücreler girişe uzaklık sırasıyla açılır: önce uzaklığı 1 olanlar, sonra uzaklığı 2 olanlar… Bu yönteme genişlik öncelikli arama (breadth-first search, BFS) denir.

BFS'nin en kısa yolu neden garanti ettiği kısaca şöyle açıklanır. Kuyrukta hücreler her zaman uzaklıklarına göre sıralıdır: önce uzaklığı d olanların hepsi, sonra uzaklığı d + 1 olanlar. Bir hücreye ilk kez ulaşıldığında ona bir uzaklık yazılır ve hücre bir daha kuyruğa girmez. Uzaklığı d olan bir hücreye daha kısa bir yoldan ulaşılabilseydi, o yolun bir önceki hücresi daha erken kuyruktan çıkardı ve hücreye ondan önce ulaşılırdı. Bu yüzden ilk ulaşma her zaman en kısa yoldandır.

Bu labirentte BFS de 9 hücrelik yolu bulur. Yani burada iki arama aynı uzunlukta yol verdi; doğrulama programındaki BFS bunu 9 hücre olarak hesapladı. Bunun nedeni labirentin dar olmasıdır: çıkışa giden tek bir koridor vardır. Genel durumda DFS'nin bulduğu yol çok daha uzun olabilir. BFS'nin bedeli de vardır: yolu geri kurabilmek için her hücrenin hangi hücreden ulaşıldığını saklamak gerekir. İki aramanın zaman ve bellek maliyeti aynı mertebededir: O(m · p). BFS ile en kısa yolu bulan tam kod alıştırma çözümlerinde verilir.

Bu iki algoritmanın kodlarını ayrıntılı inceleyebilecek kişi en iyi onları yazandır. Bir başkası, kodu adım adım izlemeden onun ne yaptığını tam olarak analiz edemez. Kod izleme tabloları bu yüzden önemlidir: hem yazana kodunu sınama fırsatı verir hem de okuyana kodun davranışını görünür kılar.

8.3İfade gösterimleri

Yığının en eski ve en yaygın uygulamalarından biri aritmetik ve mantıksal ifadelerin değerlendirilmesidir. Bir derleyici x = a / b − c + d * e − a * c satırını okuduğunda, bu ifadeyi hangi sırayla hesaplayacağına karar vermek zorundadır. Bu kesim sorunu tanımlar ve çözümün dayandığı üç gösterimi tanıtır.

8.3.1İfade değerlendirme sorunu

İfade değerlendirme (evaluation of expressions), bir ifadenin değerini işleçlerin önceliğine ve birleşme yönüne uyarak hesaplamaktır. İfade iki tür öğeden oluşur. İşleçler (operator) +, −, *, / gibi yapılacak işlemi belirten simgelerdir. İşlenenler (operand) ise işlemin uygulandığı değerlerdir: a, b gibi değişkenler ya da 4, 2 gibi sabitler. Parantezler de ifadenin bir parçasıdır ve hesaplama sırasını değiştirir.

Sorunun neden zor olduğunu bir örnekle görelim. a = 4, b = 2, c = 2, d = 3, e = 3 olsun. a / b − c + d * e − a * c ifadesi matematikte şöyle okunur: önce bölme ve çarpmalar, sonra soldan sağa toplama ve çıkarmalar. Yani ((4 / 2) − 2) + (3 * 3) − (4 * 2). Bu da 2 − 2 + 9 − 8 = 1 eder. Aynı ifadeyi soldan sağa, önceliğe bakmadan hesaplayan biri ise ((((4/2) − 2) + 3) · 3 − 4) · 2 = 10 bulurdu. Doğru sonuç 1'dir.

İnsan ifadeye bütün olarak bakar ve önce çarpmaları seçer. Bilgisayar ise ifadeyi soldan sağa, karakter karakter okur. Okurken bir işleci gördüğü anda onu uygulayamaz, çünkü sağında daha öncelikli bir işleç olabilir. a + b * c'de + görüldüğünde a + b hesaplanırsa yanlış olur; önce b * c gerekir. Parantezler işi daha da karıştırır: a / (b − c) + d * (e − a) * c ifadesinde parantez içindeki çıkarmalar önce yapılmalıdır.

Derleyicilerin yıllardır kullandığı çözüm iki aşamalıdır:

1. İfade, işleç önceliğini ve parantezleri hesaba katarak sonek gösterime çevrilir. Bu gösterimde parantez ve öncelik kalmaz; işleçler uygulanacakları sırada dizilir.
2. Sonek ifade soldan sağa tek geçişte hesaplanır.

İki aşama da bir yığınla yapılır. Bu yeni bir buluş değildir. Bu problemi pek çok kişi defalarca çözmüştür ve iyi bilinen bir çözümü vardır. Bir problemle karşılaşınca önce bu tür bilinen çözümler araştırılmalı, en hızlı yol bulunmalıdır. Problem gerçekten çözülmemişse keşif ancak o zaman başlar.

8.3.2Öncelik ve birleşme yönü

Bir ifadede hangi işlecin önce uygulanacağını iki kural belirler.

Tablo 8.3 C'nin öncelik tablosunun bu not için gereken kısmını özetler. Satırlar yukarıdan aşağı önceliği azalan sırada verir.

Tablo okunurken önce öncelik, öncelik eşitse birleşme yönü karar verir. Parantez her ikisini de geçersiz kılar: parantez içindeki kısım her zaman önce hesaplanır. İkinci satırdaki tekli işleçler (eksi işareti, mantıksal değil, artırma ve azaltma, içerik ve adres işleçleri) sağdan sola birleşir. Örneğin *p++, *(p++) demektir. Tablo C'nin bütün işleçlerini içermez; kaydırma, bit düzeyi, koşul ve atama işleçleri burada yer almaz.

Bu notun algoritmaları yalnız beş ikili işleçle (+ − * / %) ve parantezle sınırlıdır. Tekli eksi, karşılaştırma ve mantıksal işleçler yöntemi değiştirmez; yalnız öncelik tablosu genişler. Horowitz, Sahni ve Anderson-Freed'in kitabındaki tablo (Şekil 3.12) bu işleçlerin tamamını içerir.

8.3.3Ara ek, önek ve sonek

Bir ifade, işlecin işlenenlere göre yerine bağlı olarak üç biçimde yazılabilir. Gösterimlerin adları İngilizcede yaygın olarak infix, prefix ve postfix diye geçer; sunum başlıklarında ve fonksiyon adlarında (postfix, prefix_eval) bu kısa adlar kullanılır.

“Polonya gösterimi” adı, önek gösterimi 1920'lerde mantık formülleri için öneren Polonyalı mantıkçı Jan Łukasiewicz'den gelir. Sonek gösterim onun ters çevrilmiş biçimidir. Ters Polonya gösterimi bir zamanlar bazı hesap makinelerinde de kullanılırdı: kullanıcı önce iki sayıyı girer, sonra işlem tuşuna basardı.

Tablo 8.4 dört ifadenin üç gösterimdeki karşılığını verir. Tablodaki her satır doğrulama programındaki postfix ve prefix fonksiyonlarıyla üretildi.

Tablonun ikinci satırı önceliğin sonek gösterimde nasıl kaybolduğunu gösterir. 2+3*4'te çarpma önce yapılmalıdır. Sonek karşılığı 234*+'dır. Soldan okuyan biri önce 2, 3 ve 4'ü görür, sonra * işlecini görür ve onu en son iki sayıya, yani 3 ile 4'e uygular. Ardından +, 2 ile 12'yi toplar. Önceliği bilmeye gerek kalmamıştır: işleçlerin sırası, uygulanma sırasının kendisidir.

Üçüncü satırda parantez kaybolur. (a+b)*c'de toplama önce yapılmalıdır. Sonek karşılığında +, *'dan önce yazılır: ab+c*. Sonek gösterimde parantezin işlevini işleçlerin konumu üstlenir.

Dördüncü satır daha karmaşıktır. b-c+d soldan sağa birleştiği için (b−c)+d'dir ve sonek karşılığı bc-d+ olur. Bölme bunun önüne a'yı ekler: abc-d+/. Sonra (e-a) ile çarpılır (ea-*) ve en son c ile çarpılır (c*). İki çarpma soldan sağa birleştiği için önce soldaki yapılır.

8.3.4Elle çevirme

Ara ek bir ifadeyi elle sonek gösterime çevirmenin üç adımlı basit bir yolu vardır. Tablo 8.5 bu adımları a / b − c + d * e − a * c ifadesine uygular.

1. Tam parantezleme. Öncelik ve birleşme yönüne göre her işlem kendi parantezine alınır (Örnek 8.1). Her işlecin tam bir parantez çifti olur.
2. Taşıma. Her işleç kendi parantez çiftinin sağ kapanışına taşınır. (a / b) çifti (a b /) olur.
3. Silme. Parantezler silinir. Kalan dizi sonek ifadedir: a b / c − d e * + a c * −.

Önek gösterim için ikinci adımda işleç sağ kapanışa değil, kendi çiftinin sol açılışına taşınır. Aynı ifadenin önek karşılığı − + − / a b c * d e * a c'dir.

Çevirinin sonucunda önemli bir gözlem yatar: işlenenlerin sırası değişmez. Ara ek ifadede işlenenler a b c d e a c sırasındadır; sonek ifadede de aynı sıradadır. Yalnız işleçlerin yeri değişir. Bu gözlem yığınlı algoritmanın temelidir. İşlenen geldiği anda doğrudan çıktıya yazılabilir. İşleçler ise uygun an gelene kadar, yani kendilerinden sonra gelen ve daha öncelikli olan işlemler bitene kadar bir yığında bekler.

8.3.5Sonekten ara eke yığınla

Ters yöndeki çeviri, yani sonek ifadeden tam parantezli ara ek ifade elde etmek, yığının nasıl çalıştığını görmek için iyi bir başlangıçtır. Kural kısadır. İfade soldan sağa okunur:

• İşlenen gelirse yığına konur.
• İşleç gelirse yığından iki öğe alınır. İlk alınan sağ işlenen, ikinci alınan sol işlenendir. İkisi, araya işleç konarak ve bir parantez çiftine alınarak birleştirilir. Oluşan dizgi yığına geri konur.
• İfade bitince yığında tek bir öğe kalır: tam parantezli ara ek ifade.

Sunumdaki örnek 42/2−33*+42*− ifadesidir. Bu, a / b − c + d * e − a * c ifadesine a = 4, b = 2, c = 2, d = 3, e = 3 değerleri konarak elde edilen sonek ifadedir. Tablo 8.6 her adımdan sonra yığını verir.

İki * adımında yığının durumu ilgi çekicidir. İlk * işlendikten sonra yığında iki öğe vardır: ((4/2)−2) ve (3*3). Yani [1] hücresi boş kalmaz; orada (3*3) durur ve top = 1'dir. İkinci *'dan sonra da aynı hücrede bu kez (4*2) durur. Yığın hiçbir anda üç öğeyi geçmez. Bu ifadede en derin an 3 3 ya da 4 2 çiftinin yığına konduğu andır.

Bu yöntem C'de yazılırken yığında karakter değil, dizgi tutulur. Her birleştirme yeni bir dizgi için bellek ayırmayı ve artık gereksiz olan iki parçayı serbest bırakmayı gerektirir. Bu yüzden malloc ve free'nin dikkatli kullanılması gerekir. Tam kod alıştırma çözümlerinde verilir.

8.4Sonek ifadeyi hesaplama

Sonek ifadenin hesaplanması, iki aşamalı çözümün ikinci aşamasıdır ama anlaşılması en kolay olanıdır. Bu yüzden önce onu inceleyelim. Kural, sonekten ara eke çevirmedeki kuralın neredeyse aynısıdır. Tek fark, yığında dizgiler yerine sayıların durmasıdır.

• İşlenen gelirse değeri yığına konur.
• İşleç gelirse yığından iki değer alınır, işlem yapılır ve sonuç yığına konur.
• İfade bitince yığında kalan tek değer sonuçtur.

8.4.1Söz dizim birimi: token_al

Hesaplayıcı ifadeyi karakter karakter okur. Her okumada bir söz dizim birimi (token) elde edilir. Söz dizim birimi, bir ifadenin anlam taşıyan en küçük parçasıdır: bir işleç, bir parantez, bir işlenen ya da ifadenin sonu. Gerçek derleyicilerde bir birim birden çok karakterden oluşabilir; 123 ya da toplam tek bir birimdir. Bu notta işi sade tutmak için her işlenenin tek basamaklı bir sayı olduğu varsayılır. Böylece her karakter bir birimdir.

typedef enum { sol_paran, sag_paran, arti, eksi,
    carpma, bolme, mod, eos, operand } oncelik;

oncelik token_al(const char *expr, char *sembol, int *n) {
    *sembol = expr[(*n)++];
    switch (*sembol) {
        case '(':  return sol_paran;
        case ')':  return sag_paran;
        case '+':  return arti;
        case '-':  return eksi;
        case '/':  return bolme;
        case '*':  return carpma;
        case '%':  return mod;
        case '\0': return eos;
        default:   return operand;
    }
}

Kodun ilk kısmı bir sayım tipi (enumeration, enum) tanımlar. typedef enum { … } oncelik; bildirimi dokuz adlandırılmış tamsayı sabiti üretir: sol_paran 0, sag_paran 1, arti 2 … operand 8. Bu sabitler birimin türünü etiketler. Kodun geri kalanında '+' karakteri yerine arti gibi okunur bir ad kullanılır. typedef enum ile etiketleme yapmak kodu kolaylaştırır: hem okunurluk artar hem de derleyici, bir switch içinde unutulan etiketler için uyarı verebilir.

token_al fonksiyonu üç parametre alır. expr hesaplanan ifadedir. sembol, okunan karakterin yazılacağı yerin adresidir; böylece fonksiyon hem birimin türünü döndürür hem de karakterin kendisini çağırana iletir. n ise ifadede o anda okunan konumun adresidir. *sembol = expr[(*n)++] satırı n'nin gösterdiği konumdaki karakteri okur ve konumu bir ilerletir. Sonraki çağrı bir sonraki karakteri okur. Ardından switch karakterin türünü belirler. İşleç ve parantez karakterleri kendi etiketlerini, '\0' ifadenin sonunu (eos, end of string), geri kalan her şey operand etiketini döndürür.

Doğrulama programı "(7%3)" ifadesini birim birim okuttu ve sırasıyla sol_paran (0), operand (8), mod (6), operand (8), sag_paran (1) ve eos (7) türlerini aldı.

İşlenen bir karakterdir; hesap için onu sayıya çevirmek gerekir. Bunun yolu sembol − '0' ifadesidir. C'de bir karakter, aslında kodunu tutan küçük bir tamsayıdır. ASCII tablosunda rakamlar art arda dizilir: '0''ın kodu 48, '1''inki 49, '2''ninki 50'dir. Bu yüzden '2' − '0' işlemi 50 − 48 = 2 verir. Bir rakam karakterinden '0' çıkarmak onun sayısal değerini verir.

İfadenin expr adıyla küresel bir dizide tutulması da mümkündü. Horowitz ve arkadaşlarının kitabında böyledir: get_token fonksiyonu yalnız iki parametre alır ve expr'i küresel değişkenden okur. Sunumdaki sürüm ifadeyi parametre olarak alır. Bu küçük fark, bir sonraki kesimde tartışılan “bileşen gibi yazma” ilkesinin ilk adımıdır.

8.4.2eval: küresel sürüm

Sonek ifadeyi hesaplayan yordamın ilk sürümü, kitaptaki gibi küresel bir yığın ve küresel bir ifade kullanır:

float eval(void) {
    char sembol;  oncelik token;
    float op1, op2;
    int n = 0, top = -1;
    token = token_al(expr, &sembol, &n);
    while (token != eos) {
        if (token == operand)
            yigit_ekle(&top, sembol - '0');
        else {
            op2 = yigit_al(&top);   /* önce sağ işlenen */
            op1 = yigit_al(&top);
            yigit_ekle(&top, islem(token, op1, op2));
        }
        token = token_al(expr, &sembol, &n);
    }
    return yigit_al(&top);   /* kalan tek öğe sonuç */
}

İfadenin kendisi (expr) ve yığın dizisi (yigit) küreseldir; top ise yereldir ve yığın fonksiyonlarına adresiyle verilir. Yordamın akışı şöyledir:

• n = 0 ifadenin başını, top = -1 boş yığını gösterir. İlk birim döngüden önce okunur.
• Döngü birim eos olmadığı sürece döner. Her turun sonunda bir sonraki birim okunur. Bu, “önce oku, sonra döngüde işle ve bir sonrakini oku” kalıbıdır.
• Birim işlense, sembol − '0' ile sayısal değeri yığına konur.
• Birim işleçse yığından iki değer alınır. İlk alınan op2'dir, yani sağ işlenen. Sonra sol işlenen op1 alınır. islem fonksiyonu işlemi yapar ve sonuç yığına konur.
• Döngü bitince yığında kalan tek değer döndürülür.

islem fonksiyonu işleç türünü bir switch ile ayırır:

float islem(oncelik token, float op1, float op2) {
    switch (token) {
        case arti:   return op1 + op2;
        case eksi:   return op1 - op2;
        case carpma: return op1 * op2;
        case bolme:  return op1 / op2;
        case mod:    return (int)op1 % (int)op2;
        default:     return 0;   /* işleç değil: buraya gelinmez */
    }
}

İşlenenlerin alınma sırası bu yordamın en önemli ayrıntısıdır. Sonek ifadede sol işlenen yığına önce konur, sağ işlenen sonra. Yığın son konanı ilk verdiği için ilk alınan değer sağ işlenendir. 6 2 − ifadesinde yığına önce 6, sonra 2 konur. − geldiğinde ilk alınan 2'dir (op2), ikinci alınan 6'dır (op1). Sonuç op1 − op2 = 6 − 2 = 4'tür. İşlenenler ters alınsaydı 2 − 6 = −4 bulunurdu. Toplama ve çarpmada sıra sonucu değiştirmez, ama çıkarma, bölme ve kalan işlemlerinde değiştirir.

mod durumundaki (int)op1 % (int)op2 ifadesi bir C kuralından kaynaklanır. Yığın float değer tutar, çünkü bölme sonucu kesirli olabilir. % işleci ise float ile kullanılamaz; yalnız tamsayılar için tanımlıdır. Bu yüzden iki işlenen önce int'e çevrilir. Kesirli değerler için kalanı hesaplamak gerekirse standart kitaplıktaki fmod fonksiyonu kullanılır.

islem'deki default dalı da gereklidir. Sayım tipi üzerinde yapılan bir switch, etiketlerin bir kısmını karşılamazsa derleyici -Wswitch uyarısı verir. Burada sol_paran, sag_paran, eos ve operand bu fonksiyona hiç gelmez; default dalı bunu açıkça belirtir ve uyarıyı giderir.

Bu yordam doğrulama programında küresel expr = "42/2-33*+42*-" ile çalıştırıldı ve 1 değerini döndürdü. Sunumdaki ilk sürümde token_al iki argümanla, token_al(&sembol, &n) biçiminde çağrılıyordu. Bu çağrı, üç parametreli token_al tanımıyla derlenmez (“too few arguments”). Doğru çağrı, küresel expr'i de veren token_al(expr, &sembol, &n)'dir.

8.4.3Bileşen gibi yazmak

Küresel sürüm çalışır, ama ciddi bir tasarım sorunu taşır. Yordam dış dünyaya bağımlıdır:

/* kuresel surum: disa bagimli */
char expr[] = "42/2-33*+42*-";
float yigit[MAX_SIZE];
float eval(void);

eval parametre almaz; hangi ifadeyi hesaplayacağını küresel expr'den, nereye yazacağını küresel yigit'ten öğrenir. Bu bağımlılığın üç sonucu vardır. Birincisi, aynı anda iki ifade hesaplanamaz: ikinci ifadeyi hesaplamak için expr'in içeriğini değiştirmek gerekir. İkincisi, yordam başka bir programa taşınamaz; onu kullanmak isteyen her program aynı adlı küresel değişkenleri tanımlamak zorundadır. Üçüncüsü, yordam yan etkilidir: çalışırken programın başka bir yerinin de kullandığı bir diziyi değiştirir. Programın bir yerindeki hata, bambaşka bir yerde ortaya çıkabilir.

Bileşen gibi yazılmış sürümde her şey parametre ya da yerel değişkendir:

/* bileşen: her şey parametre/yerel */
float eval(const char *expr);
/* yığın eval'in içinde yerel dizi */
/* main içinde: */
float a = eval("23*54*+9-");
float b = eval("42/2-33*+42*-");

İfade parametre olarak gelir; yığın eval'in içinde yerel bir dizidir ve her çağrıda yeniden kurulur. Aynı yordam her yerde, her ifadeyle ve yan etkisiz çalışır. main'deki iki çağrı birbirini hiç etkilemez. Kod izlemelerinde bu sürüm kullanılır.

Bu ilke yalnız bu yordam için değil, yazılan her fonksiyon için geçerlidir. Fonksiyonlar bir bileşen (component) gibi yazılmalıdır: ihtiyaç duyduğu her şeyi parametreyle almalı, sonucunu dönüş değeriyle vermelidir. Küresel değişkenler, fonksiyonun içinden okunan #define sabitleri gibi kullanımlar dışa bağımlılık yaratır. Ekip hâlinde çalışılan bir projede herkes böyle bağımsız parçalar yazar. “Benim değişkenlerimi main'in üstüne koyun, ben böyle çalışıyorum” diyen bir programcının kodu başkalarının koduyla birleştirilemez. Kişiye özgü bir tarz, ortak çalışmanın önünde engeldir.

Bileşen sürümünün tam kodu şudur:

float eval(const char *expr) {
  float y[MAX_SIZE], op1, op2;  int top = -1;
  for (int n = 0; expr[n] != '\0'; n++) {
    char c = expr[n];
    if (isdigit(c)) y[++top] = c - '0';
    else {
      op2 = y[top--];  op1 = y[top--];
      switch (c) {
        case '+': y[++top] = op1 + op2; break;
        case '-': y[++top] = op1 - op2; break;
        case '*': y[++top] = op1 * op2; break;
        case '/': y[++top] = op1 / op2; break;
      }
    }
  }
  return y[top];
}

Kod küresel sürümden daha kısadır. token_al yerine doğrudan for döngüsü ifadenin karakterlerini gezer; döngü '\0' karakterinde durur. isdigit(c) (<ctype.h>) karakterin bir rakam olup olmadığını sınar. Yığın işlemleri fonksiyon çağrısı yerine dizi ifadeleriyle yazılmıştır: y[++top] = … üste koyma, y[top--] üstten almadır. op2 = y[top--]; op1 = y[top--]; satırı yine önce sağ işleneni alır. switch bu kez karakterin kendisi üzerindedir ve dört işleci karşılar. MAX_SIZE yerel yığının boyudur; ifadedeki işlenen sayısından büyük olmalıdır.

8.4.4Kod izleme: eval("23*54*+9-")

İlk örnek 23*54*+9-'dir. Bu, ara ek gösterimde 2*3 + 5*4 − 9 ifadesinin sonek karşılığıdır. Değeri 6 + 20 − 9 = 17 olmalıdır. Tablo 8.7 her karakter işlendikten sonra yığının içeriğini verir.

İzlemede yığının en derin anı n = 4'tür: üç değer (6, 5, 4) aynı anda yığındadır. Bu an, 5*4 çarpımının 2*3 ile toplanmayı beklediği andır. Sonek ifadede bekleyen ara sonuçları yığın saklar.

Maliyet açıktır. İfadenin uzunluğu n olsun. Her karakter bir kez okunur. İşlenen için bir üste koyma, işleç için iki üstten alma, bir işlem ve bir üste koyma yapılır. Bunların her biri O(1)'dir. Toplam süre Θ(n)'dir. Yığın en kötü durumda bütün işlenenleri aynı anda tutar (örneğin 1234+++); ek bellek O(n)'dir.

8.4.5Kod izleme: eval("42/2-33*+42*-")

İkinci örnek, ifade değerlendirme sorununu tanıtan ifadenin sonek karşılığıdır: 42/2-33*+42*-. Beklenen değer 1'dir. Bu ifadenin ara ek karşılığı zaten yığınla bulunmuştu: ((((4/2)−2)+(3*3))−(4*2)). Şimdi aynı yığın, dizgiler yerine sayılarla çalışır.

Bu izleme, ilk karşılaştırmadaki “soldan sağa hesaplayan” yanlış sonucun neden çıkmadığını gösterir. + işleci geldiğinde yığında 0 ve 9 vardır; yani 3*3 çarpımı, toplamadan önce hesaplanmıştır. Önceliği bilen, çeviri aşamasıdır. Hesaplayıcı yalnız işleçleri geldikleri sırayla uygular.

Doğrulama programı bu iki ifadeyi ve alıştırmadaki 623+-382/+* ifadesini hesapladı: sonuçlar 17, 1 ve 7'dir. Programın ara yığın dökümü tablolardaki her satırla aynıdır.

8.4.6Hatalı ifadeler

İyi kurulmuş bir sonek ifadede işlem sonunda yığında tam bir değer kalır. Bu kural bir geçerlilik testi olarak da kullanılabilir. İfade boyunca bir sayaç tutulsun: işlenen sayacı bir artırır, ikili işleç bir azaltır (iki değer alıp bir değer koyar). İfade geçerliyse sayaç hiçbir işleçte 2'nin altına inmeden işlem yapılır ve sonunda tam 1 olur.

• İşlenen eksikse (örneğin 2*), işleç geldiğinde yığında tek değer vardır. Sunumdaki kısa kod y[top--]'yu iki kez çalıştırır ve top −1'e düştükten sonra y[-1]'i okumaya kalkar. Bu, dizi dışına okumadır ve tanımsız davranıştır.
• İşleç eksikse (örneğin 234+), ifade bittiğinde yığında iki değer kalır. Kod üstteki değeri döndürür ve hatayı fark etmez.

Sağlam bir yordam her üstten almadan önce top >= 0 denetimi yapmalı, sonda da top == 0 olduğunu sınamalıdır. Sunumdaki yigit_al fonksiyonu boş yığında hata iletisi vererek bu denetimi üstlenir. Sıfıra bölme de ayrıca ele alınmalıdır: float ile yapılan bölmede sonuç sonsuz ya da NaN (not a number) çıkar, % işleminde ise sıfıra kalan bulmak tanımsız davranıştır.

8.5Ara ekten soneke çevirme

Çözümün birinci aşaması, ara ek ifadeyi sonek gösterime çevirmektir. Elle çevirmede gözlendiği gibi işlenenlerin sırası değişmez; değişen yalnız işleçlerin yeridir. Algoritma bu gözlemi doğrudan kullanır: işlenenler geldikleri anda çıktıya yazılır, işleçler ise bir yığında sıralarını bekler.

8.5.1Algoritma ve isp/icp

Bir işlecin ne zaman çıktıya yazılacağını öncelik belirler. a + b * c'de + yığına girer ve bekler. * geldiğinde + hâlâ yığındadır. * daha öncelikli olduğu için önce uygulanmalıdır, yani çıktıya +'dan önce yazılmalıdır. Bu yüzden *, +'nın üstüne biner. Tersine, a * b + c'de + geldiğinde yığında * vardır. * daha önceliklidir ve artık uygulanabilir; + yığına girmeden önce * çıktıya alınır.

Algoritmanın kuralları şunlardır. İfade soldan sağa okunur.

1. İşlenen doğrudan çıktıya yazılır.
2. İşleç gelince, yığının üstündeki işlecin önceliği gelen işlecin önceliğinden büyük ya da ona eşit olduğu sürece üstteki işleç çıktıya alınır. Sonra gelen işleç yığına konur. Eşitlikte de çıktıya almak, soldan sağa birleşmeyi sağlar.
3. Sol parantez ( her zaman yığına girer. Yığındayken en düşük öncelikli işleç gibi davranır; üstüne her işleç binebilir.
4. Sağ parantez ) gelince ( görülene kadar yığındaki işleçler çıktıya alınır. Sonra ( yığından atılır. Parantezler çıktıya hiç yazılmaz.
5. İfade bitince yığında kalan işleçlerin hepsi çıktıya alınır.

Sol parantezin iki farklı davranışı tek bir öncelik değeriyle ifade edilemez. Gelirken hiçbir işleci yığından çıkarmamalıdır; bu, en yüksek öncelik demektir. Yığındayken ise üstüne her işleç binmelidir; bu da en düşük öncelik demektir. Çözüm, her işlece iki öncelik vermektir.

Tablodaki sayıların kendisi önemli değildir; yalnız aralarındaki sıra önemlidir. Horowitz ve arkadaşları C'nin tam öncelik tablosuna uymak için 12 ve 13 gibi değerler kullanır. ('ın gelen önceliği 20'dir ve hiçbir isp değeri 20'ye ulaşmaz; bu yüzden ( geldiğinde yığından hiçbir şey çıkmaz. Yığın içi önceliği 0'dır ve her işlecin gelen önceliği 0'dan büyüktür; bu yüzden ('ın üstüne her işleç biner. Aynı zamanda hiçbir işleç ('ı yığından çıkaramaz, çünkü 0 ≥ 12 hiçbir zaman doğru değildir. ('ı yalnız ) kaldırır.

Yığının dibindeki # bir bekçidir. Yığın içi önceliği −1'dir; hiçbir işlecin gelen önceliğinden büyük ya da ona eşit değildir. Bu yüzden “üstteki işleci çıktıya al” döngüsü #'a ulaşınca kendiliğinden durur. Böylece döngü koşulunda yığının boş olup olmadığını ayrıca denetlemeye gerek kalmaz. Labirentin çevresindeki duvar çerçevesiyle aynı fikirdir.

Doğrulama programında öncelikler şu iki küçük fonksiyonla tanımlandı:

int isp(char c) {           /* yığındaki öncelik */
  switch (c) {
    case '(': return 0;
    case '*': case '/': case '%': return 13;
    case '+': case '-': return 12;
    default: return -1;     /* '#': yığının dibi */
  }
}
int icp(char c) {           /* gelen öncelik */
  if (c == '(') return 20;
  return isp(c);
}

8.5.2postfix yordamı

void postfix(const char *e, char *cikti) {
  char y[MAX] = {'#'};  int top = 0, k = 0;
  for (; *e; e++) {
    if (isalnum(*e)) cikti[k++] = *e;
    else if (*e == ')') {
      while (y[top] != '(')
        cikti[k++] = y[top--];
      top--;                /* '(' at */
    } else {
      while (isp(y[top]) >= icp(*e))
        cikti[k++] = y[top--];
      y[++top] = *e;
    }
  }
  while (top > 0) cikti[k++] = y[top--];
  cikti[k] = '\0';
}

• y işleç yığınıdır. char y[MAX] = {'#'} bildirimi ilk hücreye # yazar (geri kalan hücreler sıfırlanır). top = 0 dip işaretini gösterir; yani yığın mantıksal olarak boştur ama dipte bekçi vardır. k, çıktı dizgisinde bir sonraki yazılacak konumdur.
• for (; *e; e++) döngüsü işaretçiyi ifadenin sonuna, '\0''a kadar ilerletir. e parametresi bir kopya olduğu için onu ilerletmek çağıranın dizgisini etkilemez.
• isalnum(*e) harf ya da rakam sınar. İşlenen doğrudan cikti'ya yazılır.
• ) gelirse iç döngü yığının üstü ( olana kadar işleçleri çıktıya alır. Sonra top-- ile ( atılır; çıktıya yazılmaz.
• Öteki her karakter (dört işleç, % ve () için “büyük ya da eşit oldukça al” döngüsü çalışır. Ardından gelen karakter yığına konur. ( için döngü hiç dönmez, çünkü icp('(') = 20'dir.
• Döngüden sonra top > 0 olduğu sürece, yani dipteki #'a gelinceye kadar kalan işleçler çıktıya alınır. En son çıktı dizgisi '\0' ile kapatılır.

Fonksiyon sonucu çağıranın verdiği cikti dizisine yazar. Çağıran bu diziyi yeterince büyük ayırmalıdır. Sonek ifade parantez içermediği için hiçbir zaman ara ek ifadeden uzun olmaz; ifade uzunluğu kadar yer artı '\0' yeter.

8.5.3Kod izleme: a*(b+c)-d

Yordamı a*(b+c)-d üzerinde çalıştıralım. Yığının dibinde her zaman # bulunur; tabloda ve şekillerde gösterilmez.

İzlemenin kilit anı )'dır. Parantez içindeki b+c işlemi kapanış parantezi gelene kadar tamamlanamaz; + bu yüzden yığında bekler. ) geldiğinde + çıktıya alınır. Böylece parantez içi, dışarıdaki *'dan önce uygulanacak biçimde çıktıya geçer. Sonuç abc+*d-'dir. Bu ifade “önce b+c, sonra a ile çarp, sonra d'yi çıkar” diye okunur.

8.5.4Eşit öncelik: a*(b+c)*d

İkinci örnek yalnız bir karakterle ayrılır: - yerine *. İzleme )'a kadar aynıdır. Fark, ikinci * geldiğinde ortaya çıkar. Yığının üstünde ilk * vardır ve isp(*) = 13 ≥ icp(*) = 13'tür. Eşitlik de çıktıya almak için yeterlidir. İlk * çıktıya alınır, ikinci * yığına girer. Sonuç abc+*d*'dir.

Eşitlikte çıktıya almanın anlamı, soldan sağa birleşmedir. a*(b+c)*d ifadesi (a*(b+c))*d demektir: önce soldaki çarpma yapılır. Soldaki çarpma çıktıya önce yazılırsa sonek ifadede de önce uygulanır. Çarpma birleşmeli olduğu için burada sonuç değişmez, ama çıkarmada değişir. a-b-c doğru kuralla ab-c-'ye, yani (a−b)−c'ye çevrilir. Eşitlikte almayan bir kod (> kullanan) ise abc-- üretir. Bu a−(b−c) demektir. a = 9, b = 5, c = 2 için doğru sonuç 2, yanlış kodun sonucu 6'dır. Doğrulama programı iki sürümü de çalıştırdı ve bu iki değeri buldu.

8.5.5İzleme tablosu: a+b*c

Sunumdaki son örnek a+b*c'dir. Tablo 8.11 Horowitz ve arkadaşlarının kitabındaki biçimi izler: yığın hücreleri [0] ve [1] ayrı sütunlardır ve dipteki işaret sayılmaz. Bu yüzden tablodaki top değerleri koddaki değişkenden bir eksiktir: kodda y[0] hücresinde # durur, + y[1]'e yazılır.

* geldiğinde yığının üstünde + vardır. isp(+) = 12 < icp(*) = 13 olduğu için + çıktıya alınmaz; * onun üstüne biner. Girdi bitince yığın üstten boşaltılır: önce *, sonra + çıkar. Daha öncelikli işleç önce uygulanır.

Bu tabloda sık sorulan bir soru şudur: “Son işlenen c çıktıya basılmıyor mu?” Basılır. postfix yordamı işlenenleri geldikleri anda çıktıya yazar; c de son satırdan önce çıktıya geçmiştir. Sonda yalnız yığında bekleyen işleçler boşaltılır.

8.5.6Maliyet

İfadenin uzunluğu n olsun. Dış döngü her karakteri bir kez işler. İç döngüler ilk bakışta maliyeti karesel yapacakmış gibi görünür: tek bir ) ya da tek bir işleç, yığındaki birçok öğeyi çıktıya alabilir. Ama her işleç yığına en çok bir kez girer ve en çok bir kez çıkar. Bütün iç döngülerin toplam tur sayısı bu yüzden yığına giren işleç sayısını geçemez, yani n'den küçüktür. Bu tür sayıma toplu analiz (aggregate analysis) denir: tek bir adımın değil, bütün adımların toplam maliyeti hesaplanır. Toplam süre Θ(n)'dir. Yığın ve çıktı dizisi O(n) ek bellek kullanır.

Çeviri ve hesaplama birlikte de doğrusaldır: önce Θ(n)'de sonek ifade üretilir, sonra Θ(n)'de hesaplanır. Derleyiciler bir ifadeyi ayrıştırırken genellikle bu iki adımı birleştirir ya da sonek ifade yerine bir ifade ağacı kurar, ama temel fikir aynıdır.

8.6Önek gösterim

Önek gösterim sonek gösterimin ayna görüntüsüdür. İşleç işlenenlerinden önce gelir. Çevirme ve hesaplama yöntemleri de soneke benzer; fark, ifadenin hangi yönden okunduğundadır.

8.6.1Ara ekten öneke

Ara ek ifadeyi öneke çevirmenin kolay bir yolu, zaten elde olan postfix algoritmasını kullanmaktır. Yöntem dört adımdan oluşur. Tablo 8.12 adımları (a+b)*c-d/a ifadesine uygular.

Yöntemin mantığı şudur. İfade ters çevrilince her işlecin solundaki işlenen sağa, sağındaki sola geçer. Ters çevrilmiş ifadenin soneki bulunduğunda işleç işlenenlerinin sonuna yazılır. Sonuç yeniden ters çevrilince işleç işlenenlerinin önüne geçer; işlenenler de asıl sıralarına döner. Ters çevirme parantezleri de çevirir: (a+b), )b+a( olur. Bu yüzden ikinci adımda parantezler yer değiştirir.

Üçüncü adımda önemli bir değişiklik vardır: eşit öncelikte yığından alınmaz; karşılaştırma > ile yapılır. Ters çevrilmiş ifadede birleşme yönü de ters döner. a-b-c, yani (a−b)−c, ters çevrilince c-b-a olur. Bu ifadenin doğru öneke dönüşmesi için soldaki -'nin yığında kalması, sağdaki -'nin onun üstüne binmesi gerekir. Doğrulama programı bu kuralla a-b-c için --abc'yi, yani −(−(a, b), c)'yi buldu; bu doğru önek karşılığıdır.

Yöntemin C kodu şöyle yazılabilir (aynı isp/icp fonksiyonlarını kullanır):

/* infix -> prefix: ters çevir, parantezleri değiştir,
   eşitlikte almadan (>) postfix'e çevir, yeniden ters çevir */
void prefix(const char *e, char *cikti) {
  char t[MAX], y[MAX] = {'#'};
  int n = strlen(e), top = 0, k = 0;
  for (int i = 0; i < n; i++) {        /* ters çevir */
    char c = e[n - 1 - i];
    t[i] = c == '(' ? ')' : c == ')' ? '(' : c;
  }
  t[n] = '\0';
  for (char *p = t; *p; p++) {
    if (isalnum(*p)) cikti[k++] = *p;
    else if (*p == ')') {
      while (y[top] != '(') cikti[k++] = y[top--];
      top--;
    } else {
      while (isp(y[top]) > icp(*p))    /* > : eşitte alma */
        cikti[k++] = y[top--];
      y[++top] = *p;
    }
  }
  while (top > 0) cikti[k++] = y[top--];
  cikti[k] = '\0';
  for (int i = 0, j = k - 1; i < j; i++, j--) {   /* yeniden ters çevir */
    char g = cikti[i]; cikti[i] = cikti[j]; cikti[j] = g;
  }
}

Sonuç Tablo 8.4'ün üçüncü satırıyla aynıdır. Fonksiyon dört ifadenin hepsinde tablodaki önek karşılığını üretti. Ters çevirmeler, yığın işlemleri ve çeviri ifadenin her karakterine sabit sayıda işlem uygular; toplam süre Θ(n)'dir.

Doğrudan bir yol da vardır. İfade sağdan sola taranır. İşlenenler çıktının başına eklenir; işleçler aynı yığın kuralıyla yönetilir, yine eşitlikte alınmadan. Parantezlerin rolü de yer değiştirir: sağdan sola okurken önce ) görülür ve yığına girer, ( görülünce yığın boşaltılır. İki yol da O(n)'dir.

8.6.2Önek ifadeyi hesaplama

Önek ifade sağdan sola okunarak, sonek hesaplamayla aynı yığın tekniğiyle hesaplanır:

float prefix_eval(const char *e) {
  float y[MAX], op1, op2;  int top = -1;
  for (int i = strlen(e) - 1; i >= 0; i--) {
    if (isdigit(e[i])) y[++top] = e[i] - '0';
    else {
      op1 = y[top--];  op2 = y[top--];
      y[++top] = uygula(e[i], op1, op2);
    }
  }
  return y[top];
}

i son karakterden başlar ve 0'a kadar azalır. Rakam yığına konur. İşleç gelince iki değer alınır ve uygula fonksiyonu işlemi yapar. Bu fonksiyon dört işleci bir switch ile ayırır:

float uygula(char islec, float op1, float op2) {
  switch (islec) {
    case '+': return op1 + op2;
    case '-': return op1 - op2;
    case '*': return op1 * op2;
    case '/': return op1 / op2;
    default:  return 0;
  }
}

Kodun can alıcı farkı alınma sırasıdır. Önek ifadede bir işlecin hemen sağında önce sol işlenen, sonra sağ işlenen yazılır. Sağdan sola okunduğunda sağ işlenen önce görülür ve yığına önce konur. Sol işlenen sonra konur ve üstte durur. Bu yüzden ilk alınan değer sol işlenendir: op1 = y[top--]; op2 = y[top--];. Sonek hesaplamada ise ilk alınan sağ işlenendi.

strlen(e) - 1 ifadesi bir tip ayrıntısı içerir. strlen işaretsiz size_t döndürür. Boş dizgide 0 - 1 işaretsiz aritmetikte çok büyük bir sayıya dönüşür. Kod bu sonucu int i'ye atadığı için uygulamada −1 elde edilir ve döngü hiç dönmez. Döngü değişkeni size_t yapılsaydı i >= 0 koşulu her zaman doğru olurdu ve döngü sonsuza giderdi.

Sunumdaki örnek -+*23*549'dur. Bu, 2*3+5*4−9 ifadesinin önek karşılığıdır; değeri sonek örnekteki gibi 17 olmalıdır.

Son adımda alınma sırası sonucu belirler. Yığında 9 altta, 26 üsttedir. İlk alınan 26 sol işlenendir ve sonuç 26 − 9 = 17 olur. Sonek kuralı burada uygulansaydı 9 − 26 = −17 bulunurdu. Doğrulama programı -62 için 4'ü, *-623 için (6 − 2) · 3 = 12'yi buldu.

8.6.3Öteki çeviriler

Üç gösterim ve hesaplama dört köşeli bir şema oluşturur. Şekil 8.11 bu şemayı verir. Yeşil oklar bu notta kodu verilen yolları, kırmızı soru işaretleri ise tasarlanacak çevirileri gösterir.

Kalan çevirilerin hepsi aynı yığın düşüncesiyle tasarlanabilir:

• Sonekten ara eke: elle yapılan çevirinin C ile yazılması. Yığında dizgiler durur; çözüm alıştırmalarda verilir.
• Sonekten öneke: sonekten ara eke çevirmenin aynısı, yalnız birleştirme op a b biçiminde yapılır. Önekten soneke: ifade sağdan sola okunur, birleştirme a b op biçimindedir.
• Ara ekten öneke doğrudan: ifade sağdan sola taranır (önceki kesimde anlatıldı).
• Önekten ara eke: sağdan sola okunur, ilk alınan sol işlenendir, birleştirme (a op b) biçimindedir.
• Ara ek ifadeyi doğrudan hesaplamak: iki yığın kullanılır, biri işlenenler biri işleçler için. Çeviri algoritması bir işleci çıktıya yazacağı anda, o işleç işlenen yığınından iki değer alıp sonucu geri koyar. Böylece sonek ifade hiç üretilmeden doğrudan değer hesaplanır.

8.7Parantez denetimi

Ara ekten soneke çeviri, ifadedeki parantezlerin doğru kurulduğunu varsayar. Bu varsayım ayrı bir algoritmayla denetlenebilir. Parantez denetimi (balanced parentheses), açılan her parantezin doğru türde ve doğru sırada kapandığını sınar. Problem yığının en temiz uygulamalarından biridir.

Tanımın ortasındaki “en son açılan” ifadesi yığını işaret eder. {a*(b+c)-[d]} dizgisinde (, {'dan sonra açılmıştır ve ondan önce kapanmalıdır. Açanlar bir yığına konursa, kapanan geldiğinde eşi her zaman yığının üstündedir.

8.7.1dengeli yordamı

bool dengeli(const char *e) {
  char y[MAX];  int top = -1;
  for (; *e; e++) {
    if (*e=='(' || *e=='[' || *e=='{')
      y[++top] = *e;
    else if (*e==')' || *e==']' || *e=='}') {
      if (top < 0 || !eslesir(y[top], *e))
        return false;  /* fazla/yanlış */
      top--;
    }
  }
  return top == -1;       /* açık kalmadı mı */
}

• Açan bir parantez ((, [, {) gelirse yığına konur.
• Kapanan bir parantez gelirse iki durum denetlenir. Yığın boşsa (top < 0) bu kapananın eşi yoktur: fazla kapanan. Yığın boş değilse üstteki açanın kapananla eşleşip eşleşmediğine bakılır. Eşleşmiyorsa türler karışmıştır: yanlış eşleşme. İki durumda da fonksiyon hemen false döndürür. Eşleşirse açan yığından atılır (top--).
• Parantez olmayan karakterler atlanır.
• Dizgi bitince yığın boşsa (top == -1) her açan kapanmıştır ve sonuç true olur. Boş değilse kapanmamış açan vardır.

Koşuldaki top < 0 || !eslesir(y[top], *e) ifadesi kısa devre değerlendirmeye dayanır. || işleci önce sol tarafı değerlendirir; sol taraf doğruysa sağ tarafa hiç bakmaz. Yığın boşken y[top], yani y[-1] okunmaz. Koşullar ters sırayla yazılsaydı boş yığında dizi dışına okunurdu. eslesir fonksiyonu sunumda verilmemiştir; doğrulama programında şöyle yazıldı:

bool eslesir(char acan, char kapanan) {
  return (acan == '(' && kapanan == ')') ||
         (acan == '[' && kapanan == ']') ||
         (acan == '{' && kapanan == '}');
}

8.7.2Kod izleme: {a*(b+c)-[d]}

Yığın en çok iki açan tuttu. Bu, iç içe geçmenin derinliğidir: ( ve [ her biri {'nın içinde ama birbirinden bağımsızdır.

8.7.3Üç hata türü

Dengesiz bir dizgi üç farklı biçimde ortaya çıkar. Tablo 8.15 her türden bir örnek verir; üç örnek de doğrulama programında false sonucu verdi.

Tek türde parantez için yığına gerek yoktur; bir sayaç yeter. Açanda sayaç bir artar, kapananda bir azalır. Sayaç hiçbir zaman sıfırın altına inmez ve sonda sıfır olursa dizgi dengelidir. Birden çok parantez türü olduğunda sayaç yetmez. [(a+b]*c) dizgisinde açan ve kapanan sayıları eşittir, ama türler çaprazlanmıştır. Bunu yakalamak için “en son açılan hangisiydi?” sorusunu yanıtlamak gerekir. Bu bilgiyi yığın tutar.

Bu algoritma pek çok yazılımın içinde çalışır. Derleyiciler kaynak koddaki parantez ve küme parantezlerini böyle denetler. HTML ve XML denetleyicileri açılan ve kapanan etiketleri aynı yöntemle eşler; orada yığına parantez değil etiket adı konur. Metin düzenleyicilerin imleç bir parantezin üzerine gelince eşini vurgulaması da bu algoritmanın bir uygulamasıdır.

Maliyet: dizginin uzunluğu n ise her karakter bir kez incelenir ve her işlem O(1)'dir; süre O(n)'dir. En kötü durumda bütün karakterler açandır ve hepsi yığına girer; ek bellek O(n)'dir. Hata erken bulunursa fonksiyon dizginin sonuna gitmeden döner.

8.8Yığın ve kuyruğun başka uygulamaları

Labirent, ifade değerlendirme ve parantez denetimi ortak bir düşünceyi paylaşır: “en son açılan ilk kapanır”. Bu düşünce görülen her yerde yığın kullanılabilir. “Sırayla”, yani “ilk gelen ilk işlenir” görülen yerde ise kuyruk kullanılır. Bu kesim bu ilkenin birkaç başka uygulamasını kısaca tanıtır.

8.8.1Geri al ve yinele

Metin düzenleyicilerdeki geri al (undo) ve yinele (redo) komutları iki yığınla çalışır. Kullanıcı bir işlem yaptığında işlem “geri al” yığınına konur ve “yinele” yığını boşaltılır. Geri al komutu “geri al” yığınının üstündeki işlemi alır, tersini uygular ve onu “yinele” yığınına koyar. Yinele komutu “yinele” yığınının üstündeki işlemi alır, yeniden uygular ve “geri al” yığınına koyar.

Örneğin kullanıcı sırayla A, B ve C işlemlerini yapsın. “Geri al” yığını A · B · C olur. İki kez geri alınırsa önce C, sonra B geri alınır. “Geri al” yığınında A, “yinele” yığınında C · B kalır; B üsttedir. Bir kez yinelenirse B yeniden uygulanır. Bu anda kullanıcı yeni bir D işlemi yaparsa “yinele” yığınındaki C silinir. Yeni bir dal başlamıştır ve eski geleceğe dönülemez. Web tarayıcılarının geri ve ileri düğmeleri de aynı iki yığınla çalışır.

8.8.2Özyinelemesiz ağaç gezinmesi

İkili ağacın düğümlerini sırayla ziyaret etmeye gezinme denir. Gezinme doğal olarak özyinelemeyle yazılır: kök ortada gezinmede önce sol alt ağaç gezilir, sonra kök ziyaret edilir, sonra sağ alt ağaç gezilir. Özyineleme, bekleyen işleri çağrı yığınında saklar. Aynı iş açık bir yığınla da yapılabilir; böylece özyinelemeli çağrıların yükü ortadan kalkar ve yığının boyu programcının denetimine girer.

Kodlar için şu düğüm tipi kullanılır: her düğüm bir karakter ve iki alt ağaç işaretçisi taşır.

typedef struct dugum *dugum_gost;
typedef struct dugum {
  char veri;
  dugum_gost sol, sag;
} dugum;

void kok_ortada(dugum_gost p) {          /* inorder, özyinelemesiz */
  dugum_gost y[MAX];  int top = -1;
  for (;;) {
    for (; p; p = p->sol) y[++top] = p;  /* sola inerken it */
    if (top < 0) break;                  /* yığın boş: bitti */
    p = y[top--];
    printf("%c", p->veri);
    p = p->sag;                          /* sağ alt ağaca geç */
  }
}

void kok_basta(dugum_gost p) {           /* preorder, özyinelemesiz */
  dugum_gost y[MAX];  int top = -1;
  if (p == NULL) return;
  y[++top] = p;
  while (top >= 0) {
    p = y[top--];
    printf("%c", p->veri);
    if (p->sag) y[++top] = p->sag;       /* önce sağ itilir, */
    if (p->sol) y[++top] = p->sol;       /* sol üstte kalır */
  }
}

void kok_sonda(dugum_gost p) {           /* postorder, iki yığınla */
  dugum_gost y1[MAX], y2[MAX];  int t1 = -1, t2 = -1;
  if (p == NULL) return;
  y1[++t1] = p;
  while (t1 >= 0) {
    p = y1[t1--];
    y2[++t2] = p;                        /* kök, sağ, sol sırası */
    if (p->sol) y1[++t1] = p->sol;
    if (p->sag) y1[++t1] = p->sag;
  }
  while (t2 >= 0) printf("%c", y2[t2--]->veri);   /* ters: sol, sağ, kök */
}

kok_ortada fonksiyonu kök ortada (inorder) gezinmeyi yapar. İç for döngüsü p'den başlayıp sol bağları izleyerek aşağı iner ve geçtiği her düğümü yığına koyar. Sol uca varılınca yığının üstündeki düğüm alınır, yazdırılır ve onun sağ alt ağacına geçilir. Yığın boşalınca ve p NULL olunca gezinme biter. Yığında her an kökten şimdiki düğüme giden yol üzerindeki “sağına henüz geçilmemiş” düğümler durur. Bu yüzden yığının boyu ağacın yüksekliğini aşmaz.

kok_basta (preorder) daha basittir. Kök yığına konur. Her turda üstteki düğüm alınır ve yazdırılır; sonra önce sağ, sonra sol çocuğu yığına konur. Sol çocuk üstte kaldığı için önce o işlenir. kok_sonda (postorder) iki yığınla yazılmıştır. Birinci yığın düğümleri “kök, sağ, sol” sırasında ikinci yığına aktarır. İkinci yığın ters sırayla boşaltılınca “sol, sağ, kök” sırası, yani kök sonda gezinme elde edilir.

Doğrulama programı (a+b)*c-d/a ifadesinin ağacını kurdu: kök -, sol alt ağaç (a+b)*c, sağ alt ağaç d/a. Üç gezinme sırasıyla a+b*c-d/a (parantezsiz ara ek), -*+abc/da (önek) ve ab+c*da/- (sonek) çıktılarını verdi. Bir ifade ağacının üç gezinmesi, ifadenin üç gösterimidir. Ağaç kurmak ve bırakmak için yapılan 9 malloc çağrısının hepsine bir free karşılık geldi.

Maliyet: n düğümlü ağaçta her düğüm yığına bir kez girer ve bir kez çıkar; süre O(n)'dir. Kök ortada ve kök önde gezinmede yığın en çok ağacın yüksekliği h kadar düğüm tutar (kök önde için tam sınır h + 1 mertebesindedir); ek bellek O(h)'dir. Dengeli bir ağaçta h = O(log n), tek kola dönmüş bir ağaçta h = n − 1'dir. İki yığınlı kök sonda gezinmede ikinci yığın bütün düğümleri tuttuğu için ek bellek O(n)'dir. Ağacın düzeylerini sırayla dolaşan düzey sıralı gezinme (level-order traversal) ise kuyrukla yapılır: kök kuyruğa konur, her adımda önden bir düğüm alınır ve çocukları arkaya eklenir.

8.8.3Sonraki büyük öğe

Bir dizinin her öğesi için sağındaki ilk büyük öğe bulunmak istensin. İki iç içe döngü bunu O(n²)'de yapar. Yığın aynı işi tek geçişte yapar:

/* her öğenin sağındaki ilk büyük öğe; yoksa -1 */
void sonraki_buyuk(const int a[], int n, int sonuc[]) {
  int y[MAX], top = -1;                  /* yığında indisler */
  for (int i = 0; i < n; i++) {
    while (top >= 0 && a[y[top]] < a[i])
      sonuc[y[top--]] = a[i];            /* a[i], bekleyenin cevabı */
    y[++top] = i;
  }
  while (top >= 0) sonuc[y[top--]] = -1; /* sağında büyük yok */
}

Yığında cevabını henüz bulamamış öğelerin indisleri durur. Bu öğelerin değerleri alttan üste azalan sıradadır; bu yüzden yapıya azalan yığın (monotonic stack) denir. Yeni bir öğe a[i] gelince, üstteki bekleyen öğe ondan küçük olduğu sürece a[i] o öğenin cevabıdır; öğe yığından alınır. Sonra i yığına konur. Dizi bitince yığında kalan öğelerin sağında büyük öğe yoktur; cevapları −1'dir.

Doğrulama programı {4, 5, 2, 25, 7, 3, 8} dizisi için 5 25 25 −1 8 8 −1 sonucunu verdi. Örneğin 25 geldiğinde yığında 5 ve 2'nin indisleri vardır; ikisi de 25'ten küçüktür ve ikisinin cevabı da 25 olur. Her indis yığına bir kez girip bir kez çıktığı için toplam süre O(n)'dir; ek bellek en kötü durumda (azalan dizi) O(n)'dir.

8.8.4Kayan pencere en büyüğü

n öğeli bir dizide k genişlikli bir pencere soldan sağa kaydırılsın ve her konumda penceredeki en büyük öğe istensin. Her pencereyi ayrı taramak O(n · k) sürer. Çift uçlu kuyruk (deque), yani iki ucundan da ekleme ve çıkarma yapılabilen kuyruk, işi O(n)'e indirir:

/* k genişlikli her pencerenin en büyüğü; d: indis tutan deque */
void kayan_maks(const int a[], int n, int k, int sonuc[]) {
  int d[MAX], on = 0, arka = -1;         /* d[on..arka] */
  for (int i = 0; i < n; i++) {
    if (on <= arka && d[on] <= i - k) on++;           /* pencereden çıktı */
    while (on <= arka && a[d[arka]] <= a[i]) arka--;  /* küçükler atılır */
    d[++arka] = i;
    if (i >= k - 1) sonuc[i - k + 1] = a[d[on]];      /* en büyük önde */
  }
}

Çift uçlu kuyrukta indisler durur ve değerleri önden arkaya azalan sıradadır. Yeni öğe gelince önce önden, pencerenin dışına düşmüş indis atılır. Sonra arkadan, yeni öğeden büyük olmayan bütün indisler atılır: bu öğeler yeni öğe pencerede kaldığı sürece hiçbir zaman en büyük olamaz. Yeni indis arkaya eklenir. Penceredeki en büyük öğe her zaman öndedir. {1, 3, −1, −3, 5, 3, 6, 7} dizisi ve k = 3 için sonuç 3 3 5 5 6 7'dir. Her indis bir kez eklenir ve en çok bir kez atılır; süre O(n), ek bellek O(k)'dır.

8.8.5Kuyrukla en kısa yol ve öteki geri izleme problemleri

Labirentte yığının yerine kuyruk kullanılırsa ilk bulunan yol en kısa yoldur. Bu, genişlik öncelikli aramanın temel özelliğidir ve labirentin ötesinde, adımların eşit maliyetli olduğu her ağda geçerlidir. Bir oyunda karakterin en az hamleyle hedefe ulaşması, bir sosyal ağda iki kişi arasındaki en kısa tanışıklık zinciri aynı yöntemle bulunur.

Geri izlemenin öteki klasik örnekleri de yığınla, ya da özyinelemeyle, çözülür. Hanoi kuleleri problemi diskleri bir çubuktan ötekine taşırken bekleyen alt problemleri bir yığında tutar. N-vezir problemi satranç tahtasına birbirini tehdit etmeyen N vezir yerleştirir. Her satıra bir vezir konur; çıkmaza girilirse son konan vezir kaldırılıp bir sonraki sütun denenir. Sudoku çözücüsü boş hücrelere sırayla rakam dener, çelişki çıkınca son denemeyi geri alır. Üçü de labirent yordamının iskeletini taşır: seçim yığına konur, çıkmazda yığından alınır. Bu problemler genellikle özyinelemeyle yazılır ama labirentteki gibi açık bir yığınla da yazılabilir.

8.9Karmaşıklık özeti

Tablo 8.16 notun algoritmalarının maliyetlerini bir arada verir. Her satırın gerekçesi ilgili kesimde açıklandı.

Tablodaki doğrusal sürelerin hepsi aynı gerekçeye dayanır: her öğe yapıya en çok bir kez girer ve en çok bir kez çıkar, her giriş ve çıkış O(1)'dir. İç içe döngüler bu sınırı bozmaz, çünkü iç döngülerin toplam tur sayısı çıkarılan öğe sayısıyla sınırlıdır. Bu sayım yöntemi yığın ve kuyruk algoritmalarını analiz ederken en sık kullanılan araçtır.

8.10Sık yapılan hatalar

1. Sonek hesaplamada op1 ile op2'yi ters almak. İlk alınan sağ işlenendir. Ters alınırsa 6 2 −, 4 yerine −4 olur.
2. Önek hesaplamada sonek sırasını kullanmak. Önek ifade sağdan sola okunur ve ilk alınan sol işlenendir.
3. Ara ekten soneke çevirmede eşit öncelikte yığından almamak. > ile karşılaştıran kod a−b−c'yi abc−−'ye, yani a−(b−c)'ye çevirir.
4. ) gelince ('ı yığında unutmak ya da çıktıya yazmak. ( atılmazsa yığında kalır ve sonraki işleçlerin önünde engel olur; sonda boşaltılırken çıktıya da karışır.
5. Labirentte gezildi işaretini unutmak. Algoritma iki hücre arasında gidip gelir, sonsuz döngüye girer ya da yığını taşırır.
6. Labirentin çevresini 1 ile çevirmemek. Kenardaki hücrelerin komşuları dizi dışına düşer; C bunu denetlemez ve tanımsız davranış oluşur.
7. Parantez denetiminde yığının boş olup olmadığına bakmadan üstteki öğeyi okumak. (a+b))'de ikinci ) boş yığında y[-1]'i okur.
8. Yığın taşmasını denetlememek. Sabit boyutlu dizi yığınında MAX aşılırsa öğeler dizinin dışına yazılır. Ya boyut girdiye göre güvenli seçilmeli ya da her üste koymada denetim yapılmalıdır.

8.11Alıştırmalar ve çözümleri

Sunumdaki altı alıştırmanın çözümleri aşağıda ayrıntılı olarak verilir. Kodların hepsi doğrulama programlarında derlenip çalıştırıldı.

8.11.1Bir ifadeyi soneke ve öneke çevirmek

İfade a/(b-c)+d*(e-a)*c'dir. Önce elle çevirelim. Tam parantezli biçim ((a/(b−c)) + ((d*(e−a))*c))'dir. Bölme ve iki çarpma, toplamadan öncülüdür; iki çarpma soldan sağa birleşir.

• Sonek: her işleç sağ kapanışa taşınır. (b−c) → bc-, a/… → abc-/, (e−a) → ea-, d*… → dea-*, …*c → dea-*c*. Toplam: abc-/dea-*c*+.
• Önek: her işleç sol açılışa taşınır. Sonuç +/a-bc**d-eac'dir.

Aynı sonuç postfix yordamıyla da bulunur. Kısaca: a çıktıya; / yığına; ( yığına; b, c çıktıya, - ('ın üstüne; ) gelince - çıktıya. + gelince isp(/) = 13 ≥ 12 olduğu için / çıktıya, + yığına. d çıktıya; *, +'nın üstüne biner. (e-a) aynı biçimde ea- üretir. İkinci * gelince eşit öncelikteki ilk * çıktıya alınır. c'den sonra girdi biter; yığındaki * ve + sırayla çıktıya geçer. Doğrulama programının postfix ve prefix fonksiyonları da abc-/dea-*c*+ ve +/a-bc**d-eac sonuçlarını verdi.

8.11.2Bir sonek ifadeyi hesaplamak

İfade 6 2 3 + − 3 8 2 / + *'dır. Yığın soldan sağa şöyle değişir: 6; 6 · 2; 6 · 2 · 3; + → 2 + 3 = 5, yığın 6 · 5; − → 6 − 5 = 1, yığın 1; 1 · 3; 1 · 3 · 8; 1 · 3 · 8 · 2; / → 8 / 2 = 4, yığın 1 · 3 · 4; + → 3 + 4 = 7, yığın 1 · 7; * → 1 · 7 = 7. Sonuç 7'dir. Yığın en çok dört değer tuttu. eval("623+-382/+*") de 7 döndürdü.

8.11.3Sonekten ara eke çeviren C yordamı

Yığında artık karakter değil, dinamik olarak ayrılmış dizgiler durur. Yöntem sonekten ara eke elle çevirmenin aynısıdır.

/* postfix -> tam parantezli infix; yığında dinamik dizgiler durur */
char *postfix_infix(const char *e) {
  char *y[MAX];  int top = -1;
  for (; *e; e++) {
    if (isalnum((unsigned char)*e)) {
      char *s = malloc(2);
      if (s == NULL) return NULL;
      s[0] = *e;  s[1] = '\0';
      y[++top] = s;
    } else {
      char *b = y[top--], *a = y[top--];       /* önce sağ işlenen */
      char *s = malloc(strlen(a) + strlen(b) + 4);
      if (s == NULL) return NULL;
      sprintf(s, "(%s%c%s)", a, *e, b);
      free(a);  free(b);                       /* parçalar artık gereksiz */
      y[++top] = s;
    }
  }
  return y[top];             /* çağıran free etmeli */
}

• İşlenen gelince iki baytlık bir dizgi ayrılır: karakterin kendisi ve '\0'. Dizginin adresi yığına konur.
• İşleç gelince iki dizgi alınır; ilk alınan b sağ işlenendir. Yeni dizginin boyu iki parçanın uzunluğu artı dört bayttır: iki parantez, işleç ve '\0'. sprintf parçaları "(a op b)" biçiminde birleştirir.
• Parçalar yeni dizgiye kopyalandıktan sonra artık gereksizdir ve free ile bırakılır. Bu satır unutulursa her işleçte iki blok sızar.
• Dönüş değeri yığındaki son dizgidir. Bu dizgiyi bırakmak çağıranın görevidir.

Doğrulama programı dört ifadeyi çevirdi. 42/2-33*+42*- için ((((4/2)-2)+(3*3))-(4*2)), ab+c*da/- için (((a+b)*c)-(d/a)) elde edildi. malloc ve free çağrılarını sayan sarmalayıcı fonksiyonlarla 44 ayırma ve 44 bırakma sayıldı; sızıntı yoktur. Kodun eksik bir yanı da vardır: malloc başarısız olursa fonksiyon NULL döndürür ama yığında kalan dizgileri bırakmaz. Sağlam bir sürüm dönmeden önce yığını boşaltmalıdır. Maliyet açısından her birleştirme iki parçayı kopyalar; dizgiler uzadıkça kopyalama da uzar. n uzunluklu bir ifadede toplam kopyalama en kötü durumda O(n²)'dir (örneğin ab+c+d+… gibi sola yaslanan bir zincirde her adım bütün önceki dizgiyi kopyalar).

8.11.4Bulunan yolu labirentte işaretlemek

Çıkış bulunduğunda yol, yığındaki konumlar, son konum ve çıkıştan oluşur. Bu hücrelere 2 yazmak yolu labirentte görünür kılar:

/* izbul çıkışı bulduktan sonra çağrılır: yolu labirentte 2 ile işaretler */
void yolu_isaretle(int top, short int satir, short int sutun) {
  for (int i = 0; i <= top; i++)
    labirent[yigit[i].satir][yigit[i].sutun] = 2;
  labirent[satir][sutun] = 2;                  /* son konum */
  labirent[CIKIS_SATIR][CIKIS_SUTUN] = 2;      /* çıkış */
}

izbul'un sonunda if (bulundu) yolu_isaretle(top, satir, sutun); satırıyla çağrılır. Fonksiyon yığını değiştirmez; yalnız okur. Sonuçta labirentin satırları şöyle görünür (1 duvar, 0 gezilmeyen yol, 2 bulunan yol):

11111111
12100011
12101111
11211111
12112111
11221211
11111121
11111111

Çıkmaz koridordaki (1,3), (1,4), (1,5) ve (2,3) hücreleri 0 olarak kalır: ziyaret edildiler ama yola girmediler. İşaretleme O(top), yani yol uzunluğunda süre alır.

8.11.5Labirentte en kısa yolu kuyrukla bulmak

Kuyruğa hücrelerin (satir, sutun) çiftleri konur. Her hücre için hangi hücreden ulaşıldığı once matrisinde saklanır. Çıkışa ulaşılınca bu bilgi geriye doğru izlenerek yol kurulur.

/* labirentte en kısa yol: kuyruk + her hücrenin geldiği hücre */
typedef struct { short int satir, sutun; } hucre;
int en_kisa_yol(void) {
  hucre q[64], once[8][8];                /* 6x6 iç kısım: en çok 36 hücre */
  int bas = 0, son = 0;
  short int gordu[8][8] = {{0}};
  q[son++] = (hucre){1, 1};  gordu[1][1] = 1;
  while (bas < son) {
    hucre h = q[bas++];                   /* kuyruğun önünden al */
    if (h.satir == CIKIS_SATIR && h.sutun == CIKIS_SUTUN) {
      int uzunluk = 1;                    /* çıkıştan geriye izle */
      while (h.satir != 1 || h.sutun != 1) {
        labirent[h.satir][h.sutun] = 2;   /* yolu işaretle */
        h = once[h.satir][h.sutun];
        uzunluk++;
      }
      labirent[1][1] = 2;
      return uzunluk;
    }
    for (int yon = 0; yon < 8; yon++) {
      int s = h.satir + hareket[yon].dikey;
      int t = h.sutun + hareket[yon].yatay;
      if (!labirent[s][t] && !gordu[s][t]) {
        gordu[s][t] = 1;
        once[s][t] = h;
        q[son++] = (hucre){s, t};         /* kuyruğun arkasına ekle */
      }
    }
  }
  return 0;                               /* yol yok */
}

• Kuyruk basit bir dizidir: bas önden alınacak, son arkaya yazılacak konumdur. Her hücre en çok bir kez kuyruğa girdiği için dairesel yapıya gerek yoktur; dizi iç kısmın hücre sayısı kadar yer tutsa yeter.
• Bir hücre kuyruğa girerken işaretlenir (gordu), çıkarken değil. Böylece aynı hücre iki farklı komşudan iki kez kuyruğa giremez.
• Önden alınan hücre çıkışsa once zinciri girişe kadar izlenir. Her adımda hücre 2 ile işaretlenir ve yol uzunluğu bir artar.

Doğrulama programında fonksiyon 9 hücrelik yolu buldu ve labirenti yığınlı aramayla aynı biçimde işaretledi; bu labirentte en kısa yol tektir. Kuyruğa en çok 13 hücre girer. Süre O(m · p), ek bellek (once, gordu, kuyruk) O(m · p)'dir.

8.11.6Özyinelemesiz kök önde ve kök sonda gezinme

Çözüm, özyinelemesiz ağaç gezinmesini anlatan kesimdeki kok_basta ve kok_sonda fonksiyonlarıdır. Kök önde gezinmede kök yığına konur; her turda üstteki düğüm alınır, yazdırılır, önce sağ sonra sol çocuğu yığına konur. Kök sonda gezinme iki yığınla yapılır: birinci yığın “kök, sağ, sol” sırasını üretir, ikinci yığın bu sırayı ters çevirir. Tek yığınla da yazılabilir; o zaman her düğüm için sağ alt ağacının gezilip gezilmediğini gösteren bir ziyaret bayrağı ya da son yazdırılan düğümün adresi tutulur.

8.12Özet

• Yığın son giren ilk çıkar kuralıyla çalışır. Dizi gerçeklemesinde üste koyma y[++top] = x, üstten alma y[top--]'dır; ikisi de O(1)'dir.
• Geri izleme: labirentte her yol ayrımı yığına konur; çıkmazda yığından alınarak son ayrıma dönülür. Kayıttaki yön alanı, dönüşte daha önce denenmiş yönlerin atlanmasını sağlar. Çevredeki duvar çerçevesi sınır denetimini, gezildi matrisi sonsuz döngüyü önler.
• En kötü durum, uzun ve yanlış bir ilk yoldur: doğru yol dışındaki bütün bölge gezilir. izbul O(m · p) zaman ve bellek kullanır; bulduğu yol en kısa olmak zorunda değildir. Kuyrukla yapılan genişlik öncelikli arama en kısa yolu garanti eder.
• Gösterimler: ara ek gösterim öncelik ve parantez ister; önek ve sonek gösterim parantezsiz ve önceliksiz hesaplanır. Üç gösterimde de işlenenlerin sırası aynıdır.
• Sonek hesaplama: işlenen yığına konur; işleçte önce op2 (sağ), sonra op1 (sol) alınır, sonuç yığına konur. Θ(n). Önek hesaplamada ifade sağdan sola okunur ve ilk alınan sol işlenendir.
• Ara ekten soneke: işlenen çıktıya yazılır; yığındaki işleç isp ≥ icp oldukça çıktıya alınır. ( gelirken en yüksek, yığında en düşük önceliklidir; ) gelince ('a kadar boşaltılır. Eşitlikte almak soldan birleşmeyi sağlar. Θ(n).
• Parantez denetimi: açan yığına konur, kapanan üstteki açanla eşleşmelidir; sonda yığın boş olmalıdır. Üç hata türü: yanlış eşleşme, fazla kapanan, kapanmamış açan.
• Genel ilke: “en son açılan ilk kapanır” görülen her yerde yığın, “sırayla” görülen yerde kuyruk. Geri al/yinele, özyinelemesiz gezinme, sonraki büyük öğe ve kayan pencere bu ilkenin başka uygulamalarıdır.
• Fonksiyonlar bileşen gibi yazılmalıdır: girdiler parametreyle gelir, sonuç dönüş değeriyle gider, küresel değişkenlere bağımlılık kurulmaz.

8.13Kavram listesi

Terimlerin İngilizce karşılıkları ve öteki bölümlerdeki kullanımları terim sözlüğünde bulunur.

• yığın stack
• son giren ilk çıkar LIFO
• geri izleme backtracking
• labirent maze
• arama tablosu look-up table
• kaba kuvvet brute force
• en kötü durum worst case
• derinlik öncelikli arama depth-first search (DFS)
• genişlik öncelikli arama breadth-first search (BFS)
• en kısa yol shortest path
• ifade değerlendirme expression evaluation
• işleç önceliği operator precedence
• birleşme yönü associativity
• ara ek infix
• önek prefix (Polish notation)
• sonek postfix (reverse Polish notation)
• söz dizim birimi token
• sayım tipi enumeration (enum)
• yığın içi öncelik in-stack precedence (isp)
• gelen öncelik incoming precedence (icp)
• küresel değişken global variable
• parantez denetimi balanced parentheses
• kısa devre değerlendirme short-circuit evaluation
• geri al undo
• çift uçlu kuyruk deque (double-ended queue)
• ifade ağacı expression tree
• çağrı yığını call stack

8.14Kendini Dene

1. a*b-(c+d)/e ifadesinin sonek ve önek karşılıkları nedir?

   Cevap

   Tam parantezli biçim ((a*b) − ((c+d)/e))'dir. Sonek: ab*cd+e/-. Önek: -*ab/+cde. postfix yordamında - gelince yığındaki * çıktıya alınır; ( -'nin üstüne biner; ) gelince + çıktıya geçer; / -'nin üstüne biner. Sonda / ve - çıkar.

2. 82/3-42*+ sonek ifadesinin değeri nedir? Yığın en çok kaç değer tutar?

   Cevap

   8 / 2 = 4, 4 − 3 = 1, 4 · 2 = 8, 1 + 8 = 9. Sonuç 9'dur. Yığın en çok üç değer tutar: 4 ve 2 konduğu anda yığında 1 · 4 · 2 vardır.

3. prefix_eval("+*23-84") hangi değeri döndürür? - işlenirken op1 ve op2 nedir?

   Cevap

   Sağdan sola: 4, 8 yığına. -: ilk alınan op1 = 8, op2 = 4, sonuç 4. Sonra 3 ve 2 yığına; *: op1 = 2, op2 = 3, sonuç 6. +: 6 + 4 = 10. Sonuç 10'dur.

4. dengeli("{[}]") ne döndürür? Hangi karakterde ve neden?

   Cevap

   false. { ve [ yığına konur. Üçüncü karakter } geldiğinde yığının üstünde [ vardır; eslesir('[', '}') yanlıştır. Yanlış eşleşme hatasıdır. Açan ve kapanan sayıları eşit olduğu için tek bir sayaç bu hatayı yakalayamazdı.

5. postfix yordamında karşılaştırma >= yerine > yazılırsa a-b-c nasıl çevrilir? a = 9, b = 5, c = 2 için iki sonucun değeri nedir?

   Cevap

   İkinci - geldiğinde ilk - yığından alınmaz; ikinci - onun üstüne biner. Çıktı abc-- olur, yani a−(b−c). Değeri 9 − 3 = 6'dır. Doğru çeviri ab-c-'nin değeri (9 − 5) − 2 = 2'dir.

6. izbul'da başlangıç kaydının yön alanı 1 yerine 0 olsaydı bulunan yol değişir miydi?

   Cevap

   Değişmezdi. Yön 0, (1,1)'den kuzeye, yani çerçevedeki [0][1] duvarına bakar. Bu yön denenir, duvar olduğu için ++yon ile atlanır ve arama yön 1'den aynı biçimde sürer. Yalnız bir gereksiz deneme eklenir.

7. isp('(') 0 değil de 20 olsaydı a*(b+c) nasıl çevrilirdi?

   Cevap

   + geldiğinde isp(() = 20 ≥ icp(+) = 12 olur ve ( çıktıya alınır; ardından * da çıktıya alınır (13 ≥ 12). Çıktıya parantez karışır ve sıra bozulur. ) geldiğinde ise yığında ( bulunmaz; iç döngü dip işaretini de geçip dizi dışına okur. ('ın yığında en düşük öncelikli olması bu yüzden zorunludur.

8. (a+b)*(c-d)/e ifadesinin soneki nedir? a = 5, b = 3, c = 4, d = 2, e = 1 için değeri kaçtır?

   Cevap

   Sonek: ab+cd-*e/. * ve / eşit önceliklidir ve soldan birleşir; / geldiğinde * çıktıya alınır. Değer: 5 + 3 = 8, 4 − 2 = 2, 8 · 2 = 16, 16 / 1 = 16.

9. Labirentte yığın yerine kuyruk kullanılırsa neden ilk bulunan yol en kısa olur? Kuyruğa giren bir hücre neden girerken işaretlenir?

   Cevap

   Kuyruk hücreleri girişe uzaklık sırasıyla verir: uzaklığı d olan bütün hücreler, uzaklığı d + 1 olanlardan önce işlenir. Bir hücreye ilk ulaşan yol bu yüzden en kısa yoldur. Hücre girerken işaretlenmezse, kuyruktan çıkmadan önce başka bir komşu onu ikinci kez kuyruğa ekleyebilir; kuyruk gereksiz yere büyür ve once bilgisi yanlış bir yolla üzerine yazılabilir.

8.15İleri okuma

• E. Horowitz, S. Sahni, S. Anderson-Freed, Fundamentals of Data Structures in C, 2. baskı, Kesim 3.5 ve 3.6. Labirent yordamı, isp/icp tablosu ve ifade değerlendirme bu notta izlenen biçimiyle oradadır.
• R. Sedgewick, Algorithms in C, Kısım 1–4, Kesim 4.3. Sonek hesaplama ve ara ekten soneke çevirme, yığın soyut veri tipinin ilk uygulamaları olarak ele alınır; özyineleme ile yığın arasındaki ilişki 5. bölümde işlenir.
• T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, 3. baskı, MIT Press, 2009, Bölüm 10 ve 22. Yığın ve kuyruğun dizi ile gerçeklenmesi, genişlik ve derinlik öncelikli aramanın doğruluk kanıtlarıyla birlikte anlatılır.

8.16Kaynaklar

1. E. Horowitz, S. Sahni, S. Anderson-Freed, Fundamentals of Data Structures in C, 2. bs., Silicon Press, 2008. Bölüm 3.5 (labirent), 3.6 (ifade değerlendirme).
2. R. Sedgewick, Algorithms in C, Kısım 1–4, 3. bs., Addison-Wesley, 1998. Bölüm 4.3 (sonek), 5 (özyineleme ve yığın).
3. T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, 3. bs., MIT Press, 2009.