Parse Tree Python

Parse Tree Python

Implementasi tree yang lengkap secara struktur dapat digunakan untuk menyelesaikan malasah ril, di antaranya adalah parse tree (pohon uraian).

Langkah pertama dalam pembangunan suatu parse tree Adalah memecah string ekspresi ke dalam daftar tokens. Ada 4 jenis token berbeda yang perlu diperhatikan: kurung left, kurung kanan, operator dan operan. Kita tahun bahwa kapanpun kita membaca kurung kiri kita

memulai suatu ekspresi baru, dan karena itu kita membuat suatu tree baru untuk menyesuaikan ekspresi tersebut. Sebaliknya, kapanpun kita membaca suatu kurung kanan, kita telah menyelesaikan suatu ekspresi. Kita juda mengetahui bahwa operan akan menjadi node daun (leave) dan anak-anak (children) dari operator-operatornya. Terakhir, kita mengetahui bahwa setiap operator akan mempunyai anak kiri dan kanan.

Berdasarkan informasi di atas kita dapat mendefinisikan 4 rule berikut:
1. Jika current token adalah '(', tambahkan node baru sebagai anak kiri (left child) dari current node, dan turunkan ke anak kiri tersebut.
2. Jika current token adalah operator dalam list ['+','-','/','*'], set nilai root dari current node ke operator yang direpresentasikan oleh current token. Tambahkan node baru sebagai anak nakan dari current node dan turunkan ke anak kanan tersebut.
3. Jika current token adalah suatu bilangan, set nilai root dari current node ke bilangan tersebut dan kembali ke induknya.
4. Jika current token adalah ')', pindahkan ke induk dari current node.

Sekarang mari kita manfaatkan 4 aturan di atas untuk menguji ekspresi matematika (3 + (4 * 5)). Ekspresi ini akan diurai ke dalam daftar token ['(', '3', '+', '(', '4', '*', '5' ,')',')']. Awalnya dimulai dengan suatu parse tree yang mengandung node root kosong.


Source Code :

from __future__ import print_function

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)

    

class Binarytree:

    def __init__(self,root):

        self.key = root

        self.leftChild = None

        self.rightChild = None

    def insertLeft(self,newNode):

        if self.leftChild == None :

            self.leftChild = Binarytree(newNode)

        else :

            t = Binarytree(newNode)

            t.leftChild = self.leftChild

            self.leftChild = t

    def insertRight(self,newNode):

        if self.rightChild == None :

            self.rightChild = Binarytree(newNode)

        else :

            t = Binarytree(newNode)

            t.rightChild = self.rightChild

            self.rightChild = t

    def getrightChild(self):

        return self.rightChild

    def getleftChild(self):

        return self.leftChild

    def getrootVal(self):

        return self.key

    def setrootVal(self,obj):

        self.key = obj

    def size(left):

        count = 0

        selfleft = self

        selfright = self

        while selfleft.getleftChild() != None or selfright.getrightChild() != None :

            count += 1

            if selfleft.getleftChild() != None:

                selfleft = selfleft.getleftChild()

            else :

                selfright = selfright.getrightChild()

        return count

    

def buildParseTree(fpexp):

    fplist = fpexp.split()

    pStack = Stack()

    eTree = Binarytree("")

    pStack.push(eTree)

    currentTree = eTree

    for i in fplist:

        if i == "(":

            currentTree.insertLeft("")

            pStack.push(currentTree)

            currentTree = currentTree.getleftChild()

        elif i not in ["+","-","*","/",")"]:

            currentTree.setrootVal(int(i))

            parent = pStack.pop()

            currentTree = parent

        elif i in ["+","-","*","/"]:

            currentTree.setrootVal(i)

            currentTree.insertRight("")

            pStack.push(currentTree)

            currentTree = currentTree.getrightChild()

        elif i == ")":

            currentTree = pStack.pop()

        else:

            return ("Error")

    return eTree

def Inorder(tree):

    if tree != None:

        Inorder(tree.getleftChild())

        print(tree.getrootVal(),end=" ")

        Inorder(tree.getrightChild())

def Preorder(tree):

    if tree != None:

        print(tree.getrootVal(),end=" ")

        Preorder(tree.getleftChild())

        Preorder(tree.getrightChild())

def Postorder(tree):

    if tree != None :

        Postorder(tree.getleftChild())

        Postorder(tree.getrightChild())

        print(tree.getrootVal(),end=" ")

pt = buildParseTree( "( ( 3 + ( 4 * 5 ) ) )" )

Inorder(pt)

print ()

Preorder(pt)

print ()

Postorder(pt)

Binary Tree Python

Binary Tree Python

Tree digunakan di banyak bidang informatika termasuk sistem operasi, pemrosessan bahasa alami, penggalian data web, grafika, sistem database dan jaringan komputer. Struktur data tree mempuyai suatu root (akar), branches (cabang) dan leaves (daun-daun).

Pada tree berbentuk list of lists (list di dalam list), kita menyimpan nilai dari node root sebagai elemen pertama dari list. Elemen kedua dari list akan merepresentasikan sub-tree kiri. Elemen ketiga adalah list lain yang mewakili sub-tree kanan. Tentang ilustrasikan struktur data ini, gambar 5.1 memperlihatkan tree sederhana beserta list yang mewakilinya.



Source Code :

from __future__ import print_function

class Binarytree:

    def __init__(self,root):

        self.key = root

        self.leftChild = None

        self.rightChild = None

    def insertLeft(self,newNode):

        if self.leftChild == None :

            self.leftChild = Binarytree(newNode)

        else :

            t = Binarytree(newNode)

            t.leftChild = self.leftChild

            self.leftChild = t

    def insertRight(self,newNode):

        if self.rightChild == None :

            self.rightChild = Binarytree(newNode)

        else :

            t = Binarytree(newNode)

            t.rightChild = self.rightChild

            self.rightChild = t

    def getrightChild(self):

        return self.rightChild

    def getleftChild(self):

        return self.leftChild

    def getrootVal(self):

        return self.key

    def size(self):

        count = 0

        selfleft = self

        selfright = self

        while selfleft.getleftChild() != None or selfright.getrightChild() != None :

            count += 1

            if selfleft.getleftChild() != None:

                selfleft = selfleft.getleftChild()

            else :

                selfright = selfright.getrightChild()

        return count

r = Binarytree('a')

r.insertLeft('b')

r.insertRight('c')

r.getleftChild().insertLeft('d')

r.getleftChild().insertRight('e')

r.getleftChild().getrightChild().insertLeft('f')

r.getleftChild().getrightChild().insertRight('g')

print(r.getrootVal())

print(r.getleftChild().getrootVal())

print(r.getleftChild().getleftChild().getrootVal())

print(r.size())

Double Linked List Python

Double Linked List Python

from __future__  import print_function

class Node:

    def __init__(self,initdata):

        self.data = initdata

        self.next = None

        self.prev = None

    

    def getData(self):

        return self.data

    def getNext(self):

        return self.next

        

    def getPrev(self):

        return self.prev

    def setData(self,newdata):

        self.data = newdata

    def setNext(self,newnext):

        self.next = newnext

        

    def setPrev(self,newprev):

        self.prev = newprev

class Orderlist:

    def __init__(self):

        self.head = None

        

    def show(self):

        current = self.head

        print ("Head ->", end = " ")

        while current != None and current.getNext() != None:

            print (current.getData(), end = "<->")

            current = current.getNext()

        else :

            print (current.getData(), end = "-> None")

        print ("\nNone <-")

    def isEmpty(self):

        return self.head == None

    def add(self,item):

        temp = Node(item)

        temp.setNext(self.head)

        temp.setPrev(None)

        self.head = temp

        prev1 = temp.getData()

        next1 = temp.getNext()

        if next1 != None:

            next1.setPrev(temp)

            

    def size(self):

        current = self.head

        count = 0

        while current != None:

            count = count + 1

            current = current.getNext()

        return count

        

    def search(self,item):

        current = self.head

        found = False

        while current != None and not found:

            if current.getData() == item:

                found = True

            else :

                current = current.getNext()

        return found

    

    def remove(self,item):

        current = self.head

        previous = None

        found = False

        while current != None and not found:

            if current.getData()== item:

                found = True

            else :

                previous = current

                current = current.getNext()

                if current == None:

                    next1 = None

                else:                

                    next1 = current.getNext()

                    

        if previous == None:

            self.head = current.getNext()

        else:

            if current == None:

                previous.setNext(None)

            else :

                previous.setNext(current.getNext())

            if next1 != None:

                next1.setPrev(current.getPrev())

                

    def mainmenu(self):

        print ("=".center(80,"="))

        print("Selamat Datang Di Aplikasi (Double Linked List)".upper().center(80))

        print("By : Moh. Irsad 170411100024".upper().center(80))

        print ("=".center(80,"="))

        stop = False

        while not stop: 

            print ("=".center(30,"="))

            print ("Menu Aplikasi Linked List")

            print ("=".center(30,"="))

            print ("1. Tambah data")

            print ("2. Remove data")

            print ("3. Cari data")

            print ("4. Jumlah data")

            print ("5. Tampil data")

            print ("=".center(30,"="))

            opsi = int(input("Masukkan pilihan anda : "))

            print ()

            

            if opsi == 1 :

                print ("=".center(30,"="))

                print ("Tambah Data".center(30))

                print ("=".center(30,"="))

                n = int(input("Berapa banyak data yang ingin anda masukan : "))

                for i in range (n):

                    i +=1

                    data = int(input("Masukkan data ke- %d : "% i))

                    angka.append(data)

                angka.sort()

                angka.reverse()

                for j in angka:

                    self.add(j)

                print ("=".center(40,"=")) 

                print ("Data Berhasil Ditambahkan".center(40))

                print ("=".center(40,"="))

                

            elif opsi == 2:

                print ("=".center(30,"="))

                print ("Remove Data".center(30))

                print ("=".center(30,"="))

                data = int(input("masukkan data yang ingin anda remove : "))

                self.remove(data)

                if data in angka:

                    print ("=".center(40,"="))

                    print ("Data berhasil di remove!!!".center(40))

                    print ("=".center(40,"="))

                else :

                    print ("=".center(40,"="))

                    print ("Data yang ingin anda remove tidak ada".center(40))

                    print ("=".center(40,"="))

                    

            elif opsi == 3:

                print ("=".center(30,"="))

                print ("Cari Data".center(30))

                print ("=".center(30,"="))

                data = int(input("Masukkan data yang ingin anda cari : "))

                status = self.search(data)

                if status == True:

                    print ("=".center(40,"="))

                    print ("Data Ditemukan".center(40))

                    print ("=".center(40,"="))

                else :

                    print ("=".center(40,"="))

                    print ("Data yang anda cari tidak ada".center(40))

                    print ("=".center(40,"="))

                    

            elif opsi == 4:

                print ("=".center(30,"="))

                print ("Jumlah Data".center(30))

                print ("=".center(30,"="))

                print ("Panjang data : ", self.size())

                print ("=".center(30,"="))

                

            elif opsi == 5:

                print ("=".center(30,"="))

                print ("Tampilkan Data".center(30))

                print ("=".center(30,"="))

                if angka == []:

                    print ("Data Masih Kosong")

                else :

                    self.show()

                    

            else :

                print ("=".center(40,"="))

                print ("Pilihan yang anda masukan tidak ada".center(40))

                print ("=".center(40,"="))

                

            if opsi != 5:          

                opsi2 =raw_input("Apakah anda ingin mencoba opsi lain? (Yes/No) :")

                if opsi2 == 'No':

                          stop = True

                          print("=".center(80,"="))

                          print("Terimakasih telah mencoba aplikasi kami.".upper().center(80))

                          print("Moh. Irsad 170411100024".center(80))

                          print("=".center(80,"="))

#Main_Program                          

angka = []

mylist = Orderlist()

mylist.mainmenu()

Single Linked List Python

Single Linked List Python

" linked list bisa kita katakan juga sebagai rantai. karena linked list adalah struktur data yang terdiri dari urutan - urutan elemen yang saling terhubung satu sama lain yang membentuk seperti rantai. dimana setiap elemennya memiliki alamat yang menyimpan alamat dari elemen selanjutnya". sehingga di dalam setiap elemen terdapat dua informasi.. yaitu isi dari setiap elemen dan juga alamat elemen selanjutnya.

from __future__  import print_function

class Node:

    def __init__(self,initdata):

        self.data = initdata

        self.next = None

    

    def getData(self):

        return self.data

    def getNext(self):

        return self.next

    def setData(self,newdata):

        self.data = newdata

    def setNext(self,newnext):

        self.next = newnext

class Orderlist:

    def __init__(self):

        self.head = None

        

    def show(self):

        current = self.head

        print ("Head ->", end = " ")

        while current != None:

            print (current.getData(), end = " -> ")

            current = current.getNext()

        print ("None")

    def isEmpty(self):

        return self.head == None

    def add(self,item):

        temp = Node(item)

        temp.setNext(self.head)

        self.head = temp

        

    def size(self):

        current = self.head

        count = 0

        while current != None:

            count = count + 1

            current = current.getNext()

        return count

        

    def search(self,item):

        current = self.head

        found = False

        while current != None and not found:

            if current.getData() == item:

                found = True

            else :

                current = current.getNext()

        return found

    def remove(self,item):

        current = self.head

        previous = None

        found = False

        while current != None and not found:

            if current.getData()== item:

                found = True

            else :

                previous = current

                current = current.getNext()

                if current == None:

                    next1 = None

                else:                

                    next1 = current.getNext()

                    

        if previous == None:

            self.head = current.getNext()

        else:

            if current == None:

                previous.setNext(None)

            else :

                previous.setNext(current.getNext())

            if next1 != None:

                next1 = current.getNext()

        

    def mainmenu(self):

        print ("=".center(80,"="))

        print("Selamat Datang Di Aplikasi (Single Linked List)".upper().center(80))

        print("By : Moh. Irsad 170411100024".upper().center(80))

        print ("=".center(80,"="))

        stop = False

        while not stop: 

            print ("=".center(30,"="))

            print ("Menu Aplikasi Linked List")

            print ("=".center(30,"="))

            print ("1. Tambah data")

            print ("2. Remove data")

            print ("3. Cari data")

            print ("4. Jumlah data")

            print ("5. Tampil data")

            print ("=".center(30,"="))

            opsi = int(input("Masukkan pilihan anda : "))

            print ()

            

            if opsi == 1 :

                print ("=".center(30,"="))

                print ("Tambah Data".center(30))

                print ("=".center(30,"="))

                n = int(input("Berapa banyak data yang ingin anda masukan : "))

                for i in range (n):

                    i +=1

                    data = int(input("Masukkan data ke- %d : "% i))

                    angka.append(data)

                angka.sort()

                angka.reverse()

                for j in angka:

                    self.add(j)

                print ("=".center(40,"=")) 

                print ("Data Berhasil Ditambahkan".center(40))

                print ("=".center(40,"="))

            elif opsi == 2:

                print ("=".center(30,"="))

                print ("Remove Data".center(30))

                print ("=".center(30,"="))

                data = int(input("masukkan data yang ingin anda remove : "))

                self.remove(data)

                if data in angka:

                    print ("=".center(40,"="))

                    print ("Data berhasil di remove!!!".center(40))

                    print ("=".center(40,"="))

                else :

                    print ("=".center(40,"="))

                    print ("Data yang ingin anda remove tidak ada".center(40))

                    print ("=".center(40,"="))

                    

            elif opsi == 3:

                print ("=".center(30,"="))

                print ("Cari Data".center(30))

                print ("=".center(30,"="))

                data = int(input("Masukkan data yang ingin anda cari : "))

                status = self.search(data)

                if status == True:

                    print ("=".center(40,"="))

                    print ("Data Ditemukan".center(40))

                    print ("=".center(40,"="))

                else :

                    print ("=".center(40,"="))

                    print ("Data yang anda cari tidak ada".center(40))

                    print ("=".center(40,"="))

                    

            elif opsi == 4:

                print ("=".center(30,"="))

                print ("Jumlah Data".center(30))

                print ("=".center(30,"="))

                print ("Panjang data : ", self.size())

                print ("=".center(30,"="))

                

            elif opsi == 5:

                print ("=".center(30,"="))

                print ("Tampilkan Data".center(30))

                print ("=".center(30,"="))

                if angka == []:

                    print ("Data Masih Kosong")

                else :

                    self.show()

                    

            else :

                print ("=".center(40,"="))

                print ("Pilihan yang anda masukan tidak ada".center(40))

                print ("=".center(40,"="))

                

            if opsi != 5:          

                opsi2 = raw_input("Apakah anda ingin mencoba opsi lain? (Yes/No) :")

                if opsi2 == 'No':

                          stop = True

                          print("=".center(80,"="))

                          print("Terimakasih telah mencoba aplikasi kami.".upper().center(80))

                          print("Moh. Irsad 170411100024".upper().center(80))

                          print("=".center(80,"="))

            

#Main_Program

angka = []

mylist = Orderlist()

mylist.mainmenu()

Mengukur kecepatan dalam methode hashing

Siapakah yang paling cepat antara Open Address dengan Close Address :

Source Code :

from __future__ import print_function

import time

import random

waktu = time.time() 

print ("Waktu sekarang :", waktu)

print("=".center(80,"="))

print("Tugas Praktikum 4".center(80))

print("=".center(80,"="))

print()

print("=".center(80,"="))

print("No.1 Linear Probbing".center(80))

print("=".center(80,"="))

table = [None]*110

def Linear(x):

    return x % 11

def insert(table,keys,value):

    index = Linear(keys)

    if table[index]==None:

        table[index]=value

    else:

        tumbukan=index

        found = False

        ind = tumbukan + 1

        if ind >= len(table)-1:

            ind = 0

        while (ind<=len(table)-1) and not(found):

            if table[ind]== None:

                found = True

                table[ind]=value

            ind +=1

    return table

keys = []

for i in range (0,100):

    keys.append(random.randint(11,111))

value = list(keys)

for j in range(0,100):

    linear = insert(table,keys[j],value[j])

print (linear)

waktu1 = time.time() 

print ("Waktu sekarang :", waktu1)

print("=".center(80,"="))

print("Quadratic Probbing".center(80))

print("=".center(80,"="))

table1 = [None]*100

def Quadrat(x):

    return x% 11

def insert1(table1,keys1,value1):

    index = Quadrat(keys1)

    if table1[index]==None:

        table1[index]=value1

    else:

        tumbukan=index

        found = False

        ind = tumbukan + 1

        if ind >= len(table1)-1:

            ind = 0

        i = 1

        while (ind<=len(table1)-1) and not(found):

            i+=1

            if table1[ind]== None:

                found = True

                table1[ind]=value1

            ind = (ind+(i**2))

    return table1

keys1 = list(keys)

value1 = list(keys)

for j in range(0,100):

    quadratic=insert1(table1,keys1[j],value1[j])

print (quadratic)

waktu2 = time.time() 

print ("Waktu sekarang :", waktu2)

print("=".center(80,"="))

print("Chaining(Close Address)".center(80))

print("=".center(80,"="))

table2 = [[]]*20

def Chaining(x):

    return x % 11

def insert2(table2,keys2,value2):

    index = Chaining(keys2)

    if table2[index]==[]:

        table2[index]=[value2]

    else:

        table2[index].append(value2)

    return table2

keys2 = list(keys)

value2 = list(keys)

for j in range(0,100):

    chaining = insert2(table2,keys2[j],value2[j])

print (chaining)

waktu3 = time.time() 

print ("Waktu sekarang :", waktu3)

print("=".center(80,"="))

print("No.2 Methode yang Paling Cepat".center(80))

print("=".center(80,"="))

if waktu2-waktu1 > waktu3-waktu2 < waktu1-waktu :

    print ("Metode Chaining Yang Paling Cepat".upper().center(80))

elif waktu2-waktu1 == waktu3-waktu2:

    print ("Methode Chaining dengan Quadratic sama-sama cepat".upper().center(80))

else:

    print ("Methode Quadratic Paling Cepat".upper().center(80))

Silahkan Mencoba dan tentukan mana yang paling cepat...

Hashing Python

Hashing pada Python

Hashing adalah proses pengindeksan dan pengambilan elemen (data) dalam sebuah datastructure untuk menyediakan cara yang lebih cepat dalam menemukan elemen menggunakan kunci hash.

Collision = Ketika dua item hash ke slot yang sama, kita harus memiliki metode sistematis untuk menempatkan item kedua dalam tabel hash.
Memecahkan:

A. Open Address: dalam hal itu mencoba untuk menemukan slot atau alamat terbuka berikutnya di tabel hash.

1. Linear Probbing: kita melihat secara berurutan, slot demi slot, sampai kita menemukan posisi terbuka.

Source Code :

table = [None]*110
def Linear(x):
    return x % 11
def insert(table,keys,value):
    index = Linear(keys)
    if table[index]==None:
        table[index]=value
    else:
        tumbukan=index
        found = False
        ind = tumbukan + 1
        if ind >= len(table)-1:
            ind = 0
        while (ind<=len(table)-1) and not(found):
            if table[ind]== None:
                found = True
                table[ind]=value
            ind +=1
    return table
keys = []
for i in range (0,100):
    keys.append(random.randint(11,111))
value = list(keys)
for j in range(0,100):
    linear = insert(table,keys[j],value[j])

print (linear)

2. Qudratic Probbing: Ini berarti bahwa jika nilai hash pertama adalah h, nilai berturut-turut adalah h + 1, h + 4, h + 9, h + 16. seterusnya

Source code :

table1 = [None]*100 def Quadrat(x): return x% 11 def insert1(table1,keys1,value1): index = Quadrat(keys1) if table1[index]==None: table1[index]=value1 else: tumbukan=index found = False ind = tumbukan + 1 if ind >= len(table1)-1: ind = 0 i = 1 while (ind<=len(table1)-1) and not(found): i+=1 if table1[ind]== None: found = True table1[ind]=value1 ind = (ind+(i**2)) return table1 keys1 = list(keys) value1 = list(keys) for j in range(0,100): quadratic=insert1(table1,keys1[j],value1[j]) print (quadratic)

B. Close Address

Chaining = memungkinkan banyak item ada di lokasi yang sama dalam tabel hash. Ketika tabrakan terjadi, item tersebut masih ditempatkan di slot yang tepat dari tabel hash.

Source Code :

table2 = [[]]*20
def Chaining(x):
    return x % 11
def insert2(table2,keys2,value2):
    index = Chaining(keys2)
    if table2[index]==[]:
        table2[index]=[value2]
    else:
        table2[index].append(value2)
    return table2
keys2 = list(keys)
value2 = list(keys)
for j in range(0,100):
    chaining = insert2(table2,keys2[j],value2[j])
print (chaining)

Selamat Mencoba...

Infix To Prefix + Evaluasi

Infix To Prefix pada Python

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 replace(data):

    for i in range(len(data)):

        if data[i]=='(':

            data[i]=')'

        elif data[i]==')':

            data[i]='('

    return data

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)

def postfixEval(postfixExpr):

    operandStack = Stack()

    tokenList = postfixExpr

    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

#Main Program

infix = input("Masukan : ")

a = infix.split()

Data = []

for i in range (len(a)):

    Data.append(a[i])

data2= Data[::-1]

hasil = replace(data2)

total1 = infixToPostfix(hasil)

total = total1[::-1]

print (total)

Preval = input("Masukan : ")

b = Preval.split()

Data2 = []

for i in range (len(b)):

    Data2.append(b[i])

Datum = Data2[::-1]

eval1 = postfixEval(Datum)

print (eval1)

Infix To Postfix + Evaluasi

Infix To Postfix pada Python

from __future__ import print_function

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 infixToPostfix(infixexpr):

    prec = {}

    prec["*"] = 3

    prec["/"] = 3

    prec["+"] = 2

    prec["-"] = 2

    prec["("] = 1

    opStack = Stack()

    postfixList = []

    tokenList = infixexpr.split()  

    print (tokenList)

    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)

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

# Infix To Postfix

data = input("Masukan Infix (Dalam bentuk String dan tambahan spasi): ")

postfix = infixToPostfix(data)

print (postfix)

# Postfix Evaluasi

data2 = input("Masukan Postfix (Dalam bentuk Angka dan tambahan spasi): ")

infix = postfixEval(data2)

print (infix)

Implementasi Stack terhadap Infix, Prefix, dan Postfix

Infix To Postfix + Evaluasi

Dalam struktur data yang kita pelajari secara umum ada 3 notasi operasi yang dilakukan untuk suatu operasi aritmatika,yaitu Prefix,Infix,dan postfix.Dan untuk mengetahui notasi-notasi yang diatas itu,sebelumnya kita harus mengenal dan mengetahui indikator yang ada di notasi itu tersebut.

Notasi ini terbentuk dari Operand dan Operator.
Operand adalah data atau nilai yang membantu dalam proses,sedangkan Operasi adalah fungsi yang digunakan dalam proses.

contohnya:
A+B*C
2 + 5 * 3
Keterangan: A ,B ,C ,2 ,3 ,5 adalah Operand.
+,*  adalah Operator.

   Setelah kita mengenal dan mengetahui dengan Operand dan Operator, maka mari kita mengenal juga tingkat/ level yang ada didalam notasi tersebut:
-( ) (Kurung).
- ^ (Pangkat).
- * / (Perkalian / Pembagian).
- + - (Penjumlahan / Pengurangan).

Notasi ada 3 jenis, yaitu Prefix,Infix dan Postfix yang seperti kita ketahui di atas:

1.Prefix adalah notasi yang terbentuk atas operator dengan operand, dimana oprator didepan operand.
   contoh: A + B * C (infix).
   maka notasi prefixnya adalah: +A*BC.

   Pemecahannya:

                A+B*C

        Diketahui ada 3 operand yaitu: A, B, C dan 2 operand yaitu: +, *.proses dimulai dengan melihat dari hirarkhi oprator.Contoh diatas operator yang tertinggi adalah * kemudian +. Tanda * diapit oleh 2 operand yaitu B*C, prefixnya dengan menggabungkan operand dan memindahkan operator ke depan dari operand,sehingga fungsi B*C, notasi prefixnya menjadi *BC.

Sehingga hasil sementara dari notasi prefix adalah:
      A+*BC

        Selanjutnya mencari prefix untuk operator yang berikutnya yaitu  +, cara yang dilakukan sama seperti diatas, operator + diapit oleh operand, yaitu A dan *BC, gabungkan operand,sehingga menjadi A*BC,lalu pindahkan operator kedepan operand,sehingga hasil akhir menjadi :
     +A*BC.


2.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


3.Postfix adalah notasi yang membentuk atas operator dengan operand, dimana operator berada dibelakang operand.
   Contoh : A + B * C ( infix).
maka notasi postfix adalah ABC*+.

Stack, Queue, dan Dequeue Python

Stack, Queue, dan Dequeue pada Python

Stack (disebut pula “push-down stack”) adalah koleksi berurut dari item-item dimana
penambahan item baru dan penghapusan item yang telah ada selalu terjadi di ujung yang
sama. Ujung ini dinamakan sebagai “top.” Ujung berlawanan dari top dikenal sebagai “base.”
Stack diurutkan mengikuti konsep LIFO (last in first out). Berikut ini adalah beberapa operasi
terhadap stack:

- 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.

Contoh Source code Stack():

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)
print ("=".center(42,"="))       
print ("Stack")
print ("=".center(42,"="))
print()
s = Stack()
s.push("Hello")
s.push("World")

while not s.isEmpty():
    print(s.pop())

Queue atau antrian adalah suatu koleksi item berurut dimana penambahan item baru terjadi
di satu ujung bernama “ekor” (rear) dan penghapusan terjadi pada ujung lainnya yang
dinamakan “kepala” (front). Queues menggunakan pengurutan FIFO. Berikut ini adalah
beberapa operasi Queue:

- 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.

Contoh Source code Queue():

class Queue:
    def __init__(self):
        self.items = []

    def isEmpty(self):
        return self.items==[]

    def enqueue (self,items):
        self.items.insert(0,items)

    def dequeue(self):
        return self.items.pop()

    def size(self):
        return len(self.items)
     
print("Queue")
print ("=".center(42,"="))
print ()
q = Queue()
q.enqueue("Hello")
q.enqueue("World")
q.enqueue("Python3")

while not q.isEmpty():
    print(q.dequeue())

Deque (Deantrian), dikenal juga sebagai antrian berujung dua (double-ended), adalah suatu koleksi item terurut serupa dengan queue. Perbedaannya? Sifat tidak terikat untuk penambahan dan penghapusan item-item dari antrian. Item baru dapat ditambahkan ke depan atau belakang. Karena itu, item yang ada dapat dihapuskan dari salah satu ujung. Struktur linier hibrida ini menyediakan semua kapabilutas stack dan antrian dalam satu struktur data.

- deque() membuat suatu deque baru yang kosong. Tidak perlu parameter dan mengembalikan suatu deque kosong.
- addFront(item) menambahkan suatu item baru ke depan dari deque. Perlu item dan tidak mengembalikan apapun.
- addRear(item) menambahkan suatu item baru ke ekor dari deque. Perlu item dam tidak mengembalikan sesuatu.
- removeFront() menghapus item depan dari deque. Tidak perlu parameter dan mengembalikan item. Deque termodifikasi.
- removeRear() menghapus item ujung (ekor) dari deque. Tidak perlu parameter dan mengembalikan item. Deque berubah.
- viewFront() menampilkan item depan dari deque.
- viewRear() menampilkan ujung (ekor) dari deque.
- isEmpty() menguji apakah deque dalam kondisi kosong. Tidak perlu parameter dan mengembalikan suatu

Contoh Source Code dequeue():

class Dequeu:
    def __init__(self):
        self.items = []
       
    def isEmpty(self):
        return self.items == []
       
    def addFront(self,items):
        self.items.insert(0,items)
       
    def addRear(self,items):
        self.items.append(items)
       
    def removeFront(self):
        return self.items.pop()
       
    def removeRear(self):
        return self.items.pop(0)
       
    def vievFront(self):
        return self.items[0]
       
    def viewRear(self):
        return self.items[len(self.items)-1]
       
print ("=".center(42,"="))
print ("Dequeu")
print ("=".center(42,"="))
d = Dequeu()
d.isEmpty()
d.addFront("d")
d.addFront("a")
d.addFront("s")
d.addFront("r")
d.addFront("I")

while not d.isEmpty():
    print(d.removeRear())

Pahami dan banyak-banyaklah mencoba...

Shell Sort Python

Shell Sort pada Pyhton

Hal ini dapat dilihat sebagai generalisasi penyortiran dengan pertukaran (bubble sort) atau penyortiran dengan penyisipan (semacam penyisipan). Metode ini dimulai dengan menyortir pasangan elemen yang berjauhan satu sama lain, lalu secara progresif mengurangi jarak antar elemen yang akan dibandingkan. Dimulai dengan elemen yang berjauhan, ia dapat memindahkan beberapa elemen di luar tempat ke posisi lebih cepat daripada pertukaran tetangga terdekat yang sederhana.

N = 8

Gap : 8/2 = 4

Compare:

0-4

1-5

2-6

3-7

Gap : 4/2 = 2

Compare:

0-2    4-6

1-3    5-7

2-4

3-5

Gap : 2/2 = 1

Insertion Sort

Contoh Source Code Shell Sort :

from __future__ import print_function

def shellSort(alist):

    sublistcount = len(alist)//2

    while sublistcount > 0:

      for startposition in range(sublistcount):

        gapInsertionSort(alist,startposition,sublistcount)

      sublistcount = sublistcount // 2

def gapInsertionSort(alist,start,gap):

    for i in range(start+gap,len(alist),gap):

        currentvalue = alist[i]

        position = i

        while position>=gap and alist[position-gap]>currentvalue:

            alist[position]=alist[position-gap]

            position = position-gap

        alist[position]=currentvalue

alist = [35,33,42,10,14,19,27,44]

shellSort(alist)

print(alist)

Selamat Mencoba...