Contoh Kasus Penggunaan Stack: Komputasi Ekspresi Aritmatika

Sebagaimana yang telah dibahas di kelas yang lalu (ada di slide sebelumnya), stack dapat digunakan untuk pemeriksaan pasangan tanda kurung. Tanpa stack, algoritma nonrekursif membutuhkan kompleksitas O(n2). Algoritma rekursif bisa mencapai O(n) namun dengan penggunaan stack internal.

Dalam kuliah ini satu contoh lagi dibahas mengenai manfaat stack. Problemnya adalah melakukan komputasi berdasar ekspresi aritmatika yang diberikan. Problem ini dalam buku teks dibahas dalam konteks “Kalkulator Sederhana”. Namun, solusi yang dibahas, secara umum ditemukan juga dalam sebagian implementasi compiler/interpreter.

Algoritma komputasi menggunakan stack yang mampu menghasilkan kompleksitas O(n), dengan n jumlah token dalam ekspresi. Algoritma terdiri atas dua tahap: (1) konversi infiks menjadi posfiks, dan (2) komputasi ekspresi posfiks.

Slide materi kuliah dapat didownload disini (versi ini sudah hasil revisi akibat adanya sejumlah kesalahan dan ditambah dua halaman slide untuk menambah kejelasannya).

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s