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

Merhaba bu yazımızda sizlerle birlikte stack veri yapısının bir uygulaması olan Infix, Postfix ve Prefix İfadelerinin Dönüşümlerini aktaracağız. Bilgisayar mühendisliğinde veri yapıları dersinde mutlaka karşımıza çıkan bu örneği birlikte inceleyeceğiz.

Öncelikle stack veri yapısı nedir ondan bahsedelim.

Stack çok yaygın bir veri yapısıdır ve en son giren ilk çıkar(lifo) yapısıyla çalıştığı için bu yapıya uygun her alanda kullanılabilir.

Şimdi stack veri yapısının temel işlemlerinden bahsedelim. Stack veri yapısının 4 temel işlemi var bunlar;

  • push: Stack’ in sonuna eleman ekler. 
  • pop : Stack’ in sonundan eleman siler ve onu geri döndürür. 
  • peek : Stack’ in sonundaki elemanı geri döndürür(silmez). 
  • empty : Eğer stack boş ise true döndürür. Değilse false.
Aşağıdaki linki kullanarak Javadaki stack classı’nı inceleyebilirsiniz. Ama dikkat edin javadaki stack classı vectorden extend edildiği için bir stack yapısına ait olmayan bazı operasyonlara sahip.


Şimdi ise stack yapısını kullanarak Infix, Postfix ve Prefix İfadelerinin Dönüşümlerini yapalım.

Tablo 1
Tablo 1
Tablodan da görüldüğü üzere infix ifadeler bizim günlük hayatta kullandığımız operatörlerin harflerin arasında olduğu ve bizler için anlaması kolay ifadelerdir. Postfix ve prefix ifadeler için bilgisayarlar veya hesap makineleri için anlaması kolay olan ifadelerdir çünkü onlar ifadeleri soldan sağa doğru tararlar ve işlemi yaparlar. Buna göre postfix ifadelerde önce harfler(operand) gelir sonra operatörler prefix de ise tam tersi önce operatörler sonra harfler(operand) gelir.

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

(Conversion of A + (( B – C * D ) / E ) + F – G / H to postfix.)

Tablo 2
Tablo 2
     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. 

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

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

(Conversion of A + (( B – C * D ) / E ) + F – G / H to prefix.) 

Öncelikle ifadeyi ters çeviriyoruz 

(To do this we need to convert this statement to reverse so we will get) 

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

Tablo 3
Tablo 3
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 

(Evaluating postfix expression  A B C D * - E / + F + G H / - with numbers 

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

Result of infix: 7 + (( 14 – 4 * 1 ) / 5 ) + 3 – 8 / 2 = 7 + 2 + 3 – 4 = 8)

Tablo 4
Tablo 4
             Sonuç : 8 

Aşağıdaki kod da verilen postfix ifadenin sonucunu recursive olarak bulan kodu inceleyebilirsiniz. Bizler burada stack olarak linkedlist kullandık sizler stack kullanabilirsiniz.


    /***
     * This method evaluates a prefix expression and returns result.
     * @param postfix a postfix expression that is separated with spaces.
     * @param list a stack to keep elements
     * @return result of expression
     */
    public static double evPostfix(String postfix,LinkedList<Integer> list){
        String value;
        char token;
        if (postfix == null || postfix.equals("")){ //if string is done stop
            return list.pop ();
        }
        if (!postfix.contains (" ")){ //if there is just one token
            value = postfix;
            postfix=""; //make empty string to stop
        }
        else
            //split string from space and evaluate token
            value = postfix.substring (0,postfix.indexOf (" "));
        token = value.charAt (0);
        if (Character.isDigit (token)){ //if it is digit push it list
            list.push (Integer.parseInt (value));
        }
        else if (isOperator (token)){ //if it is operator evaluate it.
            int rhs = list.pop(); //right side
            int lhs = list.pop(); //left side
            int result =0;
            switch (token) {
                case '+' :
                    result = lhs + rhs;
                    break;
                case '-' :
                    result = lhs - rhs;
                    break;
                case '/' :
                    result = lhs / rhs;
                    break;
                case '*' :
                    result = lhs * rhs;
                    break;
            }
            list.push (result);
        }
        return evPostfix (postfix.substring(postfix.indexOf (" ")+1),list); //call again
    }
    /***
     * This is a helper method to evaluate post and pre expression
     * @param c a character will be checked
     * @return true if it is an operator
     */
    private static boolean isOperator(char c){
        String operators = "+-*/";
        return operators.indexOf(c) != -1;
    }