Infix, Prefix dan Postfix pada Python

A. Definisi

Infix adalah cara penulisan atau ungkapan yang meletakan operator di tengah antara 2 operand dalam hal ini dalam kurung sangat menentukan posisi.

Contoh Infix :

A + B

( A - B ) * 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

Posfix adalah cara penulisan yang meletakan operator disebelah kanan 2 operand dan posisi operand yang berada di dalam kurung sangat menentukan.

Contoh Postfix :

A B +

A B - C *

B. Ilustrasi

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

D. Kode Program 

Berikut ini kode program Konversi dari Infix ke bentuk Postfix :

2. class Stack:
3.     def __init__(self):
4.         self.items = []
5.     def isEmpty(self):
6.         return self.items == []
7.     def push(self, items):
8.         self.items.append(items)
9.     def pop(self):
10.         return self.items.pop()
11.     def peek(self):
12.         return self.items[len(self.items)-1]
13. 
    
14. def infixToPostfix(infixexpr):
15.     prec = {}
16.     prec["*"] = 3
17.     prec["/"] = 3
18.     prec["+"] = 2
19.     prec["-"] = 2
20.     prec["("] = 1
21.     opStack = Stack()
22.     postfixList = []
23.     tokenList = infixexpr.split()
24. 
    
25.     for token in tokenList:
26.         if token in "ABCDEFGHIJKLMNOPQRSTUVWXYZ" or token in "0123456789":
27.             postfixList.append(token)
28.         elif token == '(':
29.             opStack.push(token)
30.         elif token == ')':
31.             topToken = opStack.pop()
32.             while topToken != '(':
33.                 postfixList.append(topToken)
34.                 topToken = opStack.pop()
35.         else:
36.             while (not opStack.isEmpty()) and \
37.                (prec[opStack.peek()] >= prec[token]):
38.                   postfixList.append(opStack.pop())
39.             opStack.push(token)
40. 
    
41.     while not opStack.isEmpty():
42.         postfixList.append(opStack.pop())
43.     return " ".join(postfixList)
44. 
    
45. print(infixToPostfix("A * B + C * D"))

Kode Program konversi Infix ke Prefix :

class Stack:

    def __init__(self):

        self.items = []

    def isEmpty(self):

        return self.items == []

    def push(self, items):

        self.items.append(items)

    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 showList(self):

          return self.items

def infixToPrefix(infixexpr):

    

    prec = {'*':3, '/':3 , '+':2, '-':2 , '(':1}

    opStack = Stack()

    prefixList = []

    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":

            prefixList.append(token)

        elif token == '(':

            opStack.push(token)

        elif token == ')':

            topToken = opStack.pop()

            

            while topToken != '(':

                prefixList.append(topToken)

                topToken = opStack.pop()

        else:

            while (not opStack.isEmpty()) and \

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

                  prefixList.append(opStack.pop())

            opStack.push(token)

    while not opStack.isEmpty():

        prefixList.append(opStack.pop())

    prefixList = prefixList[::-1]

    return " ".join(prefixList)

print(infixToPrefix("A * B - C * D"))

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