Infix Prefix dan Postfix

INFIX,PREFIX DAN POSTFIX
A. Infix adalah notasi yang membentuk atas operator dengan operand,dimana operator berada diantara operand.
   Contoh :        
                 - A + B * C
                 - (A + B) * C
                 - A - (B + C) * D ^ E

B. Postfix adalah notasi yang membentuk atas operator dengan operand, dimana operator berada dibelakang operand.

   Contoh : A + B * C ( infix).

maka notasi postfix adalah ABC*+.

C. Prefix adalah cara penulisan atau ungkapan yang meletakan operator disebelah kiri 2 operand dan dalam kurung sangat menentukan posisi.

Contoh Prefix :

+ A B

* - A B C

 Algoritma:

Berikut ini algoritma dari konversi Infix ke Postfix:

1. Buat presisi atau kekuatan operator ( Penjumlahan dan Pengurangan bernilai 2 , Perkalian dan Pembagian bernilai 3 , Kurang buka dan tutup bernilai 1 )
2. Input data dalam bentuk infix
3. Pisahkan data infix menggunakan split menjadi bentuk List
4. Periksa semua data yang berada di dalam list secara urut mulai dari awal hingga akhir
5. Jika bertemu operand, maka masukan data ke PostfixList untuk dicetak
6. Jika bertemu kurung buka '(' maka masukan ke Stack Operator
7. Jika bertemu kurung tutup ')' maka Stack Operator yang paling atas dan bukan kurung buka '(' diambil untuk dicetak ke PostfixList
8. Jika bertemu operator maka jika Stack Operator tidak kosong dan kekuatan operator yang digunakan lebih kecil dari kekuatan operator yang berada di top Stack Operator maka operator yang berada di Stack Operator diambil (pop) untuk dicetak di PostfixList. lalu masukan operator yang digunakan ke dalam Stack Operator.
9. Begitu seterusnya sampai List yang berisi data Infix habis.
10. Jika Stack Operator masih ada isinya maka ambil dan tambahkan ke PostfixList untuk dicetak.
11. Cetak PostfixList

Berikut ini Algoritma dari konversi Infix ke Prefix:

1. Balikan data Infix
2. Jika operator kurung buka '(' maka ganti dengan kurung tutup ')' begitu sebaliknya
3. Masukan data tersebut ke konversi Infix ke Postfix 
4. Setelah keluar hasil, Balikan lagi hasil tersebut
5. Maka keluar bentuk Prefix

kode programnya:

class Stack:

     def __init__(self):

         self.items = []

     def isEmpty(self):

         return self.items == []

     def push(self, item):

         self.items.append(item)

     def pop(self):

         return self.items.pop()

     def peek(self):

         return self.items[len(self.items)-1]

     def size(self):

         return len(self.items)

def infixToPostfix(infixexpr):

    prec = {}

    prec["*"] = 3

    prec["/"] = 3

    prec["+"] = 2

    prec["-"] = 2

    prec["("] = 1

    opStack = Stack()

    postfixList = []

    tokenList = infixexpr.split()

    tokenList.reverse()

    for i in range(len(tokenList)):

         if tokenList[i] == '(':

              tokenList[i]=')'

         elif tokenList[i] == ')':

              tokenList[i]='('

    for token in tokenList:

        if token in "ABCDEFGHIJKLMNOPQRSTUVWXYZ" or token in "0123456789":

            postfixList.append(token)

        elif token == '(':

            opStack.push(token)

        elif token == ')':

            topToken = opStack.pop()

            while topToken != '(':

                postfixList.append(topToken)

                topToken = opStack.pop()

        else:

            while (not opStack.isEmpty()) and \

               (prec[opStack.peek()] >= prec[token]):

                  postfixList.append(opStack.pop())

            opStack.push(token)

    while not opStack.isEmpty():

        postfixList.append(opStack.pop())

    postfixList = postfixList[::-1]

    return " ".join(postfixList)

print(infixToPostfix("A * B + C * D"))

print(infixToPostfix("( A + B ) * C - ( D - E ) * ( F + G )"))

 
 Kode Program PostfixEval:

class Stack:

     def __init__(self):

         self.items = []

     def isEmpty(self):

         return self.items == []

     def push(self, item):

         self.items.append(item)

     def pop(self):

         return self.items.pop()

     def peek(self):

         return self.items[len(self.items)-1]

     def size(self):

         return len(self.items)

def postfixEval(postfixExpr):

    operandStack = Stack()

    tokenList = postfixExpr.split()

    for token in tokenList:

        if token in "0123456789":

            operandStack.push(int(token))

        else:

            operand2 = operandStack.pop()

            operand1 = operandStack.pop()

            result = doMath(token,operand1,operand2)

            operandStack.push(result)

    return operandStack.pop()

def doMath(op, op1, op2):

    if op == "*":

        return op1 * op2

    elif op == "/":

        return op1 / op2

    elif op == "+":

        return op1 + op2

    else:

        return op1 - op2

print(postfixEval('4 5 6 * +'))