Stack (Yığın) Kullanarak Infix-Postfix Dönüşümü

Veri yapıları derslerinde “iyi de hocam bunlar gerçek hayatta ne işimize yarayacak” dediğinizi duyar gibiyim. Bir programcı olarak şu basit soruyu düşünmenizi istiyorum; kullanıcı tasarladığım bir hesap makinesine karakter olarak bir takım sayılar, işlemler ve parantezler girecek. Peki ben hangi sayıları hangi öncelikle hangi işleme sokacağımı nasıl çözebilirim?

Infix,Postfix,Prefix bildiğimiz arıtmetik işlemlerin gösterimidir. Aslında ilkokuldan beridir bunlardan birine çok aşinayız. Örneğin a+b-c arıtmetik işlemini ele alalım . Bu yazdığım arıtmetik operatörlerin aralara gelerek gösterilmesine Infix gösterim deniyor. In (inside-içinde) olarak düşünebilirsiniz. Peki neden farklı gösterimlere ihtiyaç duyarız?

Mesela kod yazarken araya bir yere bir arıtmetik işlem sıkıştırdığınızda bilgisayarlar için bu gösterim şeklini çözmek çok zordur. Örneğin ((a+b)*c)/d) gibi bir gösterimde işin içine parantezler de girerse derleyici için sıkıntılı bir süreç başlar. İşte derleyici birkaç adım ile işlemi kendisinin daha iyi anlayacağı Postfix biçimine dönüştürerek bu işi çözer, parantezlerle hiç uğraşmaz. İşte bizim hesap makinasının işlemleri daha kolay anlayabilmesi için yapacağı iş te budur.

Bu gösterimler arasındaki farklar şudur . Prefix gösteriminde operatörler önem sırasına göre operandlardan önceye koyar. Pre (previous — öncesi) olarak düşünebilirsiniz. Postfixte de tahmin edebileceğiniz gibi arıtmetik operatörler operandlardan sonra gelir. İki gösterimde de parantezler yoktur .

Gösterimlere Örnek

Aşağıda parantez ile örnek verildiğinde operatörlerin yerleşme sırasını daha iyi anlayacaksınız.

Postfix ve Prefix gösterimde parantezler anlamayı kolaylaştırması açısından konulmuştur.

Yani benim hesap makinam

Öyleyse derleyiciler bu dönüşümü nasıl efektif bir şekilde yapıyorlar ? Stack yapısı kullanılarak bu işlem hafıza karmaşıklığı açısından başarılı bir şekilde gerçekleştirilebiliyor. Bunun için aşağıdaki adım algoritmasını kullanabiliriz.

Adım 1-Sıradaki karakteri oku Adım 2 ye geç.
Adım 2-
A-Eğer karakter aç parantez ise yığına ekle.
B-Eğer operatör ise ve yığın boş ise karakteri
yığına at eğer yığın boş değil ise ve yığındaki karakter aç parantez ise; karakteri yığına ekle, eğer
yığındaki karakter aç parantez değil operand ise ve eğer yığındaki operandın önceliği karakterden
yüksek ise ; yığındaki operatörun önceliği düsük olana kadar postfix gösterime ekle yığından çıkar, karakteri yığına ekle.
Yığındaki operandın önceligi karakterden küçük ise karakteri yığına ekle.
C-Eğer kapa parantez ise ; yığında aç-parantez görene kadar yığını boşaltıp postfix gösterime ekle, aç parantezi de yığından at.
D-Eğer operand ise; postfix gösterime ekle . Adım 3'e geç.
Adım 3-Karakter dizisi sonunda değilsen Adım 1'e dön, karakter sonunda
isen yığını kontrol et bos ise bitir bos degilse stack boş olana kadar stackteki
karakterleri postfix gösterime ekle.

Kaynak = Kayhan Ayar — Veri Yapıları 03 — Infix’den Postfix’e dönüşüm