PROGRAM
STACK METODE NOTASI POLISH & PROGRAM METODE BINARY TREE SEARCH
A.
Program
Stack Metode Notasi Polish
A.1.
Notasi Prefix
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.
Contoh notasi prefix dari notasi infix:
Infix Prefix
A + B + A B
A + B – C - + A B C
( A + B ) * ( C – D ) * + A B – C D
A – B / ( C * D $ E ) - - -
Secara sederhana, proses konversi dari infix menjadi
prefix sebagai berikut:
1. Ungkapan yang akan dikonversikan adalah ( A + B )
* ( C – D ).
2. Dengan menggunakan tanda kurung bantuan, ungkapan
diatas kita ubah menjadi: [ + A B ] * [ - C D ]
3. Jika [ + A B ] kita misalkan P, dan [ - C D ]
kita misalkan Q maka ungkapan di atas bisa ditulis sebagai berikut: P * Q
4. Selanjutnya notasi infix dirubah menjadi prefix:
* P Q
5. Dengan mengembalikan P dan Q pada notasinya
semula dan menghapus tanda kurung bantuan, kita peroleh notasi prefix dari
persamaan ( A + B ) * ( C – D ) yaitu: * + A B – C D
Contoh:
1. A + B * C
B * C = * B C ..... P
C * P = * C P ..... Q
Ø Algoritma Infix Ke Prefix:
Langkah 0:- Baca ungkapan dalam notasi infix,
misalnya S;
- Tentukan panjang ungkapan tersebut, misalnya N;
- Siapkan sebuah tumpukan kosong dan siapkan derajat
masing-masing operator.
Misalnya: $ berderajat 3, * dan / berderajat 2, +
dan – berderajat 1 dan (berderajat 0).
Langkah 1:
Dimulai dari I : N sampai 1, kerjakan
langkah-langkah berikut :
a. R = S ( I )
b. Test nilai R. Jika R adalah:
- Operand : Langsung ditulis
- Kurung buka : Pop dan tulis semua isi tumpukan
sampai ujung tumpukan = ‘)‘, pop juga tanda ini tetapi tidak perlu ditulis.
- Kurung tutup : Push kedalam tumpukan
- Operator : Jika tumpukan kosong, atau derajat R
lebih tinggi
dibanding derajat ujung tumpukan, push operator
ke dalam tumpukan. Jika tidak pop ujung tumpukan dan
tulis, kemudian ulangi perbandingan R dengan ujung tumpukan, lalu R di push.
Catatan: Kurung tutup di dalam tumpukan dianggap
mempunyai derajat yang lebih rendah dibanding R.
Langkah 2: Jika akhir notasi infix telah tercapai
dan tumpukan masih belum kosong, pop semua isi tumpukan dan tulis hasilnya.
Contoh:
1. A + B * C
Proses Ke- Karakter Dibaca Isi Stack Karakter
Tercetak Notasi Prefix Terbentuk
1. C C C
2. * *
3. B * B BC
4. + + * *BC
5. A + A A*BC
6. + +A*BC
A.2.
Notasi Infix
Salah satu pemanfaatan tumpukan adalah untuk menulis
ungkapan menggunakan notasi tertentu. Dalam penulisan ungkapan khususnya
ungkapan numeris, kita selalu menggunakan tanda kurung untuk mengelompokkan
bagian mana yang harus dikerjakan lebih dahulu.
Contoh :
1. ( A + B ) * ( C – D )
Suku ( A + B ) akan dikerjakan lebih dahulu,
kemudian suku ( C – D ) dan terakhir mengalikan hasil yang diperoleh dari 2
suku ini.
2. A + B * C – D
Maka B * C akan dikerjakan lebih dahulu diikuti yang
lain.
Dalam hal ini pemakaian tanda kurung akan sangat
mempengaruhi hasil akhir. Cara penulisan ungkapan sering disebut dengan “Notasi
Infix” artinya operator ditulis diantara 2 operand.
A.3.
Notasi Postfix
Notasi lain yang merupakan kebalikan notasi prefix
adalah “Notasi Postfix” atau lebih dikenal dengan Notasi Polish Terbalik
(Reverse Polish Notation atau RPN). Dalam hal ini operator ditulis sesudah
operand. Sama halnya dengan notasi prefix disini juga diperlukan tanda kurung
pengelompokan.
Proses notasi dari infix ke postfix adalah :
1. Ungkapan yang akan dikonversikan adalah: (A + B )
* ( C – D ).
2. Dengan menggunakan tanda kurung bantuan, ungkapan
diatas diubah menjadi: [ A B + ] * [ C D - ]
3. Jika [ A B + ] kita misalkan P, dan [ C D - ]
kita misalkan Q, maka ungkapan diatas dapat ditulis: P * Q
4. Selanjutnya notasi infix dirubah menjadi postfix
yaitu: P Q *
5. Dengan mengembalikan P dan Q paada notasinya
semula dan menghapus tanda kurung bantuan kita peroleh notasi postfix dari
persamaan:
( A + B ) * ( C - D ) yaitu A B + C D - *
Contoh
notasi infix ke postfix:
Infix Postfix
A + B – C A B + C –
( A + B ) * ( C – D ) A B + C D - *
A – B / ( C * D $ E ) - - -
Contoh soal:
1. A – B / ( C * D $ E )
D $ E = D E $ .... P
C * P = C P * .... Q
B / Q = B Q / .... R
A – R = A R –
= A B Q / -
= A B C P * / -
= A B C D E $ * / -
e- Karakter Dibaca Isi Stack Karakter Tercetak Notasi Postfix Terbentuk
1. A A A
2. + +
3. B + B AB
4. * *+
5. C *+ C ABC
6. + * ABC*
7. + ABC*+
Tabel
3. Perbandingan Operator dalam stack dan operator yang dibaca
Operator
|
Nilai Operator
Dalam Stack
|
Nilai Operator
Yang Dibaca
|
(
|
0
|
|
)
|
0
|
5
|
+,-
|
2
|
1
|
*,/
|
4
|
3
|
Berdasarkan tabel tersebut suatu operator yang dibaca dan akan dimasukan
ke dalam stack, terlebih dahulu melalui proses perbandingan nilai dengan
operator yang ada di dalam stack sebelumnya. Dalam arti kata lain jika nilai
dari operator yang berada dalam stack lebih besar dari nilai operator yang
dibaca maka operator yang berada di dalam stack akan dikeluarkan sampai nilai
tersebut sama atau lebih kecil. Implementasi dari algoritmanya dapat dijabarkan
dalam bentuk fungsi sebagai berikut :
Function IsiDlmStack(Operator : Char) : Integer;
Begin
Case Operator Of
‘(‘ : IsiDlmStack := 0;
‘+‘,’-‘ : IsiDlmStack := 2;
‘*‘,’/’ : IsiDlmStack := 4;
End
End;
Fungsi Isidlmstack tersebut di atas merupakan fungsi
level operator yang posisinya berada dalam suatu stack, adapun fungsi untuk
menentukan level operator yang dibaca adalah :
Function Stackyangdibaca(Operator : Char) : Integer;
Begin
Case Operator Of
‘)‘ : Stackyangbaca := 0;
‘+‘,’-‘ : Stackyangbaca := 1;
‘*‘,’/’ : Stackyangbaca := 3;
‘(‘ : Stackyangbaca := 5
End
End;
Setelah fungsi pengecekan dilakukan, proses yang
perlu dirancang selanjutnya adalah membentuk suatu prosedur untuk menyimpan
operator yang dibaca ke dalam suatu susunan array yang implementasinya dibuat
sebagai berikut :
Procedure SimpanChar(Ch : Char;
Var Ekspost : TipeEks;
Var Indekspost : TipeIndex);
Begin
Indekspost :=Indekspost + 1;
Ekspost := ch
End;
Dengan adanya prosedur penyimpanan operator ke dalam
suatu array tersebut di atas, maka proses konversi notasi infix ke notasi
Postfix disusun dalam bentuk bahasa algoritma sebagai berikut[2] :
Ø Prosedur Konversi Infix Ke Postfix
1. Read Panjang suatu untai karakter
2. Create Stack
3. Push Operator ‘(‘ ke Puncak Stack
4. n := 0
5. For K := 1 To Panjang suatu untai + 1 do
If untai ke k adalah operand then
Keluarkan
untai ke K dalam bentuk Output
Else
While
Nilai operator dal;am stack > operator yang dibaca do
Pop
Isi operator dari dalam stack
Keluarkan operator tersebut dalam bentuk output
End While
If Operator
ke K = ‘)’ then
Pop isi
operator dari stack
Else
Push
Operator ke dalam stack
End If
End If
Panjang untai ;= n
6. End For
Dengan berpandangan pada algoritma konversi tersebut
di atas, rancang bangun algoritma dalam baha pemrograman Pascal disusun sebagai
berikut :
Procedure konversi infixkePostfix (eks dlm : Tipe
eks;
pjg dlm : Tipe index;
var ekspost: Tipe Eks;
var panjang post : Tipe indeks);
Var
opstack : stack ;
indeksdlm, indeks post: Tipe index;
chdlm, operator, simpan : char ;
Begin
create (Opstack);
Push (Opstack, '(');
Push (Opstack, '(');
eksdlm[pjg dlm +1] := ')';
Indeks post: = 0;
For indeksdlm : = 1 to pjgdlm +1 Do
Begin
chdlm: = Eks Dlm [indeks dlm];
if ch dlm in ['A'....'Z'] then
simpan char (ch Dlm, Ekspost,indekspost)
Else
Begin
While isidlmstack(puncak stack (opstack))> stack
yang dibaca (ch dlm) Do
begin
pop(opstack,operator);
simpanchar(operator,ekspost,indekspost)
end;
if chdlm = ')' then
pop(opstack,simpan)
else
push(opstack,simpan)
end
panjang post := indekspost
end;
panjang post := indekspost
end;
Sajian lengkap dari proses konversi notasi infix ke
notasi Postfix dalam bahasa Pascal yang siap untuk diterapkan diuraikan di
bawah tulisan ini
Aplikasi
konversi notasi infix ke notasi Postfix merupakan salah satu sarana untuk dapat
mengetahui proses perhitungan aritmatika dalam mesin kompilasi. Penggunaan
stack tersebut juga dapat dipakai untuk metode lain seperti membuat matching
parentheses, maupun uji palindrome disamping penggunaannya dalam proses konversi
notasi ini, yang perlu dipahami adalah suatu stack pada dasarnya merupakan
array yang memuat 2 informasi penting yaitu NOEL yang berfungsi untuk
mengetahui jumlah tumpukan dan TOP yang berfungsi untuk menentukan posisi
puncak dari suatu stack. Stack juga memiliki 2 kondisi yang dapat menyebabkan
error yaitu kondisi underflow jika stack tersebut dalam keadaan kosong
dilakukan operasi ambil data (pop) dan kondisi overflow jika stack dalam
keadaan penuh dilakukan operasi penambahan data. Kedua posisi ini dapat
menyebabkan stack dalam keadaan tidak valid sehingga penggunaan error trapping
untuk menampung kondisi tidak valid perlu diperhatikan.
Notasi infix yang umum digunakan oleh berbagai
kalangan dalam melakukan suatu proses perhitungan aritmatika dapat *** disusun
ke dalam notasi Postfix yang digunakan oleh mesin kompilasi sehingga
pengetahuan tentang penggunaan notasi aritmatika akan lebih luas.
Listing
Program
{ Program
Name : Konversi.Pas
Authors : Oke Hendradhy
Version
: 1.0
}
Uses crt;
const
Noelstack = 80;
Makschar = 80;
Type
Eon = char;
stack =
Record
Top : array[1...Noelstack] of
Eon;
Noel : 0... Noelstack;
End;
Tipeindex =
0... makschar;
Typeeks =
array[1... Noelstack] of char
Var
lagi : char;
{Bentuk-bentuk operasi stack}
Function isempty(Var s : stack):Boolean;
Begin
IsEmpty : =
s. noel = 0
End;
Procedure create (var s. stack);
Begin
S. Noel : =
0;
End;
procedure buatkosong (Var s. stack);
Begin
S. Noel : =
0;
End ;
Procedure stack Error (tingkat Error: integer);
Begin
Case tingkat
error of
1 :
Writeln (isi stack sudah terlalu penuh);
2 :
Writeln (isi stack kosong);
End
End;
Procedure push( var s : stack; tipebaru : Eon);
Begin
If s. Noel =
Noel stack then
stack
Error(1)
Else
Begin
s.Noel : = s. Noel+1 ;
s.Top[s.Noel] : = tipebaru
End
End;
Procedure pop(var s: stack ;
var
nilaistack : Eon);
Begin
If s. Noel
= 0 then
Stack
error(2)
Else
Begin
Nilaistack : = s.top[s.Noel];
S.Noel : = s. Noel - 1;
End
End;
{proses konversi suatu ekspresi}
Function puncak stack(s : stack) : Eon;
Begin
Puncak
stack : = s.top[s.noel]
End;
Function
isidlmstack (operator: char); integer;
Begin
case
operator of
'(' : isidlmstack : = 0;
'+','-' : isidlmstack : = 2;
'*',','/' : isidlmstack : = 4;
End
End;
Function stackyangdibaca (operator : char): integer
Begin
Case
operator of
')' : stackyangdibaca : =0;
'+','-' : stackyangdibaca : = 1;
'*','/' : stackyangdibaca : = 3;
'(' : stackyangdibaca : = 5;
End
End;
Procedure simpanchar(ch:char; Var ekspost :
Tipeks;Var indekspost ; Tipeindex);
Begin
Indekspost :
= indeks post+1;
ekspost
[indekspost]: = ch;
End;
Procedure
konversi infixkePostfix (eks dlm : Tipe eks;
pjg dlm : Tipe index;
var ekspost: Tipe Eks;
var panjang post : Tipe indeks);
Var
opstack :
stack ;
indeksdlm,
indeks post: Tipe index;
chdlm,
operator, simpan : char ;
Begin
create
(Opstack);
Push (Opstack,
'(');
eksdlm[pjg
dlm +1] := ')';
Indeks post:
= 0;
For
indeksdlm : = 1 to pjgdlm +1 Do
Begin
chdlm: =
Eks Dlm [indeks dlm];
if ch dlm
in ['A'....'Z'] then
simpan
char (ch Dlm, Ekspost,indekspost)
Else
Begin
While isidlmstack(puncak stack (opstack))> stack yang dibaca (ch dlm)
Do
begin
pop(opstack,operator);
simpanchar(operator,ekspost,indekspost)
end;
if
chdlm = ')' then
pop(opstack,simpan)
else
push(opstack,simpan)
end
panjang post := indekspost
end;
panjang post := indekspost
end;
produce
konversi ekspresi;
var
indeks
panjangdlm, panjang post :tipe index;
eksdlm,ekspot :tipe eks
begin
lagi :='y';
While
(upcase(lagi) ='x' do
Begin
clsscr;
panjangdlm := 0
while
not eoln do
begin
panjangdlm:=panjangdlm +1;
read(eksdlm[panjangdlm])
end;
readln
;
write('ekspresi infix:');
for
index := 1 to panjangdlm do
write(eksdlm[index]);
writeln;
konversiinfixkePostfix(eksdlm, panjangdlm, ekspost, panjang post);
write
('dalam bentuk Postfix')
for
indeks := 1 to panjangpost do
write
(ekspost [indeks]);
writeln;
writeln;
write
('ada data lagi<y/t>.'); readln (lagi)
end;
End;
begin
konversi
ekspresi;
end.
B.
Program
Metode Binary Tree Search Yang Mengimplementasikan Penggunaan Metode Notasi
Polish
B.1.
Pengertian
Sebuah pohon pencarian
biner adalah pohon dimana setiap simpul memiliki anak kiri dan kanan. Entah
anak, atau keduanya anak-anak, mungkin hilang.
Pengertian Kunjungan
Pada Pohon Biner
Ada tiga macam kunjungan pada pohon biner, yaitu kunjungan
PreOrder, InOrder, dan PostOrder. Selain itu ada kunjungan LevelOrder, yaitu
yang berdasarkan kedudukan tiap simpul dalam pohon. Keempat kunjungan itu
dibagi menjadi orientasi, yaitu left to right oriented (LRO) atau kunjungan
dilakukan di cabang kiri dulu baru ke cabang kanan dan right to left oriented
(RLO) atau kunjungan dilakukan di cabang kanan dulu baru ke cabang kiri.
1.
Kunjungan PreOrder :
Kunjungan PreOrder LRO
atau sering disebut dengan depth first order menggunakan urutan sebagai berikut
: 1. Cetak isi simpul yang dikunjungi (simpul akar) 2. Kunjungi cabang kiri 3.
Kunjungi cabang kanan.
2.
Kunjungan InOrder :
Kunjungan InOrder LRO
atau sering disebut dengan symmetric order menggunakan urutan sebagai berikut :
1. Kunjungi cabang kiri 2. Cetak isi simpul yang dikunjungi 3. Kunjungi cabang
kanan.
3.
Kunjungan PostOrder
Kunjungan PostOrder LRO
menggunakan urutan sebagai berikut : 1. Kunjungi cabang kiri 2. Kunjungi cabang
kanan 3. Cetak isi simpul yang dikunjungi.
Contoh program BINARY TREE
#include <stdio.h>
#include <conio.h>
struct Node
{ int
data;
Node
*kiri;
Node
*kanan;
};
void tambah(Node **root,int
databaru)
{ if((*root)
== NULL)
{ Node *baru;
baru
= new Node;
baru->data
= databaru;
baru->kiri
= NULL;
baru->kanan
= NULL;
(*root)
= baru;
(*root)->kiri
= NULL;
(*root)->kanan
= NULL;
printf("Data
bertambah!");
}
else if(databaru < (*root)->data)
tambah(&(*root)->kiri,databaru);
else
if(databaru > (*root)->data)
tambah(&(*root)->kanan,databaru);
else
if(databaru == (*root)->data)
printf("Data
sudah ada!");
}
void preOrder(Node *root)
{ if(root
!= NULL)
{ printf("%d ",root->data);
preOrder(root->kiri);
preOrder(root->kanan);
}
}
void inOrder(Node *root)
{ if(root
!= NULL)
{ inOrder(root->kiri);
printf("%d
",root->data);
inOrder(root->kanan);
}
}
void postOrder(Node *root)
{ if(root
!= NULL)
{ postOrder(root->kiri);
postOrder(root->kanan);
printf("%d
",root->data);
}
}
void main()
{ char
pil; int terus=1;
Node
*pohon;
pohon
= NULL;
while
(terus==1)
{ clrscr();
int
data;
printf("MENU\n");
printf("1.
Tambah\n");
printf("2.
Lihat pre-order\n");
printf("3.
Lihat in-order\n");
printf("4.
Lihat post-order\n");
printf("5.
Exit\n\n");
printf("Pilihan
Anda [1..5][ ]\b\b");
pil='
';
while
(!(pil>='1' && pil<='5')) { pil=getch();
}
printf("%c\n",pil);
switch(pil)
{ case '1': printf("Data
baru : ");scanf("%d",&data);
tambah(&pohon,data);
break;
case
'2': if(pohon!=NULL)
preOrder(pohon);
else
printf("Masih kosong!"); break;
case
'3': if(pohon!=NULL)
inOrder(pohon);
else
printf("Masih kosong!"); break;
case
'4': if(pohon!=NULL)
postOrder(pohon);
else
printf("Masih kosong!"); break;
default:
terus=0;
}
if
(pil!='5') getch();
}
}
B.2.Aplikasi Pohon Biner
Pada bagian ini akan di bahas
tenang bagaimana menusun sebuah pohon Biner yang apabila di kunjungi secara :
1. PreOrder menghasilkan notasi
Prefix.
2. InOrder mengasilkan notasi
Infix.
3. PostOrder mnghasilkan notasi
Postfix.
B.3.Contoh Program :
#include
<iostream.h>
#include
<stdio.h>
#include
<conio.h>
#include
<stdlib.h> // dibutuhkan untuk system("cls");
struct
tree_node
{
tree_node*
left;
tree_node*
right;
int
data;
};
tree_node*
root;
bool
isEmpty()
{return
root==NULL;}
void
insert(int d)
{
tree_node*
t = new tree_node;
tree_node*
parent;
t->data
= d;
t->left
= NULL;
t->right
= NULL;
parent
= NULL;
if(isEmpty())root
= t;
else
{
tree_node*
curr;
curr
= root;
while(curr!=NULL)
{
parent
= curr;
if(t->data
> curr->data) curr = curr->right;
else
curr = curr->left;
}
if(t->data
< parent->data)
parent->left
= t;
else
parent->right
= t;
}
}
void
inorder(tree_node* p)
{
if(p!=NULL)
{
if(p->left)
inorder(p->left);
cout<<"
"<<p->data<<" ";
if(p->right)
inorder(p->right);
}
else
return;
}
void
print_inorder()
{
inorder(root);
}
int
count(tree_node* p)
{
if(p==NULL)return
0;
return
count(p->left) + count(p->right) + 1;
}
int
height(tree_node* p)
{
if(p==NULL)return
0;
int
u = height(p->left),v = height(p->right);
if(u
> v)
return
u+1;
else
return
v+1;
}
void
cari_terbesar(tree_node* p)
{
if(p==NULL)
return;
else
if(p->right==NULL)
{
cout<<"
"<<p->data<<" ";
return;
}
else
{
cari_terbesar(p->right);
return;
}
}
int
main()
{
root=NULL;
int
ch,tmp;
while(1)
{
system("cls");
// Saya mengganti scrclr() karena dicompiler sy tidak ada fungsi tersebut
cout<<endl;
cout<<"Menu
Utama Operasi Pohon Biner"<<endl;
cout<<"--------------------"<<endl;
cout<<"1.
Insert/Tambah Data"<<endl;
cout<<"2.
Kunjungan In-Order"<<endl;
cout<<"3.
Kunjungan Pre-Order"<<endl;
cout<<"4.
Kunjungan Post-Order"<<endl;
cout<<"5.
Hapus Data"<<endl;
cout<<"6.
Menghitung Jumlah Node"<<endl;
cout<<"7.
Menghitung Tinggi Pohon"<<endl;
cout<<"8.
Mencari Data Terkecil"<<endl;
cout<<"9.
Mencari Data Terbesar"<<endl;
cout<<"10.
Exit"<<endl;
cout<<"Pilihan
Anda : ";
cin>>ch;
cout<<endl;
switch(ch)
{
case
1 : cout<<"Masukan Data : ";
cin>>tmp;
insert(tmp);
break;
case
2 : cout<<endl;
cout<<"Kunjungan
In-Order"<<endl;
cout<<"---------------"<<endl;
print_inorder();getch();
break;
case
6 : cout<<"Menghitung Jumlah Node"<<endl;
cout<<"------------------"<<endl;
cout<<"Jumlah
Node = "<<count(root);
getch();
break;
case
7 : cout<<"Menghitung Tinggi Pohon"<<endl;
cout<<"------------------"<<endl;
cout<<"Tinggi
Pohon = "<<height(root);
getch();
break;
case
9 : cout<<"Mecari Data Terbesar"<<endl;
cout<<"------------------"<<endl;
cout<<"Data
Terbesar Adalah = "<<endl;
cari_terbesar(root);
getch();
break;
case
10 : return 0;
break;
default:
cout<<"Pilihan yang Anda Masukkan salah!"<<endl;
getch();
break;
}
}
}
ijin share mas
BalasHapus