Tulisan ini di buat untuk rekan-rekan yang belajar tentang struktur data dan bagaimana implementasi dari struktur data tersebut dalam suatu aplikasi sederhana. Walau penerapan dari tulisan ini dibuat dalam bahasa Pascal bukan berarti tidak dapat di implementasikan ke bahasa pemrograman lain seperti dalam bahasa VB, VB.NET ataupun juga dalam bahasa C yang lebih banyak menjelaskan implementasi dari suatu teorema struktur data.
1. PENDAHULUAN
Stack merupakan bagian dari struktur data yang dikategorikan ke dalam bentuk linear data, dimana operasi pemasukan maupun pengeluaran data selalu dilakukan pada salah satu sisinya[1]. Dalam dunia komputer, penggunaan
stack (tumpukan) merupakan suatu hal yang umum digunakan seperti untuk penentuan alamat memory, penempatan ruang data dan aplikasi lain. Sebagai bagian dari struktur data, aplikasi
stack juga digunakan untuk berbagai macam keperluan seperti pengujian kalimat
palindrome, penguji tanda kurung (matching parentheses), dan juga berfungsi sebagai konversi dari notasi
infix menjadi notasi
postfix.
Pada perhitungan aritmatika, notasi
infix adalah notasi yang menempatkan operator ditengah dua operand sedangkan notasi
Postfix adalah notasi yang menempatkan operator setelah dua operand. Penggunaan notasi
infix merupakan hal yang lumrah digunakan dalam perhitungan aritmatika dibandingkan dengan penggunaan notasi
Postfix, akan tetapi bagi mesin kompilasi notasi
Postfix merupakan notasi yang digunakan untuk melakukan suatu perhitungan.
Tulisan ini dibuat untuk memberikan gambaran secara jelas proses simulasi konversi atas dua notasi aritmatika tersebut, berdasarkan studi literatur dari beberapa buku dan dituangkan dengan bantuan bahasa pemrograman Pascal. Adapun proses konversi ini ditujukan untuk menjelaskan bagaimana mesin kompilasi dapat merubah notasi
infix yang biasa digunakan oleh berbagai kalangan menjadi notasi
Postfix yang dimengerti oleh mesin kompilasi sehingga suatu proses perhitungan aritmatika dapat dilaksanakan oleh komputer. Alasan pemilihan bahasa pemrograman Pascal digunakan karena fleksibilitas bahasa tersebut dalam menerangkan implementasi dan aplikasi dari struktur data dalam bentuk pemrograman [2].
2. TEORI
2.1. Definisi
Dalam dunia komputer, penggunaan
stack atau tumpukan merupakan salah satu komponen penting untuk menjamin proses penanganan suatu data disamping hal lain seperti Queue (antrian), linked list, dan tree.
Definisi 1.
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[1]
Definisi 2.
Diberikan suatu himpunan yang terurut himpunan sebagai S = {S
1, S
2, ......., S
T}, T pada anggota S merupakan linear order, sehingga
stack dari himpunan tersebut memiliki informasi sebagai berikut [1] :
1. Elemen puncak dari
stack dalam himpunan S dikatakan sebagai TOP
, sehingga :
TOP[S} = ST ............................................................................(1)
2. Banyaknya elemen
stack dalam himpunan S dikatakan sebagai NOEL
, sehingga NOEL
= T, dimana himpunan dari S tersebut dapat disusun sebagai :
S = {S1, S2, .........., SNOEL} .............................(2)
Dari dua definisi tersebut di atas maka suatu
stack dapat digambarkan sebagai berikut :
1. Suatu
stack dalam keadaan kosong akan memiliki informasi NOEL(S) = 0 dan TOP(S)= undefined.
S
2. Untuk
stack yang bukan kosong, maka akan memiliki informasi seperti yang digambarkan di bawah ini dimana informasi yang ada adalah NOEL(S) = 1 dan TOP(S) = Merah
S
Untuk stack yang berisi lebih dari n jumlah data maka informasi yang ada pada stack tersebut berisikan NOEL(S) = 2 (jika berisi 2 data) dan TOP(S) = Biru seperti ditunjukan pada gambar di bawah ini :
S
Elemen-elemen yang berada dalam
stack tersebut di atas, memiliki prinsip dasar dalam pengoperasiannya yaitu prinsip
LIFO (
Last In First Out) atau yang masuk paling belakang akan memiliki prioritas untuk keluar paling depan.
Suatu
stack dapat digambarkan sebagai suatu array (larik) berdimensi satu yang elemen-elemennya berkisar antara 1 sampai n elemen. Dengan demikian jika suatu
stack didefinisikan dengan n elemen maka dapat dikatakan jumlah maksimum dari
stack atau NOEL(S) nya adalah n, sehingga penambahan elemen
stack yang ke n+1 tidak diperkenankan atau
stack tersebut dalam kondisi
overflow. Hal tersebut juga berlaku untuk
stack dengan nilai minimum yaitu NOEL(S) dari
stack dalam kondisi 0, jika dilakukan operasi pengambilan elemen atas
stack tersebut akan mengakibatkan
stack tersebut dalam kondisi
underflow. Dua kondisi tersebut merupakan dasar dalam merancang suatu aplikasi pemrograman komputer.
2.2. Operasi-operasi Stack
Dalam penggunaannya suatu
stack memiliki beberapa operasi yang dapat diterapkan seperti membuat
stack, penambahan eleme ke dalam
stack, menghapusan elemen dari dalam
stack, dan operasi lain yang berhubungan dengan
stack tersebut. Adapun operasi-operasi dasar dari suatu
stack adalah :
a) Create(Stack)
Operasi Create(
Stack) digunakan untuk membuat suatu
stack baru dengan nama
stack, yang nilai elemen saat
stack tersebut dibuat adalah NOEL(S) = 0, TOP(S) = NULL (tidak terdefinisikan)
b) IsEmpty(Stack)
Operasi ini merupakan operasi untuk mencek isi dari suatu
stack dalam keadaan kosong atau berisi. Operasi ini memiliki 2 (dua) kondisi boolean yaitu :
a.
True jika
stack tersebut kosong atau dapat dikatakan NOEL(S) = 0
b.
False jika
stack tersebut tidak dalam kondisi kosong atau dapat dikatakan NOEL(S) > 0
c) Push(Stack, Elemen)
Operasi ini merupakan operasi untuk menambahkan satu elemen dengan nilai X pada puncak suatu
stack, sehingga posisi TOP(S) akan bernilai X, penerapan operasi push pasa suatu
stack S akan berakibat overflow jika NOEL(S) dari
stack tersebut telah bernilai maksimum.
d) Pop(Stack)
Operasi ini berfungsi untuk menghapus satu elemen dari
stack S, sehingga posisi NOEL(S) akan berkurang satu elemen, dan TOP(S) akan berubah. Operasi pop dapat menyebabkan kondisi underflow jika suatu
stack S yang berada dalam kondisi minimum dikenakan operasi pop.
2.3. Notasi Infix dan Postfix
Suatu perhitungan aritmatika biasanya berhubungan dengan operand dan operator. Operand merupakan suatu karakter atau elemen yang nilainya dioperasikan dengan bantuan suatu operator untuik menghasilkan suatu solusi.
Misalkan jika diberikan suatu ekspresi aritmatika 2 * 3, maka elemen ‘dua’ dan elemen ‘tiga’ merupakan operand dari ekspresi tersebut dan elemen ‘*’ merupakan operator perkalian atas dua operand yang menghasilkan suatu solusi. Suatu ekspresi aritmatika dapat dibedakan dalam tiga bentuk notasi perhitungan yaitu :
1)
Notasi prefix, jika operator ditempatkan sebelum dua operand
2)
Notasi infix, jika operator ditempatkan diantara dua operand
3)
Notasi postfix, jika operator ditempatkan setelah dua operand
Dalam penggunaannya, dalam kehidupan sehari-hari notasi
infix merupakan notasi aritmatika yang paling banyak digunakan untuk mengekspresikan suatu perhitungan artimatik dibanding dengan dua notasi yang lain, akan tetapi notasi
Postfix merupakan notasi yang digunakan oleh mesin kompilasi pada komputer dengan maksud untuk mempermudah proses pengkodean, sehingga mesin kompilasi membutuhkan
stack untuk proses translasi ekspresi tersebut.
3. PEMBAHASAN
3.1.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 :
- Jika TOP(S) dari stack tersebut kosong atau berisi simbol “(“ maka operasi push akan digunakan untuk memasukan operator tersebut pada posisi di TOP(S)
- 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.
- 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 | * |
- Karakter-karakter yang akan dilacak dalam notasi infix
- 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;
3.3.Implementasi Proses Konversi Notasi Infix ke Notasi Postfix
Dari operasi dasar yang dapat diterapkan pada suatu
stack tersebut, tahap kedua dari pelaksanaan konversi notasi
infix ke notasi
Postfix adalah merancang bangun algoritma proses konversi, dengan cara melakukan perbandingan isi operator yang berada di dalam
stack dengan operator yang dibaca untuk dimasukan dalam
stack. Adapun proses perbandingan tersebut di lihat berdasarkan tingkatan operator yang tertuang dalam tabel berikut :
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 Isidlm
stack 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 KonversiInfixKePostfix
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, '(');
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
4. KESIMPULAN
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.
DAFTAR PUSTAKA
[1] LOOMIS, Mary E.S.,
Data Management and File Processing, Prentice-Hall, Inc., Englewood Cliffs, New Jersey, 1985.
[2] HOROWITZ, E and Sahni S.,
Fundamental of Computer Algorithms, Computer Science Press, Potomac, Maryland, 1978.
[3] MCCRACKEN, Daniel D.,
A Second Course in Computer Science with Pascal, John Willey & Sons, City College, New York, 1989
