Sabtu, 29 Mei 2010

Algoritma Stack (infiks ke postfix)

Algoritma yang dilakukan untuk mengubah notasi infiks ke postfix adalah sbb :
1. Lakukan pemasukan elemen dalam ekspresi satu per satu
2. Bila elemen yang dimasukkan adalah operand, maka jadikan hasil saja, lanjutkan proses 1. Bila bukan operand, jalankan proses 3.
3. Bila stack dalam keadaan hampa, masukkan elemen tersebut dan lanjutkan proses 1. Bila tidak hampa, jalankan proses 4.
4. Bila elemen yang diperiksa adalah operator ')', keluarkan semua isi elemen (digabungkan dengan hasil sebelumnya) mulai TOP hingga '('. Abaikan (buang)operator '(' dan ')' dari hasil, karenapostfix tidak menggunakan mereka, lanjutkan proses 1. Bila bukan operator ')', jalankan proses 5.
5. Bila elemen yang diperiksa memiliki tingkat derajat lebih kecil atau sama dengan TOP stack, keluarkan (digabung dengan hasil sebelumnya) TOP stack. TOP stack menjadi TOP - 1. Ulangi proses 5 ini sampai tingkat derajat yang ada di TOP stack kebih kecil, atau TOP stack berisi '(', atau stack dalam keadaan hampa, baru elemen tersebut dimasukkan. Lanjutkan proses 1
6. Bila elemen telah habis, keluarkan seluruh isi stack. Selesai.


Tingkatan derajat operator dari besar ke kecil :
1. ^ pangkat atau eksponen
2. * atau / perkalian atau pembagian (proses yang paling kiri dulu)
3. + atau - penambahan atau pengurangan (proses yang kiri dulu)


Sumber : Bambang Wahyudi, 2004, Pengantar Struktur Data dan Algoritma, Yogyakarta : Penerbit Andi.

Selasa, 25 Mei 2010

Stack (Tumpukan)

STRUKTUR DATA TUMPUKAN (STACK)

Adalah kumpulan elemen-elemen data yang disimpan dalam satu lajur linier, kumpulan elemen-elemen data hanya boleh diakses pada satu lokasi saja yaitu pada posisi ATAS (TOP) tumpukan.

Operasi-operasi dasar pada STACK (tumpukan)
a. CREATESTACK(S) : Membuat tumpukan baru S, dengan jumlah elemen kosong.
b. MAKENULL(S) : Mengosongkan tumpukan S, jika ada elemen maka semua elemen akan dihapus.
c. EMPTY : Tumpukan kosong? – menguji apakah tumpukan kosong.
d. PUSH(x,S) : Memasukan elemen baru x kedalam Tumpukan S.
e. POP(S) : Mengeluarkan elemen posisi atas pada Tumpukan S.
Ilustrasi operasi POP dan PUSH terhadap stack (Tumpukan)

No. OPERASI ISI TUMPUKAN NILAI TOP
1 CREATESTACK(S) 0
2 PUSH(‘a’,S) a 1
3 PUSH(‘b’,S) a b 2
4 PUSH(‘c’,S) a b c 3
5 POP(S) a b 2
6 PUSH(‘d’,S) a b d 3
7 PUSH(‘e’,S) a b d e 4
8 POP(S) a b d 3
9 POP(S) a b 2
10 POP(S) a 1
Apa yang terjadi bila dilakukan POP(S) sebanyak dua kali lagi? UNDERFLOW

Algoritma PUSH : PUSH(S, TOP, MAKSTUM, ELEMEN)
1. [Periksa kandungan tumpukan, apakah penuh?]
Jika TOP=MAKSTUM; Cetakan ‘OVERFLOW’
2. [Tambahkan TOP dengan 1]
TOP := TOP+1
3. [Masukan ELEMEN kedalam lokasi TOP yang baru]
S[TOP] := ELEMEN;
4. Return

Algoritma POP : POP(S, TOP, ELEMEN)
1. [Periksa kandungan Tumpukan, apakah kosong ?]
Jika TOP = 0 ; Cetakan ‘UNDERFLOW’
2. [Simpan nilai teratas pada ELEMEN]
ELEMEN := S[TOP]
3. [Kurangkan TOP dengan 1]
TOP := TOP-1
4. Return

NOTASI ARITMETIK (INFIX, PREFIX, DAN POSTFIX)
Notasi aritmetik biasa ditulis dalam notasi Infix, missal A+B-C. Notasi infix mudah dimengerti oleh manusia, hanya saja dalam notasi infix perlu diperhatikan prioritas pengerjaan karena berhubungan dengan hirarki operator pada computer. Prioritas pengerjaannya adalah :
1. Tanda kurung : ( …. )
2. Eksponensial atau pangkat : ^
3. Perkalian, pembagian : * , /
4. Penjumlahan, Pengurangan : +, -

Contoh : (A-B) * (C+D)
Prioritas pengerjaan soal diatas adalah sebagai berikut :
a. Dalam kurung yang paling kiri : (A-B)
b. Dalam kurung yang kedua : (C-D)
c. Perkalian hasil pengurangan dengan hasil penjumlahan.

Notasi Prefix dan Notasi Postfix lebih mudah dikerjakan oleh computer.

PREFIX adalah keadaan dimana symbol operator diletakan sebelum dua operand.
POSTFIX adalah keadaan dimana symbol operator diletakan sesudah dua operand.

Aturan notasi infix, prefix dan postfix :

- Notasi Infix : operand operator operand A + B
- Notasi Prefix : operator operand operand + A B (disebut juga Poslish Notation – PN)
- Notasi Postfix : Operand operand operator (disebut juga Reveser Polish Notation – RPN)

Contoh ke-1 : INFIX ke PREFIX (A+B) – (C*D)
Cara pengerjaan :
a. Pengerjaan dalam kurung ke-1 : (A+B), prefixnya adalah +AB
b. Pengerjaan dalam kurung ke-2 : (C*D), prefixnya adalah *CD
c. Terakhir adalah operator - , +AB - *CD, prefix nya adalah -+AB * CD

Contoh ke-2 : INFIX ke POSTFIX (A+B) – (C*D)
Cara pengerjaan :
a. Pengerjaan dalam kurung ke-1 : (A+B), postfixnya adalah AB+
b. Pengerjaan dalam kurung ke-2 : (C*D), postfixnya adalah CD*
c. Terakhir adalah operator - , AB+ - CD*, postfix nya adalah AB+ CD*-

Contoh ke-3 : PREFIX ke INFIX: +/*ABCD
Cara pengerjaan : mencari operator dimulai dari operand terkanan.
a. Cari operator ke-1 : *, ambil dua operand sebelumnya A dan B, sehingga infixnya adalah (A*B)
b. Cari operator ke-2 : /, ambil dua operand sebelumnya (A*B) dan C, sehingga infixnya adalah ((A*B)/C)
c. Cari operator ke-3 : +, ambil dua operand sebelumnya ((A*B)/C) dan D, sehingga infixnya adalah ((A*B)/C)+D


Contoh ke-4 : PREFIX ke POSTFIX: +/*ABCD
Cara pengerjaan : mencari operator dimulai dari operand terkanan.
a. Cari operator ke-1 : *, ambil dua operand sebelumnya A dan B, sehingga postfixnya adalah AB*
b. Cari operator ke-2 : /, ambil dua operand sebelumnya AB* dan C, sehingga postfixnya adalah AB* C/
c. Cari operator ke-3 : +, ambil dua operand sebelumnya AB* C/ dan D, sehingga postfixnya adalah AB* C/ D+


Contoh ke-5 : POSTFIX ke INFIX : ABCD*/-
Cara pengerjaan : mencari operator dimulai dari operand terkiri.
a. Cari operator ke-1 : *, ambil dua operand sebelumnya C dan D, sehingga infixnya adalah (C*D)
b. Cari operator ke-2 : /, ambil dua operand sebelumnya B dan (C*D), sehingga infixnya adalah (B/(C* D))
c. Cari operator ke-3 : -, ambil dua operand sebelumnya A dan (B/(C* D)), sehingga infixnya adalah A- (B/(C* D)).

Contoh ke-6 : POSTFIX ke PREFIX : ABCD*/-
Cara pengerjaan : mencari operator dimulai dari operand terkiri.
a. Cari operator ke-1 : *, ambil dua operand sebelumnya C dan D, sehingga prefixnya adalah *CD
b. Cari operator ke-2 : /, ambil dua operand sebelumnya B dan *CD, sehingga prefixnya adalah /B *CD
c. Cari operator ke-3 : - , ambil dua operand sebelumnya A dan /B *CD, sehingga prefixnya adalah –A /B *C

Sumber : Teddy Markus Zakaria, Agus Prijono.2005.Konsep dan Implementasi Struktur Data. Bandung : Penerbit Informatika