Algoritma dan Struktur Data : Bab 5

5.1  Aplikasi Stack

 

Stack mempunyai aplikasi yang sangat luas di bidang komputer, salah satu aplikasi yang akan kita bahas di sini adalah penggunaan stack dalam  polish notation ( notasi polish ). Sebelum dibahas tentang bagaimana penggunaan stack ini, akan disinggung terlebih dahulu tentang apakah polish notation ini.

 

Didalam menuliskan ekspresi matematika, kita selalu mempergunakanoperator dan operand. Operator adalah tanda operasi yang dipergunakan, diantaranya + (penjumlahan) , – (pengurangan), * (perkalian),  / (pembagian), ^ (pangkat), dsbnya. Sedangkan operand adalah identifier yang dipergunakan sebagai symbol, misalnya alphabet a/A … z/Z. selain operator dan operand, di dalam pengerjaan ekpresi matematika harus diperhatikan juga mengenai prioritas dari operator, dengan urutan sebagai berikut:

 

1.() Operasi dalam tanda kurung akan dikerjakan paling awal.

2. ^ ( pangkat )

3. * ( Perkalian dan / ( pembagian ).

4. + ( penjumlahan ) dan – ( pengurangan ).

 

 

 

Notasi yang dipergunakan untuk menuliskan ekspresi matematika ada tiga yaitu :

>   INFIX

Suatu notasi disebut infix jika operator  berada diantara operandnya. Notasi ini merupakan notasi yang sering kita gunakan sehari – hari.

Contoh : ( A+ B ) * ( C + D ).

 

>   PREFIX

Notasi disebut prefix,  atau sering juga di sebut  Polish Notation  ( diambil dari nama penemunya ) jika operator berada di depan dari kedua operandnya.

Contoh : +AB * + CD

 

>   POSTFIX

Suatu notasi akan disebut postfix atau  suffix  atau juga dikenal sebagai  Reverse Polish Notation  bila operator berada di belakang kedua operandnya.

Contoh : AB + CD +*.

 

INFIX

Algoritma pengerjaan operasi matematika dengan notasi infix adalah sebagai berikut :

1. Scan dari kiri ke kanan sampai ketemu dengan kurung tutup yang paling awal.

2. Scan kembali dari posisi tadi ke kiri sampai  ketemu dengan kurung buka yang pertama.

3. Lakukan operasi yang berada di dalam tanda kurung.

4. Ganti ekspresi di dalam tanda kurung tersebut dengan hasil operasi.

5. Ulangi langkah 1 sampai 4 sehingga keseluruhan ekspresi dilaksanakan.

Image

Beberapa kelemahan dari notasi infix di antaranya adalah proses pengerjaan ekspresi sangat lama, diperlukan tanda kurung untuk menandai operasi yang lebih rendah prioritasnya, dan pengerjaan sangat tidak efisien.

POSTFIX/ SUFFIX / REVERSE POLISH

Notasi postfix atau juga disebut suffix atau reverse polish notation ( selanjutnya akan dipergunakan istilah postfix ) dapat mengatasi kelemahan dari notasi infix, di antaranya adalah tidak diperlukannya tanda kurung untuk menandai operasi yang lebih tinggi prioritasnya. Lebih cepat dan efisien karena tidak diperlukan scan dari awal ekspresi.

Berikut adalah algoritma pengerjaan operasi matematika dengan notasi postfix.
1. Scan dari kiri ke kanan sampai ketemu dengan tanda operator.
2. Ambil 2 operand yang berada langsung di sebelah kiri dari operator tersebut.
3. Lakukan operasi dan ganti ekspresi tersebut dengan hasil operasi.
4. ulangi langkah 1 sampai 3 hingga keseluruhan ekspresi dilaksanakan, scan dilakukan mulai dari posisi pergantian ekspresi, jadi tidak perlu menscan dari posisi paling awal.

Dengan contoh yang dikonversikan dari notasi infix , yaitu 10 15 + 20 * 200 +, maka hasil pengerjaan dengan menggunakan notasi postfix adalah sebagai berikut :

Image

KONVERSI INFIX KE POSTFIX
Setelah mengetahui keuntungan notasi postfix dibandingkan dengan notasi infix, maka pada umumnya compiler akan dipergunakan notasi postfix di dalam mengerjakan ekspresi yang ada. Permasalahannya adalah pengguna komputer ( user ) lebih menyukai dan lebih akrab dengan notasi infix dibandingkan dengan notasi postfix, oleh karena itu diperlukan algoritma yang mengkonversikan ekspresi yang ditulis oleh user dalam notasi infix ke dalam notasi postfix sehingga dpat dikerjakan oleh compiler.

Algoritma Konversi INFIX ke POSTFIX

Infixtopostfix()
{
Postfix=” ”;
Clear(STACK);
While(!eoln(infix)) {
Read(symb);
If(symb == operand) postfix = postfix + symb;
Else {
While(!empty(STACK)) && prcd(stack[top], symb) == TRUE) {
Pop(c);
Postfix = postfix + c;
}
Push(symb);
}
}
While (!empty(STACK)) {
Pop(c);
Postfix = postfix + c;
}
}

 

Seperti terlihat pada algoritma konversi di atas, diperlukan STACK sebagai penampungan atau penyimpan operand ( kita akan menemukan operasi stack seperti pop, push, clear dan empty dalam algoritma konversi ini ), selain itu ada function lain yang diperlukan;
Precedence atau disingkat prcd; yaitu sebuah function yang akan mengecek prioritas dari dua buah operator dan akan mengembalikan nilai TRUE bila operator pertama mempunyai prioritas lebih tinggi dari operator kedua.

Contoh prcd (’’*’’, ’’+’’) TRUE
prcd (’’+’’, ’’*’’) FALSE

Algoritma di atas hanya berlaku bagi notasi infix yang tidak mempergunakan tanda kurung, untuk notasi infix yang dipergunakan tanda kurung diperlukan sedikit modifikasi terhadap algoritma di atas.

Iklan

Tinggalkan Balasan

Isikan data di bawah atau klik salah satu ikon untuk log in:

Logo WordPress.com

You are commenting using your WordPress.com account. Logout / Ubah )

Gambar Twitter

You are commenting using your Twitter account. Logout / Ubah )

Foto Facebook

You are commenting using your Facebook account. Logout / Ubah )

Foto Google+

You are commenting using your Google+ account. Logout / Ubah )

Connecting to %s