STACK
Stack adalah suatu koleksi atau kumpulan item data yang teroganisasi
dalam bentuk urutan linear, yang operasi pemasukan dan penghapusan
datanya dilakukan pada salah satu sisinya.
Konversi notasi infix ke postfix
Berdasarkan teori yang diterangkan tersebut di atas, proses konversi infix menjadi notasi Postfix dalam implementasinya membutuhkan stack pada proses konversinya, adapun proses tersebut memiliki 4 (empat) aturan yang digunakan, yaitu :
• Jika ditemukan simbol kurung buka “(“
Operasi push pada stack akan digunakan untuk menyimpan simbol tersebut ke dalam stack.
• Jika ditemukan simbol kurung buka “)”
Operasi pop digunakan untuk mengeluarkan operator-operator yang berada di dalam stack.
• Jika terdapat simbol operator
Jika dalam suatu untai notasi infix ditemukan simbol operator maka operasi yang dilakukan pada stack terbagi atas :
1. Jika TOP(S) dari stack tersebut kosong atau berisi simbol “(“ maka operasi push akan digunakan untuk memasukan operator tersebut pada posisi di TOP(S)
2. Jika operator yang berada dipuncak stack merupakan elemen yang memiliki tingkat yang sama atau lebih tinggi maka operasi pop digunakan untuk mengeluarkan operator tersebut diikuti operasi push untuk menyimpan operator hasil scanning untai.
3. Jika operator yang berada di puncak stack memiliki tingkat yang lebih rendah dari operator yang discan, maka operator baru akan langsung dimasukan ke dalam stack dengan operasi push.
Adapun tingkatan operator yang dilacak menurut urutan tingkat adalah :
Tabel 1. Level Operator dalam stack
Operator Level Operator dalam stack
** Tertinggi
* atau / Menengah
+ atau - Rendah
4. Jika ditemukan suatu operand
Nilai operand yang ada langsung dijadikan output dari notasi Postfix.
Dicontohkan dalam suatu aplikasi suatu ekspresi aritmatika dalam notasi infix sebagai berikut
((A * B) + C / D – E ** F) * G;
Ekspresi tersebut di atas, dikonversikan ke dalam bentuk notasi Postfix digambarkan sebagai berikut :
Indeks urutan ke- 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
Karakter-karakter yang akan dilacak dalam notasi infix ( ( A * B ) + C / D - E ** F ) * G ;
Operator puncak (TOP(S) ( (
( (
( *
(
( *
(
( ( +
( +
( /
+
( /
+
( -
( -
( **
-
( **
-
( * *
Output yg dihasilkan dalam bentuk postfix A B * C D / + F ** - G *
o Karakter-karakter yang akan dilacak dalam notasi infix
o Output yang dihasilkan dalam notasi Postfix
Dari contoh untai tersebut di atas, maka hasil konversi dari notasi infix menjadi notasi Postfix menghasilkan untai : A B * C D /+ E F **- G *
3.2. Implementasi algoritma Stack
Pada bahasa pemrograman PASCAL suatu stack didefinisikan dalam bentuk algoritma, hal ini dimaksudkan untuk mendapatkan hasil yang optimal dan terarah saat program tersebut di rancang dan digunakan. Dari teori tentang penggunaan stack dalam struktur data sebelumnya, suatu stack memiliki dua informasi penting yaitu adanya TOP(S) yang berisikan informasi isi untai dalam bentuk karakter dan NOEL(S) yang berisikan informasi jumlah untai yang bernilai integer dari stack tersebut.
Pada implementasinya, kedua informasi tersebut dikemas dalam bentuk record yang memuat array (larik) untuk membatasi isi dari stack, dan memberikan nilai indeks atas informasi yang masuk dalam stack tersebut pada saat dilakukan operasi. Adapun secara algoritma stack tersebut di bentuk sebagai :
Const
NoelStack = 80;
Type
Eon = Char;
Stack = Record
Top : Array [ 1 .. NoelStack] of Eon;
Noel : 0 .. NoelStack;
End;
Dari algoritma tersebut di atas, isi dari stack dapat menampung 80 karakter yang dikemas dalam bentuk record dengan nama stack.
Setelah algoritma yang memuat informasi dasar dari stack didefinisikan, pembentukan algoritma untuk operasi terhadap stack dapat disusun dalam bentuk prosedur dan fungsi yang dibuat sendiri. Adapun algoritma yang digunakan untuk operasi suatu stack adalah :
1) Algoritma Create(S)
Algoritma ini memuat suatu prosedur untuk membuat stack, yang memberikan kondisi noel dari stack akan bernilai nol dan top dari stack tersebut belum dapat didefinisikan, sehingga implementasi dari algoritma create stack adalah ;
Procedure Create(var S : Stack);
Begin
S.Noel := 0;
End;
2) Algoritma IsEmpty(S)
Algoritma untuk operasi Isempty memberikan informasi Boolean yaitu kondisi benar (true) atau salah (False), sehingga pada implementasinya algoritma ini menggunakan fungsi yang dibuat sendiri, yang terimplementasi sebagai berikut :
Function IsEmpty(Var S : Stack) : Boolean;
Begin
IsEmpty := S.Noel = 0
End;
3) Algoritma Push(S, E)
Dalam merancang algoritma untuk operasi push dimulai dengan melakukan pengecekan atas isi dari stack tersebut dalam keadaan penuh atau tidak. Kondisi stack dalam keadaan maksimum akan mengakibatkan overflow pada stack tersebut sehingga prosedur error trapping perlu didefinisikan untuk mencegah terjadinya overflow condition tersebut. Adapun implementasi dari algoritma push tersebut adalah :
Procedure Push(Var S : Stack; TipeBAru : Eon);
Begin
If S.Noel = NoelStack Then
Stackerror(1)
Else
Begin
S.Noel := S.Noel + 1;
S.Top[S.Noel] := TipeBaru
End
End;
4) Algoritma Pop(S)
Operasi terakhir dari stack adalah operasi pop yang berfungsi untuk mengeluarkan isi dari dalam stack. Seperti halnya operasi push, pada operasi pop penggunaan error trapping dipakai untuk mencek kondisi underflow yaitu kondisi stack kosong yang dikenakan operasi pop. Algoritma dari pop ini adalah :
Procedure Pop(Var S : Stack; Var NilaiStack : Eon);
Begin
If S.Noel = 0 Then
StackError(2)
Else
Begin
NilaiStack := S.Top[s.Noel];
S.Noel := S.Noel -1
End
End;
Penggunaan error trapping untuk operasi push dan pop didefinisikan lebih lanjut dalam algoritma stackerror yang digunakan untuk menentukan kondisi overflow atau underflow suatu stack. Adapun algoritma dari error trapping ini adalah ;
Procedure StackError(TingkatanError : Integer);
Begin
Case TingkatanError of
1 : WriteLn(‘Isi Stack sudah penuh... kondisi overflow’);
2 : WriteLn(‘Isi Stack Kosong ... kondisi underflow’)
End
End;
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.
Operasi-operasi dasar pada stack :
a. Cek Stack kosong (Isempty)
Fungsi yang melakukan pengecekan apakah stack dalam kondisi kosong.
public int isempty()
if(posisi==0)
System.out.println("Data Kosong");
return 1;
else
System.out.println("Data ada");
return 0;
b. Cek Stack penuh (full)
Fungsi yang melakukan pengecekan apakah stack dalam kondisi penuh atau tidak.
public int full()
if(posisi==MAX)
System.out.println(”Stack Penuh”);
return 0;
else
return 1;
c. Operasi Push
Operasi push dalam stack adalah operasi yang memasukkan elemen yang akan diletakkan pada posisi teratas dari tumpukan.
public void push (int data)
if(posisi
isistack[++posisi] = data;
d. Operasi Pop
Operasi pop dalam stack adalah operasi untuk mengambil/menghapus elemen yang terletak pada posisi paling atas dari sebuah tumpukan.
public void pop()
int y=0;
if(posisi != 0)
isistack[posisi--]=y;
e. Cek posisi Teratas (Peek)
Operasi peek digunakan untuk mengecek posisi teratas dalam stack.
public void peek()
System.out.print("Posisi Atas= ");
if(posisi != 0)
System.out.print(isistack[posisi]);
System.out.println();
Penerapan stack :
Konversi notasi infix ke postfix
Berdasarkan teori yang diterangkan tersebut di atas, proses konversi infix menjadi notasi Postfix dalam implementasinya membutuhkan stack pada proses konversinya, adapun proses tersebut memiliki 4 (empat) aturan yang digunakan, yaitu :
• Jika ditemukan simbol kurung buka “(“
Operasi push pada stack akan digunakan untuk menyimpan simbol tersebut ke dalam stack.
• Jika ditemukan simbol kurung buka “)”
Operasi pop digunakan untuk mengeluarkan operator-operator yang berada di dalam stack.
• Jika terdapat simbol operator
Jika dalam suatu untai notasi infix ditemukan simbol operator maka operasi yang dilakukan pada stack terbagi atas :
1. Jika TOP(S) dari stack tersebut kosong atau berisi simbol “(“ maka operasi push akan digunakan untuk memasukan operator tersebut pada posisi di TOP(S)
2. Jika operator yang berada dipuncak stack merupakan elemen yang memiliki tingkat yang sama atau lebih tinggi maka operasi pop digunakan untuk mengeluarkan operator tersebut diikuti operasi push untuk menyimpan operator hasil scanning untai.
3. Jika operator yang berada di puncak stack memiliki tingkat yang lebih rendah dari operator yang discan, maka operator baru akan langsung dimasukan ke dalam stack dengan operasi push.
Adapun tingkatan operator yang dilacak menurut urutan tingkat adalah :
Tabel 1. Level Operator dalam stack
Operator Level Operator dalam stack
** Tertinggi
* atau / Menengah
+ atau - Rendah
4. Jika ditemukan suatu operand
Nilai operand yang ada langsung dijadikan output dari notasi Postfix.
Dicontohkan dalam suatu aplikasi suatu ekspresi aritmatika dalam notasi infix sebagai berikut
((A * B) + C / D – E ** F) * G;
Ekspresi tersebut di atas, dikonversikan ke dalam bentuk notasi Postfix digambarkan sebagai berikut :
Indeks urutan ke- 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
Karakter-karakter yang akan dilacak dalam notasi infix ( ( A * B ) + C / D - E ** F ) * G ;
Operator puncak (TOP(S) ( (
( (
( *
(
( *
(
( ( +
( +
( /
+
( /
+
( -
( -
( **
-
( **
-
( * *
Output yg dihasilkan dalam bentuk postfix A B * C D / + F ** - G *
o Karakter-karakter yang akan dilacak dalam notasi infix
o Output yang dihasilkan dalam notasi Postfix
Dari contoh untai tersebut di atas, maka hasil konversi dari notasi infix menjadi notasi Postfix menghasilkan untai : A B * C D /+ E F **- G *
3.2. Implementasi algoritma Stack
Pada bahasa pemrograman PASCAL suatu stack didefinisikan dalam bentuk algoritma, hal ini dimaksudkan untuk mendapatkan hasil yang optimal dan terarah saat program tersebut di rancang dan digunakan. Dari teori tentang penggunaan stack dalam struktur data sebelumnya, suatu stack memiliki dua informasi penting yaitu adanya TOP(S) yang berisikan informasi isi untai dalam bentuk karakter dan NOEL(S) yang berisikan informasi jumlah untai yang bernilai integer dari stack tersebut.
Pada implementasinya, kedua informasi tersebut dikemas dalam bentuk record yang memuat array (larik) untuk membatasi isi dari stack, dan memberikan nilai indeks atas informasi yang masuk dalam stack tersebut pada saat dilakukan operasi. Adapun secara algoritma stack tersebut di bentuk sebagai :
Const
NoelStack = 80;
Type
Eon = Char;
Stack = Record
Top : Array [ 1 .. NoelStack] of Eon;
Noel : 0 .. NoelStack;
End;
Dari algoritma tersebut di atas, isi dari stack dapat menampung 80 karakter yang dikemas dalam bentuk record dengan nama stack.
Setelah algoritma yang memuat informasi dasar dari stack didefinisikan, pembentukan algoritma untuk operasi terhadap stack dapat disusun dalam bentuk prosedur dan fungsi yang dibuat sendiri. Adapun algoritma yang digunakan untuk operasi suatu stack adalah :
1) Algoritma Create(S)
Algoritma ini memuat suatu prosedur untuk membuat stack, yang memberikan kondisi noel dari stack akan bernilai nol dan top dari stack tersebut belum dapat didefinisikan, sehingga implementasi dari algoritma create stack adalah ;
Procedure Create(var S : Stack);
Begin
S.Noel := 0;
End;
2) Algoritma IsEmpty(S)
Algoritma untuk operasi Isempty memberikan informasi Boolean yaitu kondisi benar (true) atau salah (False), sehingga pada implementasinya algoritma ini menggunakan fungsi yang dibuat sendiri, yang terimplementasi sebagai berikut :
Function IsEmpty(Var S : Stack) : Boolean;
Begin
IsEmpty := S.Noel = 0
End;
3) Algoritma Push(S, E)
Dalam merancang algoritma untuk operasi push dimulai dengan melakukan pengecekan atas isi dari stack tersebut dalam keadaan penuh atau tidak. Kondisi stack dalam keadaan maksimum akan mengakibatkan overflow pada stack tersebut sehingga prosedur error trapping perlu didefinisikan untuk mencegah terjadinya overflow condition tersebut. Adapun implementasi dari algoritma push tersebut adalah :
Procedure Push(Var S : Stack; TipeBAru : Eon);
Begin
If S.Noel = NoelStack Then
Stackerror(1)
Else
Begin
S.Noel := S.Noel + 1;
S.Top[S.Noel] := TipeBaru
End
End;
4) Algoritma Pop(S)
Operasi terakhir dari stack adalah operasi pop yang berfungsi untuk mengeluarkan isi dari dalam stack. Seperti halnya operasi push, pada operasi pop penggunaan error trapping dipakai untuk mencek kondisi underflow yaitu kondisi stack kosong yang dikenakan operasi pop. Algoritma dari pop ini adalah :
Procedure Pop(Var S : Stack; Var NilaiStack : Eon);
Begin
If S.Noel = 0 Then
StackError(2)
Else
Begin
NilaiStack := S.Top[s.Noel];
S.Noel := S.Noel -1
End
End;
Penggunaan error trapping untuk operasi push dan pop didefinisikan lebih lanjut dalam algoritma stackerror yang digunakan untuk menentukan kondisi overflow atau underflow suatu stack. Adapun algoritma dari error trapping ini adalah ;
Procedure StackError(TingkatanError : Integer);
Begin
Case TingkatanError of
1 : WriteLn(‘Isi Stack sudah penuh... kondisi overflow’);
2 : WriteLn(‘Isi Stack Kosong ... kondisi underflow’)
End
End;
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.
Operasi-operasi dasar pada stack :
a. Cek Stack kosong (Isempty)
Fungsi yang melakukan pengecekan apakah stack dalam kondisi kosong.
public int isempty()
if(posisi==0)
System.out.println("Data Kosong");
return 1;
else
System.out.println("Data ada");
return 0;
b. Cek Stack penuh (full)
Fungsi yang melakukan pengecekan apakah stack dalam kondisi penuh atau tidak.
public int full()
if(posisi==MAX)
System.out.println(”Stack Penuh”);
return 0;
else
return 1;
c. Operasi Push
Operasi push dalam stack adalah operasi yang memasukkan elemen yang akan diletakkan pada posisi teratas dari tumpukan.
public void push (int data)
if(posisi
isistack[++posisi] = data;
d. Operasi Pop
Operasi pop dalam stack adalah operasi untuk mengambil/menghapus elemen yang terletak pada posisi paling atas dari sebuah tumpukan.
public void pop()
int y=0;
if(posisi != 0)
isistack[posisi--]=y;
e. Cek posisi Teratas (Peek)
Operasi peek digunakan untuk mengecek posisi teratas dalam stack.
public void peek()
System.out.print("Posisi Atas= ");
if(posisi != 0)
System.out.print(isistack[posisi]);
System.out.println();
Penerapan stack :
Stack digunakan untuk menuliskan ungkapan menggunakan notasi tertentu
(Notasi Polish). Biasanya ungkapan yang digunakan adalah ungkapan
numeris. Sebagai contoh ungkapan (A + B)*(C – D) apabila ditulis dengan
menggunakan notasi Polish menjadi * + A B – C D.
Posted By : Holong Rianto
Tidak ada komentar:
Posting Komentar