1-) VERİYAPILARI - INFIX, PREFIX VE POSTFIX NOTASYONLARIN KULLANIMI

Infix notasyonu: Alışa geldiğimiz ifadeler infix şeklindedir. 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.

Prefix notasyonu: Prefix notasyonunda (PN, polish notation) operatörler, operandlarından önce yazılır. Örneğin 2+4*6 ifadesi infix notasyonundadır ve prefix notasyonunda +2*46 şeklinde gösterilir.
Benzer biçimde (2+4)*6 ifadesi *+246 şeklinde gösterilir. Görüldüğü gibi prefix notasyonunda işlem önceliklerinin sağlanması için parantezlere ihtiyaç duyulmamaktadır.

Postfix notasyonu: Postfix notasyonunda (RPN, reverse polish notation) ise önce operandlar ve ardından operatör yerleştirilir. Aynı örnek üzerinden devam edersek; infix notasyonundaki 2+4*6 ifadesi prefix notasyonunda 2 4 6 * + şeklinde, benzer biçimde (2+4)*6 ifadesi de 2 4 + 6 * şeklinde gösterilir. Yine prefix’te olduğu gibi bu gösterimde de parantezlere ihtiyaç duyulmamaktadır.

Bazı bilgisayarlar matematiksel ifadeleri postfix olarak daha iyi saklayabilmektedir.

İşlem önceliği;
1- Parantez içi
2- Üs alma
3- Çarpma/Bölme
4- Toplama Çıkarma
Aynı önceliğe sahip işlemlerde sıra soldan sağa (→) doğrudur. Yalnız üs almada sağdan sola doğru işlem yapılır.

Infix, Postfix ve Prefix İfadelerinin Dönüşümleri

Infix to postfix (Infix’den Postfix’e):

 Öncelikle soldan sağa doğru ifadeyi geziyoruz eğer gelen karakter rakam veya harf ise onu yazıyoruz. 

Eğer gelen ifade açma parantezi ‘(‘ ise direk olarak stack’e push ediyoruz. 

Eğer gelen ifade bir operator(+ - * /) ise onu öncelikle stack’in en üstündeki eleman ile karşılaştırıyoruz eğer gelen operatorun önceliği büyükse onu stack’e push ediyoruz veya stack boş veya en üstteki eleman ‘(‘ ise yine push ediyoruz. 

Eğer tam tersi ise yani önceliği düşük veya eşit ise en üstteki elemanı stack den çıkarıp(pop) ifadeye ekliyoruz ve yeni elemanı push ediyoruz veya eğer kapama parantezi ‘)’ gelirse stack da ilk açma parantezine kadar olan tüm kısmı sırayla push ederek ifadeye ekliyoruz. 

Bu işlemleri ifadenin hepsi bitene kadar yapıyoruz ve eğer ifade bittiğinde stack içerisinde operator kalırsa onları en üsttekinden başlayarak sırayla çıkararak onlarıda postfix ifademize ekliyoruz. 

Daha iyi anlamak için aşağıdaki örneğimizi inceliyoruz.

A + (( B – C * D ) / E ) + F – G / H   ifadesinin postfix’e çevrilmesi

  Sonuç:  A B C D * - E / + F + G H / -

Infix to Prefix (Infix’den Prefix’e): 

Önce verilen ifadeyi tersine çeviriyoruz yani sağdan başlayarak sola doğru  ifadeyi tekrar yazıyoruz. 

Yeni çıkan ifadeye yukarıda anlatılan infix to postfix işlemlerini uyguluyoruz. 

En son bulduğumuz ifadeyi tekrar ters çevirerek işlemi tamamlıyoruz. 

A + (( B – C * D ) / E ) + F – G / H   ifadesinin prefix’e çevrilmesi

Öncelikle ifadeyi ters çeviriyoruz 

Ters hali:  H / G – F + ( E / ( D * C – B ) ) + A

Sonuç : + A + / - B * C D E - F / G H 

Evaluating a postix expression ( Postfix ifadenin sonucunu bulma ve işlemleri yapma) 

Öncelikle Evaluate ederken sayıları stack’e pushluyoruz eğer operator gelirse stack’den en üstteki iki elemanı çıkarıyoruz ve işlemi yapıp(operatöre göre) sonucu tekrar push ediyoruz burada önemli olan şey iki eleman alırken ilk eleman operatör’ın sağı 2.eleman sol tarafı oluyor yani şöyle; 

int sag=stack.pop(); 

int sol = stack.pop(); 

int sonuc = sol operator(+-*/) sag; 

Bu şekilde ifade bitene kadar yapıyoruz ve en son stackde kalan eleman bizim sonucumuz oluyor. 

Daha iyi anlamak için aşağıdaki örneğimizi inceliyoruz. 

A B C D * - E / + F + G H / -  postfix ifadesinin sonucunu bulma, bunu yapmak için sayısal değerler veriyoruz.

A = 7, B =14 , C = 4, D=1, E =5, F =3 , G=8 , H=2 

Yeni İfade: 7 14 4 1 * - 5 / + 3 + 8 2 / - 

Aynı sayılarla infix ifade sonucu : 7 + (( 14 – 4 * 1 ) / 5 ) + 3 – 8 / 2 = 7 + 2 + 3 – 4  = 8 

             Sonuç : 8