Seorang ahli
matematika “Jan Lukasiewicz“ mengembangkan satu cara penulisan ungkapan numeris
yang selanjutnya disebut “Notasi Polish“ atau “Notasi Prefix” yang artinya:
operator ditulis sebelum kedua operand yang akan disajikan.
Dalam struktur data
yang banyak dipelajari, kita ketahui adanya 3 notasi operasi yang dilakukan
untuk suatu operasi aritmatika, yaitu prefix, infix, dan postfix.
Sebelum kita kupas
mengenai notasi di atas, perlu dipahami terlebih dahulu indikator yang membentuk
terjadinya notasi dalam struktur data. Notasi terbentuk dari operand dan
operator.Operand adalah data atau nilai yang membantu dalam proses
sedangkanoperator adalah fungsi yang digunakan dalam proses.
Contoh :
2 + 3 * 5
Keterangan : A, B, C,
2, 3, 5 adalah operand
+, *
adalah operator
Nahh… sekarang
mudah-mudahan sudah dapat diketahui indikator yang membentuk suatu notasi.
Selanjutnya kita harus mengetahui level/hirarkhi dari operator seperti
1. ^ (pangkat)
2. * (kali) atau /
(bagi)
3. + (jumlah) atau –
(kurang)
Seperti yang telah
dibahas di awal, diketahui notasi pada struktur data terdiri atas 3 macam,
yaitu
1. Prefix
yaitu notasi yang terbentuk atas operator dengan operand, dimana operator
berada didepan operand.
Contoh : A + B * C (Infix)
maka notasi prefixnya adalah +A*BC
Pemecahannya :
A +
B * C
diketahaui ada 3
operand yaitu : A, B, C, dan 2 operator yaitu : +, *. Proses dimulai
dengan melihat dari hirarkhi operator. Contoh diatas operator yang tertinggi
adalah * kemudian +.
Tanda * diapit oleh
dua operand yaitu B dan C yaitu B * C , prefixnya dengan
menggabungkan operand dan memindahkan operator kedepan 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 di atas, operator +, diapit oleh 2 operand, yaitu A dan *BC, gabungkan
operand, sehingga menjadi A*BC, lalu pindahkan operator kedepan
operand, sehingga hasil akhir menjadi
+ A * B C
Contoh yang
lain:
1. A + B
– C * D
2
3 1 —–> hirarkhi
level
A
+ B – *CD —–> 1
+AB – *CD —–> 2
–
+AB *CD —–> 3
2. A * B ^ C –
D
2 1 3
—–> hirarkhi
A * ^BC
– D —–> 1
*A^BC - D
—–> 2
-*A^BCD
—–> 3
3. A + ( B – C
) * D
3 1
2 —–> hirarkhi
A
+ -BC * D —–> 1 (karena diapit tanda
paranthesis atau kurung buka/tutup,( ) )
A
+ *-BCD —–> 2
+
A *-BCD —–> 3
2. Infix
yaitu notasi yang
terbentuk atas operator dengan operand, dimana operator berada diantara
operand. Notasi ini hanya dikenal oleh manusia dan selalu digunakan dalam
perhitungan aritmatika.
Contoh : A + B * C
( A + B ) * C
A – ( B + C ) * D ^ E
3. Postfix
yaitu notasi yang
terbentuk atas operator dengan operand, dimana operator berada dibelakang
operand. Notasi ini hanya dikenal oleh processor dan dipahami dalam ALU.
Contoh : A + B * C (Infix)
maka
notasi postfixnya adalah ABC*+
Pemecahannya :
A +
B * C
diketahaui ada 3
operand yaitu : A, B, C, dan 2 operator yaitu : +, *. Proses dimulai
dengan melihat dari hirarkhi operator. Contoh diatas operator yang tertinggi
adalah * kemudian +.
Tanda * diapit oleh
dua operand yaitu B dan C yaitu B * C , postfixnya dengan
menggabungkan operand B dan C menjadi BC lalu memindahkan operator ke
belakang operand C, sehingga fungsi B * C, notasi postfixnya menjadi
BC*. Sehingga hasil sementara dari notasi postfix adalah
A + BC*
selanjutnya mencari
postfix untuk operator yang berikutnya, yaitu +, cara yang dilakukan sama
seperti di atas, operator +, diapit oleh 2 operand, yaitu A dan BC*, gabungkan
operand tersebut, sehingga menjadi ABC*, lalu pindahkan operator + ke belakang
operand ABC*, sehingga hasil akhir menjadi
ABC*+
Contoh yang
lain:
1.
A + B – C * D
2
3 1 —–> hirarkhi
level
A
+ B – CD* —–> 1
AB+ – *CD —–> 2
AB+*CD- —–> 3
2. A * B ^ C –
D
2 1 3
—–> hirarkhi
A * BC^
– D —–> 1
ABC^* - D
—–> 2
ABC^*D-
—–> 3
3. A + ( B – C
) * D
3 1
2 —–> hirarkhi
A
+ BC- * D —–> 1 (karena diapit tanda
paranthesis atau kurung buka/tutup,( ) )
A
+ BC-D* —–> 2
A
BC-D*+ —–> 3
yahh…gitulah
pembentukkan notasi yang bisa di sharing dalam pertemuan ini.
Contoh lain:
Notasi
Infix-Prefix
Cara penulisan
ungkapan yaitu dengan menggunakan notasi infix, yang artinya operator ditulis
diantara 2 operator.
Seorang ahli
matematika bernama Jan Lukasiewiccz mengembangkan suatu cara penulisan ungkapan
numeris yang disebut prefix, yang artinya operator ditulis sebelum kedua
operand yang akan disajikan.
Contoh :
Proses konversi
dari infix ke prefix
:
= ( A + B ) * ( C – D
)
= [ + A B ] * [ - C D
]
= * [ + A B ] [ - C D
]
= * + A B – C D
Notasi
Infix-Postfix
Cara penulisan
ungkapan yaitu dengan menggunakan notasi postfix, yang artinya operator ditulis
sesudah operand.
Contoh :
Proses konversi
dari infix ke postfix
:
= ( 6 – 2 ) * ( 5 + 4
)
= [ 6 2 - ] * [ 5 4 +
]
= [ 6 2 - ] [ 5 4 + ]
*
= 6 2 – 5 4 + *
Listing Program Notasi Polish dengan Menggunakan VB.net
Public Class Form1
Dim
jmlkata As Integer
Dim
data(100) As String
Dim
tumpukan(100) As String
Dim
toptumpukan As Integer
Dim r,
postfix, prefix As String
Function
derajat(ByVal tandaop As Char) As Integer
Select
Case tandaop
Case
"^"
derajat
= 3
Case
"*", "/"
derajat
= 2
Case
"+", "-"
derajat
= 1
Case
"("
derajat
= 0
End
Select
End
Function
Sub
fungsipostfix()
postfix
= ""
For
j As Integer = 1 To jmlkata
r
= data(j)
If
r <> "*" And r <> "-" And r <>
"/" And r <> "+" And r <> "^" And r
<> "(" And r <> ")" Then
postfix
= postfix & r
ElseIf
r = "(" Then
toptumpukan
+= 1
tumpukan(toptumpukan)
= r
ElseIf
r = ")" Then
While
tumpukan(toptumpukan) <> "("
postfix
= postfix & tumpukan(toptumpukan)
toptumpukan
-= 1
End
While
toptumpukan
-= 1
ElseIf
r = "*" Or r = "-" Or r = "/" Or r =
"+" Or r = "^" Then
If
toptumpukan = 0 Or derajat(r) > derajat(tumpukan(toptumpukan)) Then
toptumpukan
+= 1
tumpukan(toptumpukan)
= r
Else
postfix
= postfix & tumpukan(toptumpukan)
toptumpukan
-= 1
If
toptumpukan = 0 Or derajat(r) > derajat(tumpukan(toptumpukan)) Then
toptumpukan
+= 1
tumpukan(toptumpukan)
= r
End
If
End
If
End
If
Next
While
toptumpukan <> 0
postfix
= postfix & tumpukan(toptumpukan)
toptumpukan
-= 1
End
While
txtpostfix.Text
= postfix
End Sub
Sub
fungsiprefix()
'konversi
infix ke prefix
toptumpukan
= 0
For
k As Integer = jmlkata To 1 Step -1
r
= data(k)
If
r <> "*" And r <> "-" And r <>
"/" And r <> "+" And r <> "^" And r
<> "(" And r <> ")" Then
prefix
&= r
ElseIf
r = ")" Then
toptumpukan
+= 1
tumpukan(toptumpukan)
= r
ElseIf
r = "*" Or r = "-" Or r = "/" Or r =
"+" Or r = "^" Then
If
toptumpukan = 0 Or tumpukan(toptumpukan) = ")" Or derajat(r) >=
derajat(tumpukan(toptumpukan)) Then
toptumpukan
+= 1
tumpukan(toptumpukan)
= r
Else
prefix
&= r
toptumpukan
-= 1
End
If
ElseIf
r = "(" Then
While
tumpukan(toptumpukan) <> ")"
prefix
&= tumpukan(toptumpukan)
toptumpukan
-= 1
End
While
toptumpukan
-= 1
End
If
Next
While
toptumpukan <> 0
prefix
&= tumpukan(toptumpukan)
toptumpukan
-= 1
End
While
txtprefix.Text
= StrReverse(prefix)
End Sub
Private
Sub btnkonversi_Click(ByVal sender As System.Object, ByVal e As System.EventArgs)
Handles btnkonversi.Click
jmlkata
= Len(txtinfix.Text)
toptumpukan
= 0
For
i As Integer = 1 To jmlkata
data(i)
= Mid(txtinfix.Text, i, 1)
Next
fungsipostfix()
fungsiprefix()
End Sub
End Class
Listing Program Binary Tree Search dengan Menggunakan C++
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedef char typeinfo;
typedef struct node tree;
struct node {
int
info;
tree
*kanan;//cabang kiri
tree
*kiri;//cabang kanan
};
tree *p,*q,*baru, *root,*baca;
int x,n=0;
float total=0.0f,jum=0.0f;
float rata=0.0f;
void alokasi(){
printf("masukan
DATA: ");
fflush(stdin);
scanf("%i",&x);
baru=(tree
*)malloc(sizeof(tree));
if(baru==NULL){
puts("Alokasi memori
gagal");
}
else{
baru->info=x;
baru->kanan=NULL;
baru->kiri=NULL;
}
}
void bentuk(){
alokasi();
n++;//banyak
data
if(root==NULL){
root=baru;
}
else{
p=root;
q=root;
while((q!=NULL)&&(baru->info!=p->info)){
p=q;
if(baru->info<p->info){
q=p->kiri;
}
else{
q=p->kanan;
}
}
if(baru->info==p->info){
puts("data duplikasi");
}
else{
if(baru->info<p->info){
p->kiri=baru;
}
else{
p->kanan=baru;
}
}
}
}
void preorder(tree *root){
if(root!=NULL){
jum=root->info;
printf("%d
",root->info);
total=total+jum;
preorder(root->kiri);
preorder(root->kanan);
}
//return;
}
void inorder(tree *root){
if(root!=NULL){
inorder(root->kiri);
printf("%d
",root->info);
inorder(root->kanan);
}
//return;
}
void postorder(tree *root){
if(root!=NULL){
postorder(root->kiri);
postorder(root->kanan);
printf("%d
",root->info);
}
//return;
}
main(){
char
jawab;
do{
bentuk();
printf("ada data lagi:
");
fflush(stdin);
jawab=getchar();
}while(jawab=='y'||jawab=='Y');
printf("hasil
prefix order : ");
preorder(root);
printf("\nhasil
infix order : ");
inorder(root);
printf("\n
hasil postfix order : ");
postorder(root);
printf("\ntotal
data=%d",total);
printf("\nbanyak
data=%d ",n);
printf("\n\nrata-rata=
%g\n",rata=total/n);
Tidak ada komentar:
Posting Komentar