Yığınlarla Infix Postfix İşlemleri Nasıl Yapılır?

Yayınlandı İçinde

Yığın yapısı kullanarak Infix’ten Postfix’e dönüşüm işlemlerini şu şekillerle daha iyi anlayabiliriz.

Örnek


using System;

namespace postfix
{
    class Program
    {
        static char[] stack = new char[100];
        static int sp = -1;
        static void push(char data)
        {
            sp++;
            stack[sp] = data;
        }
        static char pop()
        {
            char data = stack[sp];
            sp--;
            return data;
        }
        static char peek()
        {
            return stack[sp];
        }
        static void Main(string[] args)
        {
            string infix = "a+b-c+d*e*f/g-h";
            push('$');
            string vars = "abcdefgh";
            string ops = "$+-*/";
            int[] onc = new int[5];
            onc[0] = 0; // $
            onc[1] = 1; // +
            onc[2] = 1; // -
            onc[3] = 2; // *
            onc[4] = 2; // /
            string postfix = "";
            for (int i = 0; i < infix.Length; i++)
            {
                if(vars.IndexOf(infix[i]) >= 0)
                    postfix += infix[i];
                else
                {
                    if(onc[ops.IndexOf(infix[i])] > onc[ops.IndexOf(peek())])
                        push(infix[i]);
                    else
                    {
                        postfix += pop();
                        push(infix[i]);
                    }
                }
            }
            while(peek() != '$') postfix += pop();
            Console.WriteLine(postfix);
        }
    }
}

Eğer parantez içeren bir infix işlemini postfix işlemine dönüştürme isteseydik kod aşağıdaki hali alacaktı.


using System;

namespace postfix_parantezli
{
    class Program
    {
        static char[] stack = new char[100];
        static int sp = -1;
        static void push(char data)
        {
            sp++;
            stack[sp] = data;
        }
        static char pop()
        {
            char data = stack[sp];
            sp--;
            return data;
        }
        static char peek()
        {
            return stack[sp];
        }
        static void Main(string[] args)
        {
            string infix = "a+b+c/d*(a-b-c*d)";
            push('$');
            string vars = "abcd";
            string ops = "$(+-*/";
            int[] onc = new int[6];
            onc[0] = 0; // $
            onc[1] = 0; // (
            onc[2] = 1; // +
            onc[3] = 1; // -
            onc[4] = 2; // *
            onc[5] = 2; // /
            string postfix = "";
            for (int i = 0; i < infix.Length; i++)
            {
                if(infix[i] == '(')
                {
                    push(infix[i]);
                    continue;
                }
                if(infix[i] == ')')
                {
                    while(peek() != '(') postfix += pop();
                    pop();
                    continue;
                }
                if(vars.IndexOf(infix[i]) >= 0)
                    postfix += infix[i];
                else
                {
                    if(onc[ops.IndexOf(infix[i])] > onc[ops.IndexOf(peek())])
                        push(infix[i]);
                    else
                    {
                        postfix += pop();
                        push(infix[i]);
                    }
                }
            }
            while (peek() != '$') postfix += pop();
            Console.WriteLine(postfix);
        }
    }
}

Şimdi herhangi bir üslü sayı içerecek olan infix ifadenin postfix ifadeye nasıl dönüştürüleceğini ele alalım.


using System;

namespace postfix_uslu
{
    class Program
    {
        static char[] stack = new char[100];
        static int sp = -1;
        static void push(char data)
        {
            sp++;
            stack[sp] = data;
        }
        static char pop()
        {
            char data = stack[sp];
            sp--;
            return data;
        }
        static char peek()
        {
            return stack[sp];
        }
        static void Main(string[] args)
        {
            string infix = "a*b^c-d";
            push('$');
            string vars = "abcd";
            string ops = "$(+-*/^";
            int[] onc = new int[7];
            onc[0] = 0; // $
            onc[1] = 0; // (
            onc[2] = 1; // +
            onc[3] = 1; // -
            onc[4] = 2; // *
            onc[5] = 2; // /
            onc[6] = 3; // ^
            string postfix = "";
            for (int i = 0; i < infix.Length; i++)
            {
                if (infix[i] == '(')
                {
                    push(infix[i]);
                    continue;
                }
                if (infix[i] == ')')
                {
                    while(peek() != '(') postfix += pop();
                    pop();
                    continue;
                }
                if (vars.IndexOf(infix[i]) >= 0)
                    postfix += infix[i];
                else
                {
                    if (onc[ops.IndexOf(infix[i])] > onc[ops.IndexOf(peek())])
                        push(infix[i]);
                    else
                    {
                        postfix += pop();
                        push(infix[i]);
                    }
                }
            }
            while (peek() != '$') postfix += pop();
            Console.WriteLine(postfix);
        }
    }
}

Şimdi postfix bir ifadeyi yığın yapısı kullanarak sayısal karşılığını bulalım.


using System;

namespace postfix_sayisal_karsilik
{
    class Program
    {
        static int[] stack = new int[100];
        static int sp = -1;
        static void push(int data)
        {
            sp++;
            stack[sp] = data;
        }
        static int pop()
        {
            int data = stack[sp];
            sp--;
            return data;
        }
        static int peek()
        {
            return stack[sp];
        }
        static int topla(int p1, int p2)
        {
            return p1 + p2;
        }
        static int cikar(int p1, int p2)
        {
            return p1 - p2;
        }
        static int carp(int p1, int p2)
        {
            return p1 * p2;
        }
        static int bol(int p1, int p2)
        {
            return p1 / p2;
        }
        static void Main(string[] args)
        {
            string postfix = "abc*+";
            string ops = "+-*/";
            string vars = "abc";
            int[] vals = new int[3];
            vals[0] = 1;
            vals[1] = 2;
            vals[2] = 3;
            for (int i = 0; i < postfix.Length; i++)
            {
                if (ops.IndexOf(postfix[i]) == -1)
                    push(vals[vars.IndexOf(postfix[i])]);
                else
                {
                    int p1 = pop();
                    int p2 = pop();
                    if (postfix[i] == '+') push(topla(p2,p1));
                    if (postfix[i] == '-') push(cikar(p2,p1));
                    if (postfix[i] == '*') push(carp(p2,p1));
                    if (postfix[i] == '/') push(bol(p2,p1));
                }
            }
            Console.WriteLine(pop());
        }
    }
}