Shunting Yard Algoritması

İlgili bağlantı: Abaküs

'32*(55-32-(11-4)+(533-(533-(533+(533-(533+212)))*21-2)))' gibi çok operatör ve operand içeren bir işlem düşünün. Derleyiciler buna benzer ifadeleri işlerken operatör önceliklerine göre işlem sıralarını doğru belirleyip sonuç üretebiliyorlar. Peki bunu nasıl yapıyorlar?...

Operatör Öncelik Ayrıştırması (Operator Precedence Parsing)

Bir ifadede farklı önceliklere sahip operatörler yazılma sırasıyla işlenirse ifade yanlış sonuçlandırılabilir. Örneğin 3+4*2 ifadesi 7*2=14 ile sonuçlandırılabileceği gibi 3+8=11 ile de sonuçlandırılabilir. Bu yüzden ifadelerin operatör önceliklerine göre ayrıştırılması, ayrılan parçaların sıralanması ve bu sıralamaya uyularak işlem yapılması gerekir.

Shunting Yard Algoritması

Shunting yard algoritması, farklı önceliklere sahip pek çok operatörün, kendileriyle ilişkili operandları doğru sırada işlemesini kolaylaştırmak amacıyla, infix notasyonundaki bir ifadenin postfix notasyonundaki karşılığının bulunmasını sağlayan, yığın yapısı temeline dayalı bir yöntem.

'Shunting yard', tren yolunun birden fazla kola ayrılıp birleştiği kısma verilen isim ve 'manevra alanı' gibi bir anlama geliyor. Bu yöntemde operatörlerin ve operandların girdi, yığın ve çıktı arasında çizdikleri yollar, rayların kollara ayrılıp birleştiği yerlere benzetildiği için yönteme böyle bir isim verilmiş...

Yöntemin mucidi tanıdık. Adını daha önce en kısa yol algoritması, semafor kavramı, makarna yiyen filozoflar problemi ve banker algoritması ile duymuştuk; Edsger Dijkstra...

Yöntemin ayrıntılarına girmeden önce bazı temel kavramlardan bahsedelim.

Infix, Prefix ve Postfix Notasyonları

Infix notasyonu, operatörlerin işlenecek operandlar arasına yerleştirildiği gösterim biçimidir. Bu gösterimde operatör önceliklerinin değiştirilebilmesi için parantez kullanılması şarttır. Örneğin infix notasyonundaki '2+4*6' ifadesi 2+24=26 ile sonuçlanır. Aynı ifadede + operatörüne öncelik verilmesi istenirse parantezler kullanılır; '(2+4)*6'. Böylece ifade 36 ile sonuçlandırılır. Genelde bilgisayar girdilerinde bu notasyon kullanılır. Ancak girdiler işlenmeden önce prefix veya postfix notasyonuna çevrilir.

Prefix notasyonunda(PN, 'polish notation' olarak da geçer) operatörler, operandlarından önce yazılır. Örneğin infix notasyonundaki '2+4*6' ifadesi prefix notasyonunda '+ 2 * 4 6' şeklinde gösterilir. Benzer şekilde '(2+4)*6' ifadesi '* + 2 4 6' şeklinde gösterilir. Görüldüğü gibi prefix notasyonunda işlem önceliklerinin sağlanması için parantezlere ihtiyaç duyulmaz.

Postfix notasyonunda(RPN, 'reverse polish notation' olarak da geçer) ise önce operandlar ve ardından operatör yerleştirilir. Aynı örnek üzerinden devam edelim; infix notasyonundaki '2+4*6' ifadesi prefix notasyonunda '2 4 6 * +' şeklinde gösterilir. Benzer şekilde '(2+4)*6' ifadesi '2 4 + 6 *' şeklinde gösterilir. Yine prefixte olduğu gibi bu gösterimde de parantezlere itiyaç duyulmaz.

Operatörler ve Birleşme(Association) Özellikleri

Operatörler, birleşme özelliği olanlar ve olmayanlar olmak üzere ikiye ayrılır. Birleşme özelliği olan operatörler de sol birleşmeli(left associative) ve sağ birleşmeli(right associative) olmak üzere ikiye ayrılır.

'4 o 3 o 2' şeklinde bir ifade düşünelim. Eğer 'o' operatörü sol birleşmeli ise ifadedeki operatör öncelikleri '(4 o 3) o 2' şeklinde olur ve ifade soldan sağa doğru işlenir. Ancak eğer operatör sağ birleşmeli ise ifade '4 o (3 o 2)' haline döner ve sağdan sola doğru işlenir. Örneğin '3-7+1' ifadesi, - ve + operatörleri sağ birleşmeli farzedilerek işlendiğinde ifade 3-(7+1)=-5 ile sonuçlandırılır. (Buradaki olay işlem önceliği ile karıştırılmamalıdır. + ve - operatörleri eşit işlem önceliğine sahiptir. Bu yüzden ifadenin 3+(-7+1) şeklinde olması gerektiğini düşünebilirsiniz. Ancak böyle yaparsanız ifadeye bir operatör daha katmış oluyorsunuz. Herşeyi programcılarından bekleyen bilgisayarlar üzerinde çalıştığımızı unutmayalım.) Sonuç yanlıştır, çünkü bu operatörler sol birleşmelidir. Doğru sonuç (3-7)+1=-3'tür.

Bir örnek daha yapalım. 3^7^1 ifadesideki ^ operatörünü sol birleşmeli olarak ele aldığımızda ifade (3^2)^4=6561 ile sonuçlandırılır. Sonuç yanlıştır. Çünkü ^ operatörü sağ birleşmeli bir operatördür, doğrusu şudur; 3^(2^4)=43046721.

Birleşme özelliği bulunmayan(non-associative) operatörler de vardır. Örneğin '3<4<1' ifadesi (Burada '<' işareti, 'küçüktür' demek değildir. Öyle olsaydı işaret bir operatör olmazdı. Bu işaret 'küçük müdür?' anlamındadır.) bir yazım yanlışıdır. Çünkü ifade (3<4)<1 veya 3<(4<1) şeklinde işlenmeye çalışıldığında, 3<4 veya 4<1 ifadesi, '<' operatörünün işleyebileceği ikinci bir sayı değeri döndürmez. Bir operatörün birleşme özelliğinin olup olmadığının anlaşılabilmesi için, döndürdüğü değerin kendisi tarafından işlenebilir olup olmadığına bakılabilir.

Tek Terimli Eksi (Unary Minus)

Tek terimli eksi, sayı önlerine gelen '-' operatörüdür. Önüne geldiği değerin toplama işlemine göre tersini alır. Tek terimli olan bu operatörün görevi, 0 değeri kullanılarak çift terimli - operatörüne yaptırılabilir. Örneğin '3+-2' ifadesinde '-' operatörü, tek terimli eksi operatörü olarak değerlendirilmek zorundadır. İfade, tek terimli eksi'nin çift terimli eksi ile işlenebilmesi için '3+(0-2)' şeklinde yeniden yazılabilir.

Shunting Yard Algoritmasının Ayrıntıları

Şimdi ayrıntılara inmeye hazırız. Shunting yard algoritması her operatörü, işleyeceği tüm operandlar alınana kadar yığında bekletir. Operandların tümünün alındığından emin olunduğunda operatör çıktıya aktarılır. Böylece ifadenin postfix notasyonundaki karşılığı elde edilir.

Önce ifadenin, sadece operatör veya sadece operand içerecek parçalara ayrılması gerekir. Bunu nasıl yapacağınız kullanacağınız dilin yeteneklerine bağlı...

Yöntemi uygulamaya dökmek için ihtiyaç duyduğumuz 3 şey var; parçalara ayrılmış girdi, bir yığın yapısı ve çıktıyı tutacak bir alan. Bunları sağladıktan sonra parçaları sırayla dolaşmaya başlıyoruz:

1. Aşağıdaki adımlar her bir parça için tekrar edilmeli. Sıradaki parça;
1.1. Bir sayı ise çıktıya ekle.
1.2. Bir fonksiyon adı ise yığına at.
1.3. Bir fonksiyona ait bir argüman ayıracı ise (',' gibi)
1.3.1. Açma parantezi bulana kadar operatörleri yığından çekip çıktıya ekle.
       (açma parantezi yığında kalacak)
1.4. Bir operatör ise(buna o1 diyelim)
1.4.1. Bu operatör sol birleşmeli ise
1.4.1.1. Yığının en üstündeki operatörün(buna da o2 diyelim) önceliği, o1 
         operatörün önceliğine eşit veya ondan büyük olduğu sürece o2 
         operatörünü yığından çekip çıktıya ekle.
         (Koşul sürekli sağlanırsa, yığın bitene kadar bu işleme devam et.)
1.4.2. Bu operatör sağ birleşmeli ise
1.4.2.1. Yığının en üstündeki operatörün(buna da o2 diyelim) önceliği, o1
         operatörün önceliğinden büyük olduğu sürece o2 operatörünü
         yığından çekip çıktıya ekle.
         (Koşul sürekli sağlanırsa, yığın bitene kadar bu işleme devam et.)
1.5. Bir parantez açma işareti ise yığına at.
1.6. Bir parantez kapama işareti ise
1.6.1. Açma parantezi bulana kadar operatörleri yığından çekip çıktıya ekle
       (açma parantezine rastlayınca onu yığından çekip at, çıktıya ekleme)
1.6.2. Eğer yığın boş değilse bir fonksiyon adı barındırıyor olması gerekir.
       Bu durumda fonksiyon adını yığından çekip çıktıya ekle.
2. Tüm parçalar tamamlanınca yığın boş değilse tüm içeriğini çıktıya ekle. 
   Yığında parantez açma/kapama işaretleri bulunmuyor olması gerekir. 
   Aksi halde girdi hatalıdır.

Böylece infix notasyonundaki girdi, postfix notasyonuna çevrilmiş olur. Bu yeni ifadenin işlenmesi daha kolaydır.

Postfix Notasyonundaki İfadenin İşlenmesi

İfadenin işlenmeye hazırlanması için yine sadece operatör veya sadece operand içerecek parçalara ayrılması gerekir. Parçalama işlemini kolaylaştırmak amacıyla yukarıdaki yöntemde çıktıya ekleme yapılırken, her eklenen yeni değer veya operatörün başına boşluk gibi bir ayıraç(delimiter) eklenebilir. Daha sonra elde edilen çıktı, bu ayıraçlar sınır kabul edilerek rahatlıkla parçalanabilir...

1. Aşağıdaki adımlar her bir parça için tekrar edilmeli. Sıradaki parça;
1.1 Sayı ise yığına at.
1.2 Operatör veya fonksiyon adı ise operatörün veya fonksiyonun işlediği
    argüman sayısı kadar değeri yığından çek ve bu değerleri operatör
    veya fonksiyon ile işle. Elde edilen sonucu yığına at.
    (Değerlerin yığından ters sırada çekildiğine dikkat edilmeli.)
2. Tüm parçalar tamamlandığında yığında tek bir değer bulunuyor olmalı.
   Bu değer ifadenin sonucudur.

Görüldüğü gibi postfix notasyonundaki ifadenin işlenip sonuçlandırılması oldukça kolay...

Leave Comment

Comments (2)