Materi Infix, Prefix, dan Postfix dengan Stack - Struktur Data

Materi Infix, Prefix, dan Postfix dengan Stack

A. Pengertian
     Ada tiga bentuk penulisan notasi matematis di komputer, satu bentuk adalah yang umum digunakan manusia (sebagai input di komputer) yaitu infix, dan dua yang digunakan oleh komputer (sebagai proses), yaitu postfix dan infix. Berikut :
  1. Infix adalah cara penulisan ungkapan dengan meletakkan operator di antara dua operand dalam hal ini pemakaian tanda kurung sangat menentukan hasil operasi.
    - Contoh pemakaian infix adalah A+B, A+B-C, (A+B)*(C-D).
  2. Prefix adalah metode penulisan dengan meletakkan operator di depan operand dan tanpa menuliskan tanda kurung.
    - Contoh pemakaian prefix adalah  +AB, – +ABC, * + AB – CD.
  3. Postfix adalah metode penulisan dengan menuliskan operator setelah operand dan tanpa menuliskan tanda kurung.
    - Contoh penulisan sufix adalah AB + , AB + C – , AB + CD -*.


B. Konversi Infix to Prefix
Algoritma Konversi Infix to Prefix :

     Untuk mengonversi infiks ke ekspresi postfix merujuk ke artikel ini Stack | Set 2 (Infix to Postfix). Kami menggunakan yang sama untuk mengonversi Infix menjadi Awalan.
  1. Langkah 1: Membalikkan panjang ekspresi infix A + B * C akan menjadi C * B + A. Catatan sambil membalik masing-masing '(' akan menjadi ')' dan masing-masing ')' menjadi '('
  2. Langkah 2: Dapatkan ekspresi postfix dari ekspresi yang diubah. CB * A +.
  3. Langkah 3: Membalikkan ekspresi postfix, karena itu di awalan contoh kita adalah + A * BC.

Sources Code :

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


    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())

    return " ".join(postfixList)



infix = "A * ( B + C ) * D"
infix=infix[::-1]
infix=infix.split()
for i in range(len(infix)):
         if infix[i] == '(':
              infix[i]=')'
         elif infix[i] == ')':
              infix[i]='('
print(infix)
prefix=infixToPostfix(infix)
prefix=prefix[::-1]
print(prefix)

Hasil Run :

Python 3.5.2 (default, Nov 23 2017, 16:37:01) 
[GCC 5.4.0 20160609] on linux
Type "copyright", "credits" or "license()" for more information.
>>> 
======================== RESTART: /home/rejeb/xxx.py ========================
['D', '*', '(', 'C', '+', 'B', ')', '*', 'A']
* A * + B C D
>>>


C. Konversi Infix to Postfix

Algoritma Konversi Infix to Postfix
  1. Buat Stack kosong yang disebut opstack untuk menjaga operator. Buat daftar kosong untuk output.
  2. Konversikan masukan infix string ke daftar dengan menggunakan metode string split.
  3. Pindai daftar token dari kiri ke kanan.
    • Jika token adalah operan, tambahkan ke akhir daftar output.
    • Jika token adalah tanda kurung kiri, tekan pada opstack.
    • Jika token adalah tanda kurung yang tepat, buka opstack sampai kurung kiri yang sesuai dihapus. Tambahkan setiap operator ke bagian akhir daftar output.
    • Namun, pertama-tama, hapus semua operator yang sudah ada di opstack yang memiliki prioritas lebih tinggi atau sama dan tambahkan ke daftar output.
  4. Ketika ekspresi input telah diproses, periksa opstack.Tetiap operator masih di Stack dapat dihapus dan ditambahkan ke akhir daftar output.

Sources Code :

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()

    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())
    return " ".join(postfixList)

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

Hasil Run :

Python 3.5.2 (default, Nov 23 2017, 16:37:01) 
[GCC 5.4.0 20160609] on linux
Type "copyright", "credits" or "license()" for more information.
>>> 
======================== RESTART: /home/rejeb/xxx.py ========================
A B * C D * +
A B + C * D E - F G + * -
>>>

D. Evaluate Prefix dan Postfix
Menghitung angka dalam prefix dan postfix :

Algoritma Prefix Evaluation :

  1. Langkah 1: Letakkan pointer P di ujung akhir
  2. Langkah 2: Jika karakter di P an operan dorong ke Tumpukan
  3. Langkah 3: Jika karakter di P dan operator pop dua elemen dari Stack. Beroperasi pada elemen-elemen ini menurut operator, dan dorong hasilnya kembali ke Stack
  4. Langkah 4: Penurunan P sebesar 1 dan lanjutkan ke Langkah 2 selama di sana adalah karakter yang tersisa untuk dipindai dalam ekspresi.
  5. Langkah 5: Hasilnya disimpan di bagian atas Tumpukan,  kembalikan itu
  6. Langkah 6: Akhiri

Sources Code Prefix Evaluation :

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[::-1]:
        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 8'))

Hasil Run :

Python 3.5.2 (default, Nov 23 2017, 16:37:01) 
[GCC 5.4.0 20160609] on linux
Type "copyright", "credits" or "license()" for more information.
>>> 
======================== RESTART: /home/rejeb/xxx.py ========================
72
>>>


Algoritma Postfix Evaluation :
  1. Buat Stack kosong yang disebut operandStack.
  2. Konversikan string ke daftar dengan menggunakan metode string split.
  3. Pindai daftar token dari kiri ke kanan.
    • Jika token adalah operand, konversikan dari string ke integer dan dorong nilainya ke operandStack.
    • Lakukan operasi aritmatika Dorong pop pertama adalah operan kedua dan pop kedua adalah operan kedua. hasilkan kembali pada operandStack.
  4. Ketika ekspresi input telah benar-benar diproses, hasilnya adalah pada stack. Pop operandStack dan kembalikan nilainya.

Sources Code Postfix Evaluation:


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 * +'))

Hasil Run :

Python 3.5.2 (default, Nov 23 2017, 16:37:01) 
[GCC 5.4.0 20160609] on linux
Type "copyright", "credits" or "license()" for more information.
>>> 
======================== RESTART: /home/rejeb/xxx.py ========================
34
>>>


Comments

Post a Comment

Popular posts from this blog

Searching - Linier Search & Binary Search Python

Image
Kelompok: Sitti Suwaibah (170411100009) Wijanarko Putra Rajeb (170411100061)  Assalamualaikum Wr. Wb. Kali ini kita akan membagikan Materi dan beberapa script python tentang linier search dan binary search. Berikut scriptnya: ### Mencari Keberadaan Suatu Angka di Dalam List Data ### A. Metode Linier Search Linear search merupakan program search yang mudah dipahami, linear search memiliki kelebihan apabila data yang di cari letaknya pada data – data awal sehingga prosesnya berjalan cepat, namun apabila data yang di cari letaknya pada data terakhir maka pencarian lebih memakan waktu yang cukup lama pula. karena di linear search mengunjungi setiap elemen data yang ada.   1. Biasa ### myList = [1,5,10,15,20,25,30,2,6,8,9] # Example List cari = int(input("Masukkan Angka Yang Anda Cari : ")) # angka yang ingin dicari counter = 0 while counter != len(myList): if myList[counter] == cari: print("Found The Search Number.",counter) cou
Read more

Sorting Data 1 - Bubble Sort dan Selection Sort

Image
Sorting adalah pengurutan data dimana di dalam sorting ituada 2 macam proses sorting. Ada bubble sort sama selection sort. 1. Bubble Sort Adalah algoritma pengurutan sederhana yang berulang kali melewati daftar yang akan diurutkan, membandingkan setiap pasangan item yang berdekatan dan menukar mereka jika mereka berada di urutan yang salah. def BubbleSort(val): counter = 0 for passnum in range(len(val)-1,0,-1): for i in range(passnum): counter += 1 if val[i]>val[i+1]: val[i],val[i+1] = val[i+1],val[i] print(val) print('jumlah iterasinya',counter) DaftarAngka = [23,7,32,99,4,15,11,20] BubbleSort(DaftarAngka) Video Tutorial Bubble Sort https://goo.gl/r8EAA5 2. Selection Sort Menemukan nilai minimum dalam array dan memindahkannya ke posisi pertama. Langkah ini adalah pengulangan untuk nilai terendah kedua, lalu yang ketiga, dan seterusnya sampai array diurutkan. def SelectionSort(val):
Read more

Materi Hashing - Struktur Data

Image
Materi Hashing A. Pengertian      Hashing adalah proses pengindeksan dan pengambilan elemen (data) dalam struktur data untuk menyediakan cara yang lebih cepat untuk menemukan elemen menggunakan kunci hash. Hash Value=Key mod (n+1) B. Collision      Collision terjadi ketika dua item hash ke slot yang sama, kita harus memiliki metode sistematis untuk menempatkan item kedua dalam tabel hash. Memecahkan: - Open Addressing : dalam hal itu mencoba untuk menemukan slot atau alamat terbuka berikutnya di tabel hash. Linear Probbing : Kita melihat secara berurutan, slot demi slot, sampai kita menemukan posisi terbuka. Quadratic Probbing : Ini berarti bahwa jika nilai hash pertama adalah h, nilai berturut-turut adalah h + 1, h + 4, h + 9, h + 16. seterusnya - Closed Address (Separate Chaining)      Pada dasarnya separate chaining membuat tabel yang digunakan untuk proses hashing menjadi sebuah array of pointer yang masing-masing pointernya diikuti oleh sebuah linke
Read more