REKAYASA PERANGKAT LUNAK PEMBELAJARAN POHON EKSPRESI (EXPRESSION TREE)

Techno.COM, Vol. 10, No. 4, November 2011: 153-161

REKAYASA PERANGKAT LUNAK PEMBELAJARAN POHON EKSPRESI (EXPRESSION TREE) Sumardi Program Studi Teknik Informatika, Fakultas Ilmu Komputer Universitas Dian Nuswantoro Jl. Nakula I No. 5-11 Semarang 50131 Telp : (024) 3517261, Fax : (024) 3520165 E-mail : [email protected]

Abstract Tree expression (expression tree) is a binary tree (binary tree) where the leaves contain operands contained in an arithmetic expression and roots contain operators contained in the arithmetic expression. The process of reading from the expression tree starting from the leftmost leaf to the main root. Operands and operators who are at lower levels will be read first. Writing an arithmetic expression consists of three forms, namely forms of Prefix, Suffix (Postfix) and infix. In the form of Prefix, the operator is written in front of operandnya, and in the form of Suffix (Postfix), the operator is written on the back of operandnya. While the infix form is a normal form of writing arithmetic expressions. Based on the research made, a learning software is designed to describe the expression tree (expression tree) of an arithmetic expression that are input. After testing the system turns the system can work well, but still there are some things that should be corrected and added that the software is becoming more perfect. Keywords : Expression tree, Prefix, Suffix, Postfix,Infix

dalam bahasa mesin, terlebih lagi karena setiap jenis komputer mempunyai bahasa mesin sendiri yang berbeda dari satu komputer ke komputer lain.

1. PENDAHULUAN Suatu komputer dapat melaksanakan sesuatu bila kepadanya diberikan sederetan perintah/instruksi yang dimengertinya yang diurut secara logika. Deretan perintah ini disebut “program”. Sekumpulan aturan-aturan dalam membuat program disebut sebagai bahasa pemrograman (Programming Language). Karena komputer itu adalah suatu mesin, maka insruksi dan bahasa yang dimengerti olehnya adalah juga instruksi dan bahasa mesin. Bahasa mesin pada dasarnya hanya mengandung dua simbol yaitu simbol biner 0 dan 1 sehingga sangat sulit bagi manusia membuat program untuk komputer

Untuk memudahkan manusia membuat program komputer, telah diciptakan bermacam-macam bahasa pemrograman. Secara garis besar, bahasa pemrograman dapat dibagi menjadi dua bagian besar yaitu, 1. Bahasa Pemrograman Tingkat Rendah (Low Level Language), contohnya bahasa pemrograman Assembly. 2. Bahasa Pemrograman Tingkat Tinggi (High Level Language), contohnya bahasa pemrograman

153


FORTRAN, COBOL, BASIC, Pascal, RPG, C dan sebagainya. Kelemahan semua bahasa pemrograman ini adalah dibutuhkannya proses penerjemah dan sarana penerjemah berupa Assembler, Compiler atau Interpreter. Selain itu, program yang dibuat dengan menggunakan bahasa pemrograman tingkat tinggi pada umumnya tidak dapat menjangkau keseluruhan bagian komputer dimana program tersebut dilaksanakan. Program yang dapat menjangkau dan memanfaatkan seluruh kemampuan komputer hanyalah yang dibuat dalam bahasa mesin atau bahasa Assembly. Tujuan dari pembuatan bahasa pemrograman tingkat tinggi pada awalnya hanya ditujukan untuk menyelesaikan ekspresi aritmatika. Sebuah bahasa pemrograman dikatakan baik apabila mampu untuk memberikan keleluasaan kepada para programmer untuk menuliskan ekspresi aritmatika dengan ketentuan yang hampir sama seperti penulisan matematika secara manual. Sebuah compiler dikatakan berkompeten apabila mampu untuk membaca ekspresi – ekspresi berikut ini, (x + y) * exp(x – z) – 4.0 a * b + c / d – c * (x + y) not (p and q) or (x <= 7.0) Pohon ekspresi (expression tree) adalah sebuah pohon biner (binary tree) dimana daun berisi operand yang terdapat dalam ekspresi aritmatika dan akar berisi operator yang terdapat dalam ekspresi aritmatika tersebut. Proses pembacaan dari pohon ekspresi dimulai dari daun paling kiri hingga akar utama. Operand dan operator yang berada pada level bawah akan dibaca terlebih dahulu. Penelusuran pohon ekspresi ditujukan untuk menyelesaikan ekspresi aritmatika. Penulisan ekspresi aritmatika terdiri dari 3 bentuk, yaitu

154

bentuk Prefix, Suffix (Postfix) dan Infix. Dalam bentuk Prefix, operator ditulis di depan dari operandnya, dan dalam bentuk Suffix (Postfix), operator ditulis di belakang dari operandnya. Sedangkan bentuk Infix merupakan bentuk penulisan normal dari ekspresi aritmatika. 2. TINJAUAN PUSTAKA Ekspresi Aritmatika Sebuah ekspresi aritmatika terdiri dari operand dan operator. Operator dalam ekspresi aritmatika dapat dibagi menjadi 2 jenis, yaitu : Binary operator (operator pasangan) dan Unary operator (operator tunggal) Binary operator adalah operator yang memiliki 2 buah operand (diapit oleh 2 buah operand), sedangkan unary operator adalah operator yang hanya memiliki 1 buah operand (diikuti oleh sebuah operand). Operator – operator yang termasuk dalam binary operator adalah operator penjumlahan (+), pengurangan (-), perkalian (*), pembagian (/), modulo (mod), divisor (div), pemangkatan (^), operator logika AND, operator logika OR, dan operator perbandingan (seperti operator lebih besar, lebih kecil, sama dengan, lebih besar sama dengan, lebih kecil sama dengan, dan tidak sama dengan). Sedangkan operator yang termasuk dalam unary operator adalah operator minus (~), operator faktorial (!), operator trigonometri (seperti operator sinus, cosinus, tangen, cotangen, secan, dan cosecan), operator logika NOT, operator exponential (exp) dan fungsi logaritma (log). Prioritas/kedudukan dari masing – masing operator (baik unary operator maupun binary operator) dari tinggi ke rendah adalah sebagai berikut,


1. Operator pemangkatan (^) dan semua unary operator. 2. Operator perkalian (*), pembagian (/), modulo (mod) dan divisor (div). 3. Operator penjumlahan (+) dan pengurangan (-). 4. Operator perbandingan, yaitu operator lebih besar, lebih kecil, sama dengan, lebih besar sama dengan, lebih kecil sama dengan, dan tidak sama dengan. 5. Operator logika NOT. 6. Operator logika AND dan OR. 7. Assignment Operator (=). Ekspresi aritmatika akan diselesaikan berdasarkan urutan prioritas dari operator di atas dengan ketentuan operator yang memiliki prioritas yang lebih tinggi akan diselesaikan terlebih dahulu. Tahapan – tahapan penyelesaian suatu ekspresi aritmatika dapat direpresentasikan dalam bentuk graph yang dinamakan pohon ekspresi (expression tree). Notasi/Penulisan Ekspresi Aritmatika Polish Notation diperkenalkan oleh seorang ahli matematika Polandia bernama Jan Lukasiewicz. Polish Notation merupakan notasi penulisan ekspresi aritmatika. Polish Notation terdiri dari 3 bentuk, yaitu : a. Prefix b. Suffix (Postfix) c. Infix Infix Bentuk infix merupakan bentuk penulisan normal dari ekspresi aritmatika. Suatu infix dapat berupa operand tunggal, atau gabungan dari unary operator dengan infix, ataupun berupa gabungan dari binary operator

155

dengan dua buah infix. Diagram bentuk infix dapat dilihat pada gambar di bawah ini. Prefix Bentuk prefix merupakan cara / bentuk penulisan ekspresi aritmatika dimana operator ditulis di depan dari operandnya. Suatu prefix dapat berupa operand tunggal, atau gabungan dari unary operator dengan prefix, ataupun berupa gabungan dari binary operator dengan dua buah prefix. Diagram bentuk prefix dapat dilihat pada gambar di bawah ini. Suffix (Postfix) Bentuk suffix (postfix) merupakan cara / bentuk penulisan ekspresi aritmatika dimana operator ditulis di belakang dari operandnya. Suatu suffix dapat berupa operand tunggal, atau gabungan dari suffix dengan unary operator, ataupun berupa gabungan dari dua buah suffix dengan binary operator. Diagram bentuk suffix dapat dilihat pada gambar di bawah ini.


156

Operand

Infix expression

Infix expression

Unary operator

Infix expression

Infix expression

Binary operator

Gambar 1 : Diagram bentuk infix

Operand

Prefix expression

Prefix expression

Unary operator

Prefix expression

Binary operator

Prefix expression

Gambar 2: Diagram bentuk prefix

Operand

Suffix expression

Suffix expression

Suffix expression

Unary operator

Suffix expression

Binary operator

Gambar 3: Diagram bentuk suffix

Pohon Ekspresi (Expression Tree) Pohon ekspresi (expression tree) adalah sebuah pohon biner (binary tree) dimana daun berisi operand yang terdapat dalam ekspresi aritmatika dan akar berisi operator yang terdapat dalam ekspresi aritmatika tersebut. Proses pembacaan dari pohon ekspresi dimulai dari daun paling kiri hingga akar utama. Operand dan operator yang berada pada level bawah akan dibaca terlebih dahulu.

Sebagai contoh, misalkan diketahui sebuah ekspresi matematika x * y + 2 * (z – 3), maka pohon ekspresinya adalah sebagai berikut, + * x

* y

2

z

3

Gambar 4 : Pohon ekspresi untuk ekspresi aritmatika x * y + 2 * (z – 3)


157

Proses Traversal pada Binary Tree Pohon biner (Binary Tree) dapat ditelusuri dengan 4 cara yakni: Preorder Traversal (Penelusuran Preorder) Cetak Node H Preorder

Cetak Node A

Left subtree

Left subtree (kosong)

Cetak Node C

Cetak Node B Left subtree (kosong)

Right subtree

Left subtree

Right subtree (kosong)

A

B

C C

Right subtree

B

B

D

D

D

Right subtree

Cetak Node D Left subtree (kosong) Right subtree (kosong)

Cetak Node K

Cetak Node J

Left subtree


J K J

L


Cetak Node L Right subtree

Left subtree (kosong) Right subtree (kosong)

L

Gambar 5: Proses Preorder traversal dari binary tree Inorder Traversal (Penelusuran Inorder) Left subtree (kosong)

Left subtree A

Left subtree (kosong) Cetak Node A

Left subtree

Right subtree

Cetak Node C


Right subtree

Cetak Node D

B

C

C

Cetak Node B Right subtree (kosong)

Right subtree (kosong) B

Inorder

D

B

Cetak Node H

D

Left subtree

D Left subtree (kosong) Cetak Node J Right subtree (kosong)

J

Right subtree

Cetak Node K Right subtree

K J

L

Left subtree (kosong) Cetak Node L Right subtree (kosong)

L

Gambar 6: Proses Inorder Traversal dari binary Tree


158

Postorder Traversal (Penelusuran Postorder) Left subtree (kosong) Left subtree (kosong)

Left subtree

B

Right subtree

C B

C B

D

Right subtree (kosong) Cetak Node B

Right subtree

A

Postorder

Left subtree

D

D

Cetak Node C

Cetak Node A

Left subtree (kosong) Right subtree (kosong) Cetak Node D


Right subtree Left subtree


K J

Cetak Node J

J

L

Left subtree (kosong) Right subtree

Cetak Node L Right subtree (kosong)

L

Cetak Node H

Cetak Node K

Gambar 7: Proses Postorder Traversal dari binary tree

3. PEMBAHASAN Algoritma Pembagian Ekspresi Aritmatika ke bentuk Sub Ekspresi Aritmatika Proses penggambaran pohon ekspresi membutuhkan sub – sub ekspresi aritmatika pada setiap tahapnya. Oleh karena itu, ekspresi aritmatika yang diinput harus dibagi ke bentuk sub ekspresi aritmatika sebelum memasuki proses penggambaran pohon ekspresi. Algoritma pembagian ekspresi aritmatika ke bentuk sub ekspresi aritmatika terbagi atas 3 (tiga) algoritma yaitu, algoritma pembagian untuk bentuk prefix, suffix (postfix) dan infix. Algoritma Pembagian Ekspresi Aritmatika dalam Bentuk Prefix ke Bentuk Sub Ekspresi Aritmatika Sebagai contoh, penulis meng-input data sebagai berikut.  Ekspresi Aritmatika dalam bentuk Prefix : „- + ~ g ^ a 2 * 4 + * b c/ d e‟.

 Proses pembagian ekspresi aritmatika ke sub ekspresi aritmatika, adalah sebagai berikut :

Gambar 8: Hasil Pembagian ke Sub Ekspresi Aritmatika dengan Input Ekspresi Aritmatika dalam bentuk Prefix ‘-+~gâ2*4+*bc/de’

Algoritma Pembagian Ekspresi Aritmatika dalam Bentuk Suffix (Postfix) ke Bentuk Sub Ekspresi Aritmatika  Contoh Input Ekspresi Aritmatika dalam bentuk Suffix (Postfix) : „c a ^ b * z ~ c e * + / d -‟.


 Proses pembagian ekspresi aritmatika ke sub ekspresi aritmatika, adalah sebagai berikut :

Gambar 9 : Hasil Pembagian ke Sub Ekspresi Aritmatika dengan Input Ekspresi Aritmatika dalam bentuk Suffix ‘c a ^ b * z ~ c e * + / d -’

Algoritma Pembagian Ekspresi Aritmatika dalam Bentuk Infix ke Bentuk Sub Ekspresi Aritmatika  Contoh Input Ekspresi Aritmatika dalam bentuk Infix (Bentuk Biasa) : „(a+b)/c*5-((3\d)^(e^2*b))‟.  Proses pembagian ekspresi aritmatika ke sub ekspresi aritmatika, adalah sebagai berikut :

159

aritmatika yang telah dihasilkan oleh algoritma pembagian.  Hasil penggambaran struktur pohon ekspresi dalam bentuk prefix ‘-+~gâ2*4+*bc/de’

Gambar 11 : Hasil Penggambaran Struktur Pohon Ekspresi dengan Input Ekspresi Aritmatika dalam bentuk Prefix ‘-+~gâ2*4+*bc/de’

 Hasil penggambaran struktur pohon ekspresi dalam bentuk infix ‘(a+b)/c*5-((3\d)^(e^2*b))’

Gambar 12 : Hasil Penggambaran Struktur Pohon Ekspresi dengan Input Ekspresi Aritmatika dalam bentuk Infix (Biasa) ‘(a+b)/c*5-((3\d)^(e^2*b))’

Algoritma Order

Gambar 10 : Hasil Pembagian ke Sub Ekspresi Aritmatika dengan Input Ekspresi Aritmatika dalam bentuk Infix (Biasa) ‘(a+b)/c*5-((3\d)^(e^2*b))’

Algoritma Penggambaran Struktur Pohon Ekspresi Algoritma penggambaran berfungsi untuk menggambarkan struktur pohon ekspresi sesuai dengan sub ekspresi

Proses

Traversal

Pre

Algoritma proses traversal Pre Order mengunjungi semua data / node yang dimulai dari data akar, dilanjutkan ke sebelah kirinya, setelah itu dilanjutkan ke sebelah kanannya. Hasil proses traversal Pre Order menghasilkan ekspresi aritmatika dalam bentuk prefix.  Hasil proses traversal Pre Order dari bentuk Prefix ‘-+~gâ2*4+*bc/de’


160

Gambar 13: Hasil Proses Traversal Pre Order dengan Input Ekspresi Aritmatika dari bentuk Prefix ‘-+~gâ2*4+*bc/de’

Algoritma proses traversal Pre Order adalah sebagai berikut : '--------- SIMULASI TRAVERSAL PREORDER Private Sub ProcPreOrder(pnNode As Integer, pcJalur As String, ByVal pnSpeed As Integer) 'Tree tidak kosong If pnNode <> 0 Then '----- Write (Aku.Isi) ShpNode(pnNode).FillColor = &HFF& 'Merah lblNode(pnNode).FontBold = True lblNode(pnNode).ForeColor = &HFFFFFF 'Putih pcJalur = pcJalur & ", " & lblNode(pnNode).Caption 'Delay 500 DoEvents Sleep pnSpeed DoEvents ShpNode(pnNode).FillColor = &HFFFFFF 'Putih lblNode(pnNode).FontBold = False lblNode(pnNode).ForeColor = 0 'Hitam '-----------------------------'Write (Aku.Kiri) Call ProcPreOrder(ArrNode(pnNode).Left, pcJalur, pnSpeed) 'Write (Aku.Kanan) / Rekursif Call ProcPreOrder(ArrNode(pnNode).Right, pcJalur, pnSpeed) End If End Sub Hasil proses traversal Pre Order dari bentuk Suffix ‘ca^b*z~ce*+/d-’

Gambar 14: Hasil Proses Traversal Pre Order dengan Input Ekspresi Aritmatika dari bentuk Suffix ‘ca^b*z~ce*+/d-’

Algoritma proses traversal In Order adalah sebagai berikut : '--------- SIMULASI TRAVERSAL INORDER Private Sub ProcInOrder(pnNode As Integer, pcJalur As String, ByVal pnSpeed As Integer) 'Tree tidak kosong If pnNode <> 0 Then 'Write (Aku.Kiri) / Rekursif Call ProcInOrder(ArrNode(pnNode).Left, pcJalur, pnSpeed) '----- Write (Aku.Isi) ShpNode(pnNode).FillColor = &HFF& 'Merah lblNode(pnNode).FontBold = True lblNode(pnNode).ForeColor = &HFFFFFF 'Putih pcJalur = pcJalur & ", " & lblNode(pnNode).Caption 'Delay 500 DoEvents Sleep pnSpeed DoEvents ShpNode(pnNode).FillColor = &HFFFFFF 'Putih lblNode(pnNode).FontBold = False lblNode(pnNode).ForeColor = 0 'Hitam '-----------------------------'Write (Aku.Kanan) Call ProcInOrder(ArrNode(pnNode).Right, pcJalur, pnSpeed) End If End Sub Hasil dari proses traversal In Order dikembalikan pada nilai variabel pcJalur


Hasil proses traversal Pre Order dari bentuk Infix (Biasa) ‘(a+b)/c*5-((3\d)^(e^2*b))’

Gambar 15 : Hasil Proses Traversal Pre Order dengan Input Ekspresi Aritmatika dari bentuk Infix (Biasa) ‘(a+b)/c*5-((3\d)^(e^2*b))’

Algoritma proses traversal Post Order adalah sebagai berikut : '--------- SIMULASI TRAVERSAL POSTORDER Private Sub ProcPostOrder(pnNode As Integer, pcJalur As String, ByVal pnSpeed As Integer) 'Tree tidak kosong If pnNode <> 0 Then 'Write (Aku.Kiri) Call ProcPostOrder(ArrNode(pnNode).Left, pcJalur, pnSpeed) 'Write (Aku.Kanan) Call ProcPostOrder(ArrNode(pnNode).Right, pcJalur, pnSpeed) '----- Write (Aku.Isi) ShpNode(pnNode).FillColor = &HFF& 'Merah lblNode(pnNode).FontBold = True lblNode(pnNode).ForeColor = &HFFFFFF 'Putih pcJalur = pcJalur & ", " & lblNode(pnNode).Caption 'Delay 500 DoEvents Sleep pnSpeed DoEvents ShpNode(pnNode).FillColor = &HFFFFFF 'Putih lblNode(pnNode).FontBold = False lblNode(pnNode).ForeColor = 0 'Hitam '-----------------------------End If End Sub

161

4. SIMPULAN Setelah menyelesaikan perancangan perangkat lunak pembelajaran pohon ekspresi (expression tree), peneliti berkesimpulan sebagai berikut :  Perangkat lunak dapat melakukan validasi terhadap struktur prefix, infix dan postfix.  Perangkat lunak didukung dengan visualisasi proses pembentukan pohon ekspresi, proses traversal, dan proses evaluasi.  Perangkat lunak dapat digunakan untuk membantu pemahaman pembentukan pohon ekspresi. DAFTAR PUSTAKA Alfred V.Aho, John E. Hopcroft, Jeffrey D. Ullman, 1983. Data Structures And Algorithms. Alfred V.Aho, Ravi Sethi, Jeffrey D. Ullman, 1986. Compilers, Principles, Techniques, and Tools Rahadian, Hadi, 2002. Pemrograman Windows API dengan Microsoft Visual Basic 6.0, PT. Elex Media Komputindo. Rahmat Putar, 2005. The Best Source Code Visual Basic, PT. Elex Media Komputindo. Robert L.Kruse, 1991. Data Structures & Program Design, Second Edition.

REKAYASA PERANGKAT LUNAK PEMBELAJARAN POHON EKSPRESI (EXPRESSION TREE)

Recommend Documents