PENGGUNAAN/APLIKASI STACK

PENGGUNAAN/APLIKASI STACK

Logika stack digunakan untuk menyelesaikan berbagai macam masalah. Antara lain digunakan pada compiler, operating system dan dalam program-program aplikasi. Berikut ini tiga buah contoh aplikasi stack, yaitu :

* MATCHING PARENTHESES
Proses ini dilakukan compiler untuk memeriksa kelengkapan tanda kurung yang terdapat pada suatu ekspresi aritmetik. Sedangkan stack di sini digunakan sebagai tempat prosesnya. Algoritma yang digunakan adalah :

1. Elemen-elemen suatu ekspresi aritmetik (string) di-Scan dari kiri ke kanan.
2. Jika ditemukan simbol "(" atau "Left parenthesis", maka simbol tersebut di-push ke dalam stack.
3. Jika ditemukan simbol ")" atau "Right parenthesis", maka isi stack diperiksa.
* Jika stack kosong * terjadi kesalahan.
berarti : ada simbol ")", tetapi tidak ada simbol "(" yang seharusnya mendahului.
* Jika stack tidak kosong * artinya ada pasangannya dan langsung di-POP keluar stack.

* NOTASI POSTFIX
Bentuk aplikasi stack yang lain adalah mengubah suatu ekspresi aritmatik (string) ke dalam notasi postfix. Notasi postfix ini digunakan oleh compiler untuk menyatakan suatu ekspresi aritmatik dalam bahasa tingkat tinggi (high level language). Stack digunakan oleh compiler untuk mentransformasikan ekspresi aritmatik menjadi suatu ekspresi dalam bentuk/notasi postfix.

Contoh :
Misal diberikan ekspresi aritmatik : A + B ;

Maka bentuknya dalam notasi postfix menjadi : AB+

Urutan (prioritas) dari operator adalah

1. Perpangkatan (^)
2. Perkalian (*) atau Pembagian (/)
3. Penjumlahan (+) atau Pengurangan (-)


Aturan yang digunakan dalam proses transformasi tersebut adalah :

1.Ekspresi aritmatik yang diberikan di- "Scan" dari kiri ke kanan.
2.Bila simbol yang di-scan adalah "(", maka simbol tersebut di push ke dalam stack.
3.Bila simbol yang di-scan adalah ")", maka seluruh isi stack di pop keluar mulai dari simbol "(" yang pertama ditemukan dalam stack.
4.Bila simbol adalah operator, maka dilakukan perbandingan dulu dengan simbol (operator) yang berada pada posisi top dalam stack.
a.Jika derajatnya setara atau lebih rendah dari simbol yang berada pada posisi top, maka top stack di-pop keluar sebagai output dan simbol yang baru di-push ke dalam stack.
b. Jika derajatnya lebih tinggi dari simbol yang berada pada posisi top, maka simbol (operator) yang di-scan tersebut di-push ke dalam stack.
5.Bila simbol yang di-scan adalah operand, maka simbol tersebut langsung sebagai output.
6.Bila simbol adalah ";" maka seluruh isi stack di-pop sebagai output.

Contoh :
Misal diberikan sebuah ekspresi aritmatik dengan bentuk sbb:

( (A + B) * C / D + E ^ F ) / G ;

dalam notasi postfix menjadi : AB+D*C/EF^+G/