APLIKASI STACK PADA STRUKTUR DATA UNTUK MENGKONVERSIKAN NOTASI INFIX MENJADI NOTASI POSTFIX

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₁, S₂, ......., 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} = S_{T ............................................................................}(1)

2. Banyaknya elemen stack dalam himpunan S dikatakan sebagai NOEL, sehingga NOEL = T, dimana himpunan dari S tersebut dapat disusun sebagai :

S = {S₁, S₂, .........., S_NOEL} .............................(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 :

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	*

• 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 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 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