Infix to postfix dönüşümü, operatorün ortada olduğu a+b yazım şeklini operatorün sonda olduğu ab+ yazım şekline dönüştürme işlemidir. Bu yazıda iki şekilde dönüşümden bahsedeceğim:
1) Stack yapısı kullanarak dönüştürme
2) Kağıt üstünde el ile dönüştürme
Infix gösterimi, bizler için kolay bir gösterim olsa da makineler için öyle değildir. İfadeyi okurken a + b * c işleminde önce b ile c yi çarpıp sonra da a ile toplamayı kolay bir şekilde yapabiliriz çünkü bizim ifadeyi sıra ile adım adım giderek okuma zorunluluğumuz yok. Önce b*c nin öncelikle olduğunu görerek oradan başlar, sonra a ile kolayca toplarız.
Ama makineler için işler başkadır. Hangi işlemin öncelikle yapılması gerektiğine karar vermesi için önce tüm ifadeyi okumalı sonra da geriye dönüp hangi ifadeleri işlemesi gerektiğini bir döngü içerisinde tekrarlaması gerekir. Ayrıca ifadeyi okurken karşılaştığı ifadenin başka bir işlemde öncelikli olduğunu bilmesi için yine okumaya devam etmesi gerekir, mesela a + b*c ifadesinde a ile b'yi toplama yanlışına girmemek için daha yüksek öncelikli bir operator var mı yok mu diye kontrol etmesi gerekir. Ancak eğer ifade postfix notasyonuna göre yazılırsa, yani abc*+ şeklinde, yapması gereken sadece soldan sağa doğru okumak ve operandları yığıta ekleyerek karşılaştığı her operator için iki tane sayıyı stack'den çıkararak işlemek.
Mesela 1 + 3*5 ifadesinin postfix hali olan 1 3 5 * + ifadesini makinenin nasıl okuyup, sayıları nasıl işlediğine bakalım:
- 1'i oku ve stack'e at. Stack: 1 Kalan ifade:3 5 * +
- 3'ü oku ve stack'e at. Stack: 1 3 Kalan ifade: 5 * +
- 5'i oku ve stack'e at. Stack: 1 3 5 Kalan ifade: * +
- *'yi oku. Çarpım olduğu için stack'den iki tane operand çek ve çarp. Sonra tekrar stack'e ekle. Yani 3 * 5 = 15. Stack: 1 15 Kalan ifade: +
- +'yi oku. Toplama olduğu için stack'den iki operand çek ve topla. Sonra tekrar stack'e ekle. Yani 1 + 15 = 16. Stack: 16 Kalan ifade:
- Tüm ifade bitti ise stack'deki sayıyı sonuç olarak ekrana yaz. Sonuç: 16
Gördüğünüz gibi makine, ifadeyi okurken hiç geriye dönmedi ve sadece solda sağa okuma yaparak önüne çıkan sayıları işleme soktu ve sonucu buldu. İnfix şeklinde yazılsaydı, geriye dönüp ne yapması gerektiğine tekrar bakacaktı ve zaman kaybı olacaktı bu durum.
Şimdiye kadar yazdıklarım tamamen sizlere postfix ifadenin neden kullanıldığını göstermek üzerineydi. Yazının devamında ise, infix ifadeyi postfix ifadeye dönüştürmenin iki yolundan bahsedeceğim. En çok bilinen yol stack kullanarak dönüşümü anlatmakla başlayalım.
Stack kullanarak infix to postfix dönüşümü
Stack kullanarak dönüşüm yapma işlemi programlamaya en uygun olan işlemdir. Algoritmamız basit. Adımları yazalım
1) Soldan sağa doğru infix ifadeyi okumaya başla
2) Eğer sıradaki karakter bir operator değilse, sonuca yaz
3) Eğer sıradaki karakter bir operator ise:
3.1) Eğer bu operator yığıtın üstündeki operatore eşit veya düşük öncelikli ise, diğerlerinden yüksek öncelikli olana kadar veya ( karakteri görene kadar yığıttaki karakterleri çıkar ve sonuca yaz, son olarak bu operatorü yığıta ekle
3.2) Eğer bu operator yığıtın üstündeki operatorden yüksek öncelikli ise yığıta ekle
4) Eğer ) karakteri ise, ( karakteri görene kadar yığıttan çıkarma yap ve sonuca yaz.
5) Karakter okuması bittiğinde, yığıttaki tüm verileri çıkar ve sonuca yaz
Bu algoritmaya uygun olarak yazdığım Python programını aşağıda bulabilirsiniz.
| # coding: utf-8 | |
| import operator | |
| # gerekli değişkenleri tanımlıyoruz | |
| islemler = { | |
| "+": operator.add, | |
| "-": operator.sub, | |
| "/": operator.truediv, # belki floordiv? | |
| "*": operator.mul, | |
| } | |
| operatorler = { | |
| "+":1, | |
| "-":1, | |
| "/":2, | |
| "*":2, | |
| "(":3, | |
| ")":3, | |
| } | |
| infix_ifadeler = [ | |
| "4*5+8-10/2", | |
| "4+57-9/3", | |
| "5+5", | |
| "3/(1+1*1)", | |
| "794/(23*34+12)" | |
| ] | |
| # tüm işlemleri tek tek yapıyoruz | |
| for infix_ifade in infix_ifadeler: | |
| print("-"*23) | |
| stack = [] | |
| postfix_ifade = [] | |
| sayi = "" | |
| for i in infix_ifade: | |
| if i.isdigit(): | |
| # sayıları bütün olarak elde edebilmek için | |
| sayi += i | |
| else: | |
| if sayi: | |
| postfix_ifade.append(sayi) | |
| sayi = "" | |
| if i == "(": | |
| stack.append(i) | |
| elif i == ")": | |
| while stack and stack[-1] != "(": | |
| postfix_ifade.append(stack.pop()) | |
| stack.pop() # açma parantezi kaldırıyoruz | |
| else: | |
| while stack and stack[-1] != "(" and operatorler.get(i) <= operatorler.get(stack[-1]): | |
| postfix_ifade.append(stack.pop()) | |
| stack.append(i) | |
| if sayi: | |
| postfix_ifade.append(sayi) | |
| while stack: | |
| postfix_ifade.append(stack.pop()) | |
| print(infix_ifade, " ifadesinin postfix sonucu ==>", postfix_ifade) | |
| # postfix ifade yardımıyla işlemin sonucunu hesaplayacağız | |
| for token in postfix_ifade: | |
| if token in islemler: | |
| a = float(stack.pop()) | |
| b = float(stack.pop()) | |
| stack.append( | |
| islemler[token](b, a) | |
| ) | |
| else: | |
| stack.append(token) | |
| print(infix_ifade, "işleminin sonucu:", *stack) |
Elle dönüşüm
Elle dönüşüm işlemi, genelde sınavlarda çok işinize yarayacaktır diye düşünüyorum. Sınavda yığıt ile uğraşmak istemiyorsanız bu yöntem size daha pratik gelecektir. Bu yöntem, elimizdeki ifadeyi ikili operandlar halinde gruplamaya dayanıyor. Elimizde a+b var ise, bunu (a+b) olarak düşünüp operatorü sona alıyoruz. Yani (ab+). Sonra parantezleri kaldırıyoruz, ab+. Dönüşüm tamamdır.
Bir başka örneğe bakalım. Mesela a+b*c ifadesini elle dönüştürelim. Öncelikle gruplama yapmamız lazım. İlk olarak gördüğünüz gibi b*c ifadesi öncelikli görünüyor. O zaman hemen gruplayalım. a+(b*c). Sonra bu ikili grubun operandını parantezin sonuna alalım. a+(bc*). Şimdi dikkat ederseniz a ve (bc*) ifadesi bir grup haline getirililebilir. Yani şöyle yapacağız, (a + (bc*)). Yine aynı kuralı uygulayıp bu grubun operandını sona alalım, (a(bc*)+). Artık gruplayacak başka ikili kalmadığına göre tüm parantezleri kaldıralım, abc*+ . Gördüğünüz gibi yığıt ile uğraşmadan postfix hale dönüştürdük.
Peki öncelik olmayan ifadeleri nasıl gruplayacağız? Onu da soldan başlayarak gruplayacağız. Mesela a+b+c ifadesini dönüştürelim. Burada öncelikli görünen bir durum yok. O zaman soldan gruplayalım. (a+b) + c. Güzel, şimdi grup operatörünü sona alalım, (ab+)+c . Eğer görebiliyorsanız, (ab+) ve c bir ikili oluşturuyor, hemen gruplayalım. ((ab+)+c). Ve şimdi yine grubun operatörünü dışarı alalım, ((ab+)c+). Ve artık gruplayacak ifade kalmadığına göre tüm parantezleri kaldıralım ve ab+c+ sonucunu elde edelim. Bu kadar basit :)
Elimden geldiğince anlaşılır bir şekilde anlattım. Anlamadığınız bir kısım olursa yorum yapabilirsiniz. Bir başka yazıda buluşmak dileğiyle...
Yorumlar
Yorum Gönder