STACK AND QUEUE POSTFIX AND PREFIX

-


STACK AND QUEUE POSTFIX AND PREFIX

1.     STACK
Stack merupakan sebuah kumpulan data atau item dengan cara penambahan item baru serta penghapusan, selalu terjadi pada tempat atau ujung yang sama. Stack ini biasa di analogikan seperti tumpukan pada piring. Dimana kita mengambil maupun meletakkan piring selalu pada sisi atasnya. Walaupun sebenarnya kita bisa mengambil dan meletakkan piring di sisi bawah. Namun hal tersebut susah ya dilaksakan? Maka yang umum dan mudah adalah pada sisi atasnya. Dan ujung tempat data di tambah maupun di hapus, biasa disebut sebagai TOP. Dan sisi yang satunya, adalah BASE. Dan class Stack ini memiliki konsep LIFO (last in first out) atau dalam bahasa indonesianya adalah data yang terakhir masuk, maka ialah yang pertama akan dikeluarkan. 


OPERASI PADA STACK
class stack ini memiliki beberapa operasi yang akan kita buat nantinya, yaitu :

Ø  stack()membuat suatu stack baru yang kosong. Tidak memerlukan parameter dan mengembalikan suatu stack kosong.

Ø  push(item)menambahkan suatu item baru ke atas (top) dari stack. Perlu item dan tidak mengembalikan apapun.

Ø  pop()menghapus item teratas dari stack. Tidak perlu parameter dan mengembalikan item. Stack berubah.

Ø  peek()mengembalikan top item dari stack tetapi tidak menghapusnya. Tidak memerlukan parameter dan stack tidak berubah.

Ø  isEmpty()memeriksa apakah stack dalam keadaan kosong. Tidak memerlukan parameter dan mengembalikan nilai boolean.

Ø  size() mengembalikan jumlah item di dalam stack. Tidak memerlukan parameter dan mengembalikan suatu integer. 





SOURCE CODE UNTUK CLASS STACK
class Stack:

    def __init__(self):

        self.stack = []

    def isEmpty(self):

        return self.size()==0

    def push(self, val):

        return self.stack.append(val)

    def pop(self):

        if self.isEmpty():

            return None

        else:

            return self.stack.pop()

    def peek(self):

        if self.isEmpty():

            return None

        else:

            return self.stack[-1]

    def size(self):

        return len(self.stack)



2.     QUEUE
Queue (Antrian) adalah kumpulan data yang berurut dimana penambahan data baru berada di satu ujung bernama ekor atau rear. Sedangkan penghapusan data berada di ujung kepala atau front. Queue menggunakan metode pengurutan FIFO (First In, First Out) yaitu data yang masuk pertama maka data tersebut juga keluar pertama kali. Contoh implementasi dari Queue adalah Antrian sembako, permainan temukan orang dan lain sebagainya.



Class queue ini memiliki beberapa operasi yang akan kita buat nantinya, yaitu :

Ø  queue() membuat suatu antrian baru yang kosong. Tidak memerlukan parameter dan mengembalikan suatu antrian kosong.

Ø  enqueue(item) menambahkan suatu item baru ke ujung saru antrian. Perlu item dan tidak mengembalikan sesuatu.

Ø  dequeue() menghapus  item depan dari antrian. Tidak memerlukan parameter dan mengembalikan itemnya. Antrian termodifikasi.

Ø  isEmpty() menguji untuk melihat apakah antrian dalam keadaan kosong. Tidak memerlukan parameter dan mengembalian nilai boolean.

Ø  size() mengembalikan jumlah item yang ada di dalam antrian. Tidak memerlukan parameter dan mengembalikan suatu integer.



Source code untuk class queue :

class Queue:

    def __init__(self):

        self.queue = []

    def isEmpty(self):

        return self.size == 0

    def enqueue(self, val):

        return self.queue.insert(0,val)

    def dequeue(self):

        if self.isEmpty():

            return None

        else:

            return self.queue.pop()

    def size(self):

        return len(self.queue)

3.      Infix to Postfix


Source Codenya :

        class Stack:

    def __init__(self):

        self.items = []

        

    def isEmpty(self):

        return self.items == []

   

    def push(self, item): #push menambahkan

        self.items.append(item)

       

    def pop(self): #pop mengambil dari atas

        return self.items.pop()

   

    def peek(self): #peek melihat

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

   

def infixToPostfix(infixexpr):

    prec = {}

    prec["*"] = 3

    prec["/"] = 3

    prec["+"] = 2

    prec["-"] = 2

    prec["("] = 1

    opStack = Stack()

    postfixList = []

    tokenList = infixexpr.split()

    for i in tokenList(len(infix)):

        if infix[i]=='(':

            infix[i]==')'

        if infix [i]==')':

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

    return " ".join(postfixList)

infixexpr=input("teks=")

print(infixToPostfix(infixexpr))


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

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


4.      Infix to Prefix

Source codenya :

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

          return self.items


def infixToPrefix(infixexpr):

    prec = {}

    prec["*"] = 3

    prec["/"] = 3

    prec["+"] = 2

    prec["-"] = 2

    prec["("] = 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 )"))
Di post oleh :
1. FITRI ANISA (170411100014)

2. DHEA OKY SYAFITRI (170411100006)





Komentar

Posting Komentar

Postingan populer dari blog ini

Class and Object in Python

-
Class dan Objek Class Merupakan Struktur data yang bisa kita gunakan untuk mendefinisikan objek yang menyimpan data bersama-sama nilai-nilai dan perilaku (behavior). Kelas adalah suatu entitas yang merupakan bentuk program dari suatu abstraksi untuk permasalahan dunia nyata, dan instans dari class merupakan realisasi dari beberapa objek. contoh kelas : binatang, kendaraan, benda dsb. 2. objek merupakan Instance dari class. Jika class secara umum merepresentasikan (template) sebuah object, maka sebuah instance adalah representasi nyata dari class itu sendiri. 3. pada dasarnya ada 2 karakteristik yang utama pada sebuah objek : Objek memiliki attribut sebagai status yang disebut Stat Objek memiliki tingkahlaku yang kemudian disebut Method 4. keyword class diikuti dengan nama class yang kita inginkan. Lebih baik digunakan kata yang diawali huruf kapital. 5. Setiap method harus memiliki parameter self yang artinya method tersebut dim...
Baca selengkapnya

DOUBLE LINKED LIST

-
DOUBLE LINKED LIST 1.       PENGERTIAN DOUBLE LINKED LIST Double Linked List sama seperti  Single Linked List  merupakan sebuah tempat yang disediakan pada satu area memori tertentu untuk menyimpan data yang dikenal dengan sebutan node atau simpul. Akan tetapi, setiap node pada double linked list selain memiliki pointer yang menunjuk ke simpul berikutnya sehingga terbentuk satu untaian, juga memiliki pointer yang menunjuk ke simpul sebelumnya. Susunan berupa untaian model ini disebut Double Linked List.  2.       SOURCE CODE class Node:     def __init__(self,initdata):         self.data = initdata         self.next = None         self.previous = None     def getData(self):         return self.data  ...
Baca selengkapnya

GRAPH

-
GRAPH 1.      PENGERTIAN GRAPH Graph adalah kumpulan node (simpul) di dalam bidang dua dimensi yang dihubungkan dengan sekumpulan garis (sisi). Graph dapat digunakan untuk merepresentasikan objek-objek diskrit dan hubungan antara objek-objek tersebut. Representasi visual dari graph adalah dengan menyatakan objek sebagai node, bulatan atau titik (Vertex), sedangkan hubungan antara objek dinyatakan dengan garis (Edge). 2.      ISTILAH PADA GRAPH Terdapat beberapa istilah yang berkaitan dengan graph yaitu : Ø   Vertex Vertex yaitu himpunan node / titik pada sebuah graph . Ø   Edge Edge yaitu himpunan garis yang menghubungkan tiap node / vertex . Ø   Adjacent Adjacent yaitu Adalah dua buah titik dikatakan berdekatan ( adjacent ) jika dua buah titik tersebut terhubung dengan sebuah sisi. Ø   Weight Disebut sebuah graph berbobot ( weight graph ), apabila terdapat sebuah fungsi bobot bernilai real. Ø ...
Baca selengkapnya