1

Pertemuan 06

Aplikasi STACK

Matakuliah : T0534/Struktur Data

Tahun : 2005

Versi : September 2005

2

Learning Outcomes

Pada akhir pertemuan ini, diharapkan mahasiswa

akan mampu :• mendemonstrasikan TDA Stack (TIK-05).• menerapkan STACK pada program aplikasi

komputer (TIK-05).

3

Outline Materi

• Notasi Aritmatika– Infix– Prefix– Postfix/Suffix

• Algoritma– Infix– Prefix– Postfix/Suffix

• Konversi Notasi• Evaluasi Notasi

4

Tiga Notasi aritmatika :1. Infix =kedua operand berada di antara operatornya, contoh :

A x B + C

(A + B) x C – D

2. Prefix=operator berada di depan kedua operandnya, contoh :

x A B C

x A B C D

3. Postfix/Suffix=operator berada di belakang kedua operandnya, contoh :

A B x C +

AB + C x D

Notasi Aritmatika

5

• Algoritma Evaluasi :

1. Scan dari kiri ke kanan sampai ketemu dg kurung tutup yg paling awal.

2. Scan kembali dari posisi tadi ke kiri sampai ketemu dg kurung buka yg pertama ditemukan.

3. Lakukan operasi yg berada dalam tanda kurung.

4. Ganti ekspresi di dalam kurung tersebut dg hasil operasi.

5. Ulangi langkah 1 sampai selesai

• Kekurangan :

Lama dan tidak effisien

INFIX

6

• Algoritma Evaluasi1. Scan dari kanan ke kiri sampai ketemu dg operator.2. Ambil 2 operand yg berada langsung di sebelah kanan operator

tersebut.3. Ganti ekspresi dg hasil operasi.4. Scan lagi hasil operasi tadi ke kiri.

• Algoritma Evaluasi dg STACK1. Scan PREFIX dari kanan ke kiri.2. Bila ketemu operand, PUSH(operand).3. Bila ketemu operator, POP dua kali yaitu POP(X), POP(Y).4. PUSH( X operator Y ).5. Ulangi 2 s.d. 4 hingga seluruh simbol PREFIX terbaca

• Keuntungannya dibandingkan dg INFIX :– Tidak perlu memakai tanda kurung utk menyatakan prioritas

pengerjaan.– Lebih cepat dan efisien, krn tidak perlu selalu scan dari depan (paling

kiri).

PREFIX

7

• Algoritma Evaluasi

1. Scan dari kiri ke kanan sampai ketemu dengan operator.

2. Ambil 2 operand yang berada langsung di sebelah kiri operator tersebut.

3. Ganti ekspresi dengan hasil operasi.

4. Scan lagi hasil operasi tadi ke kanan.• Algoritma Evaluasi dg STACK

1. Scan SUFFIX dari kiri ke kanan.

2. Bila ketemu operand, PUSH(operand).

3. Bila ketemu operator, POP dua kali yaitu POP(X), POP(Y).

4. PUSH( Y operator X ).

5. Ulangi 2 s.d. 4 hingga seluruh simbol SUFFIX terbaca• Keuntungannya dibandingkan dg INFIX : sama dg keuntungan PREFIX.

POSTFIX (SUFFIX)

8

Skema Evaluasi Infix

Notasi INFIX

Notasi SUFFIX

Hasil Evaluasi

Konversi (INFIX ke SUFFIX)

Evaluasi (SUFFIX)

Skema Evaluasi INFIX

9

KONVERSI dari INFIX

Konversi Notasi Secara Manual

Infix Prefix Postfix

A x B + C [ x A B ] + C`

+ [ x A B ] C

+ x A B C

[ A B x ] + C

[ A B x ] C +

A B x C +

( A x B ) x C – D [ + A B ] x C – D

[ x[+ A B ] C ] – D

–[ x[+ A B ] C ] D

– x + A B C D

[ A B + ] x C – D

[[ A B + ] C x ] – D

[[[ A B + ] C x ] D ] –

A B + C x D –

10

Konversi menggunakan STACK• Algoritma :

1. CREATE STACK2. Kosongkan POSTFIX3. Tambahkansimbol ‘)’ ke ujung INFIX4. PUSH( ‘(‘ )5. Selama (Not EMPTY STACK ) {

Baca Simbol dari INFIXSeleksi ( Simbol )

Operand : Tambahkan Simbol ke ujung POSTFIXOperator : Selama ( PRCD( STACK[TOP], Simbol) )

POP( X )Tambahkan X ke ujung POSTFIX Akhir Selama PUSH ( Simbol )

‘(‘ : PUSH( Simbol )‘)‘ : Selama (STACK[TOP] != ‘(‘ )

POP( X )Tambahkan X ke ujung POSTFIX Akhir Selama POP ( X ) // Buang Simbol ‘(‘

Akhir SeleksiAkhir Selama

6. Selesai

11

Selesai