STACK Sistem penyimpanan data dengan mekanisme Last In First Out( LIFO). Stack merupakan tipe data digunakan dalam berbagai adalah: Algoritma konversi algoritma evaluasi postfix kemudian.
abstrak yang banyak algoritma, diantaranya infix ke postfix dan yang akan dipelajari
Bentuk Umum Stack:
PUSH
POP E D C B A
E merupakan piringan yang terkahir masuk dan akan menjadi piringan yang pertama keluar.
1
STACK TUJUAN UMUM Memahami STACK dan representasinya TUJUAN KHUSUS z Operasi dalam Stack z Implementasi stack dengan linked list z Aplikasi Stack z Konfersi Infix ke Postfix z Algoritma Evaluasi Postfix 2
Operasi dalam stack z
Create() Menciptakan stack baru dalam keandaan kosong
z
Push(e) Memasukkan data baru dari variabel ke dalam stack
z
Pop(e) Mengambil data dari stack untuk disimpan di variabel e.
z
Empty( ) Memeriksa apakah Stack dalam keadaan kosong
z
Full( ) Memeriksa apakah stack dalam keadaan penuh.
z
Clear( ) Menghapus semua data yang ada dalam stack.
3
Implementasi Stack dengan Array #define pj_max 7 typedef int elemen type; elemen_type Stack[pj_max}; int TOP; void create( ) { TOP=0; } int full( ) {if (TOP==pj_max) return 1;else return 0; } int empty( ) { if (TOP == 0) return 1;else return 0; } void push(elemen_type e) { if (!full){TOP++;stack[TOP]=e;}; } void pop(elemen_type e) { if (!empty){*e=stack[TOP];TOP- -;}; } void clear( ) { TOP=0; }
4
Proses Push(35); 6
6
6
5
5
5
4
4
TOP
TOP
4
35
3
90
3
90
70
2
70
2
70
30
1
30
1
30
3
90
2 1
0
0
Sebelum Push
TOP
0
TOP ++
Stack([TOP] = e
Proses Pop(*e); 6
6
6
5
5
5
TOP
TOP
4
35
90
3
90
3
90
2
70
2
70
2
70
1
30
1
30
1
30
4
35
3
0
0
Sebelum Pop
*e=Stack[TOP]
4
TOP
0
TOP --
Implementasi Stack dengan Linked List Operasi Push() menggunakan Insert Depan Operasi Pop() menggunakan Delete dibagian Head Pointer Head berfungsi sebagai TOP
5
Dibandingkan dengan implementasi dengan array, maka implementasi stack dengna linked list memepunyai: Keuntungan: 1. Kapasitas stack hanya dibatasi oleh kapasitas memori komputer 2. Penggunaan memori tergantung dari banyaknya data. Kerugian Operasi clear memerlukan lebih banyak langkah. z
Latihan: 1. Untuk urutan operasi: a. create(); b. push(23); c. push(21); d. push(45); e. pop(e);cout « e; f. pop(e);cout « e; g. push(18); h. pop(e);cout « e; I. pop(e);cout « e; Tulis output yang dicetak. 2.
Tiga bilangan bulat hendak dimasukkan ke suatu STACK dengan urutan: 1, 2, 3. Bila operasi Push dan Pop dapat dilakukan secara berselingan, maka akan didapat output dengan kombinasi yang berbeda, contoh:
6
z
z
Push(1), Pop(x), Push(2), Pop(x), Push(3), Pop(x). akan menghasilkan urutan 1, 2, 3 Push(1), Push(2), Pop(x), Push(3), Pop(x), Pop(x). akan menghasilkan urutan 2, 3, 1
Tuliskan operasi Push dan Pop sedemikain sehingga didapat output dengan urutan: z z z z z z
1,2,3 1,3,2 2,1,3 2,3,1 3,1,2 3,2,1
7
Aplikasi dalam Stack Evaluasi Infix Notasi Infix Adalah suatu penulisan ekspresi aritmatik, sebagai contoh: 12 + 5 x 10. Evaluasi infix adalah mendapatkan nilai dari ekspresi tersebut, hasil evaluasi (perhitungan) dari contoh ekspresi di atas adalah 62. Membuat algoritma untuk evaluasi dari ekspresi Infix sangat sulit karena adanya presedence, yaitu operator mana yang harus didahulukan evaluasinya. Urutan yang telah dipelajari sejak bangku sekolah dasar adalah: pangkat, kali, bagi, tambah dan kurang. Belum lagi adanya tanda kurung yang dapat merubah precedencedan mempersulit algoritma. Algoritma wavaluasi Infix dapat dengan mudah dibuat bila notasi infix diubah terlebih dahulu ke notasi lain yaitu Prefix dan Postfix. Notasi Infix: Notasi Prefix: Notasi Posfix:
A+B +AB AB+
AxB+C +xABC ABxC+ 8
Konversi Infix ke Postfix
z
Dilakukan secara manual
INFIX
PREFIX
POSFIX
AxB+C
[x A B] + C
[A B x ] + C
+ [x A B] C
[A B x ] C +
+xABC
ABxC+
[+ A B] x C - D
[A B +] x C – D
[x [+ A B] C] - D
[[A B +] C x] – D
- [x [+ A B] C] D
[[A B +] C x] D –
-x+ABCD
AB+CxD-
(A + B) x C - D
Apabila ekspresi sudah berada dalam notasi Posfix, maka membuat algoritma Evaluasi Postfix akan menjadi sangat mudah, yaitu dengan mengunakan stack.
Algoritma Evaluasi Posfix(Suffix) 1. 2. 3.
4. 5. 6.
Scan sting Postfix dari kiri ke kanan Bila ketemu operand, Push(operand) Bila ketemu operator, Pop dua kali yaitu Pop(X) dan Pop(Y) Z= Y operator X Push (Z) Ulangi langkah 2 s/d 5 hingga seluruh simpbol di dalam stirng terbaca. 9
z
Contoh:
Notasi Infix: 5 x 12 – 8 Notasi Postfix : 5 12 x 8 – Ada 5 simbio yang harus dibaca. SIMBOL
Isi Stack
5
5
12
5
x
5
Keterangan Push(5)
12
Push(12) Pop(A);A=12 Pop(b);B=5
60 8
60
-
60
Push(BxA) 8
Push(8) Pop(A);A=8 Pop(B);B=60
52
Push(B-A) Selesai, hasil evaluasi: 52
Contoh:
Notasi Infix: (13 + 7) x 3 + 11 Notasi Postfix : 13 7 + 3 x 11 + Ada 7 simbio yang harus dibaca.
10
SIMBOL
Isi Stack
13
13
7
13
+
13
Ketrangan Push(13)
7
Push(7) Pop(A);A=7 Pop(B);B=13
20 3
20
x
20
Push(B + A) 3
Push(3) Pop(A);A=3 Pop(B);B=20
60 11
60
+
Push(B x A) 11
Push(11) Pop(A);A=11 Pop(B);B=60
71
Push(B + A) Selesai, Hasil evaluasi = 71
Latihan 1. Lakukan konversi secara manual dari notasi Infix dibawah ini ke notasi Prefix dan Postfix a. A + B x C + D / E b. A x (B + (C – D)) x (E – F) + T c. (D + B – 4 x A x C) / (2 x A) 2.
Evaluasi Ekspresi postfix dari soal no. 1a dan 1b di atas dengan, menggunakan algoritma Evaluasi Postfix. a. A = 13, B = 9, C = 3, D = 48 dan E = 8 b. A = 7, B = 34, C =73, D = 59, E= 16, F = 5, dan T = 28 11
Aplikasi Stack Notasi INFIX Konfersi Infix ke postfix POSFIX Evaluasi Postfix HASIL POSFIX
Evaluasi Posfix telah menggunakan algoritma Postfix, sedangkan Konversi Infix ke Postfix masih menggunakan cara manual. Supaya seluruh proses dapat dikerjakan oleh komputer maka perlu dibuat algoritma Konversi Infix ke Postfix Algoritma Komversi Infix ke Posfix 1. 2. 3. 4.
Create Stack Kosongkan string Posfix Tambahkan simbo ’(‘ ke ujung string Infix Push(‘(‘)
12
5. While(Not Empty Stack) { Baca simbol dari string Infix Switch (simbol) { case operand : Tambahkan simbol ke ujung string postfix case operator : While (prcd(stack[TOP], simbol) == true { Pop(X) Tambahkan X ke ujung string Postfix } Push(simbol) case ‘(‘ : Push(simbol) case ‘)’ : while (stack[TOP] != ‘(‘) { Pop(X) Tambahkan X ke ujung string Posfix } Pop(x) } } 6. Selesai
13
Algoritma konversi nfix ke Postfix hanya dapat dijalankan dengan bantuan daftar precedence
OPERATOR
NILAI
Prcd(‘^’,’x’)
True
Prcd(‘x’,’+’)
True
Prcd(‘x’,’x’)
True
Prcd(‘+’,’+’)
True
Prcd(‘+’,’-’)
True
Prcd(‘-’,’-’)
True
Prcd(‘x’,’^’)
False
Prcd(‘+’,’x’)
False
Prcd(‘-’,’+’)
False
Prcd(‘-’,’x’)
False
Dst
Bila operator tidak terdefinisi, maka nilainya False, Contoh: Prcd(‘(‘,’+’) = False
14
Contoh: String Infix: 6 + 2 x 2 + 72 / 8 ) SIMBOL
Isi Stack
String POSTFIX
6
(
+
(
+
6
2
(
+
62
x
(
+
x
62
2
(
+
x
622
+
(
+
622x
(
+
622x+
72
(
+
6 2 2 x + 72
/
(
+
/
6 2 2 x + 72
8
(
+
/
6 2 2 x + 72 8
)
(
+
6 2 2 x + 72 8 /
(
+
6 2 2 x + 72 8 /
(
Ket
6 Prcd(‘( ‘,’+’)=F
Prcd(‘+‘,’x’)=F
Prcd(‘x‘,’+’)=T
Prcd(‘+‘,’/’)=F
6 2 2 x + 72 8 / + 6 2 2 x + 72 8 / +
POP(X)
Selesai
15
Kemudian hasil konversi dievaluasi dengan menggunakan algoritma Evaluasi Postfix. Notasi Postfix: 6 2 2 x 72 8 / + + SIMBOL
Isi Stack
6
6
2
6
2
2
6
2
x
6
2
Ketrangan Push(6) Push(2)
2
Push(2) Pop(A);A=2
6
Pop(B);B=2
6
4
72
6
4
72
8
6
4
72
/
6
4
72
6
4
6
4
6
4
+
6 6 +
6
Push(B x A) Push(72) 8
Push(8) Pop(A);A=8 Pop(B);B=72
9
Push(B / A) Pop(A);A=9 Pop(B);B=4
13
Push(B + A) Pop(A);A=13 Pop(B);B=6
19
Push(B + A) Selesai, Hasil evaluasi:19
16
Dengan adanya algoritma konfersi Infix ke Postfix, maka Algoritma Evaluasi Infix sudah lengkap, yaitu terdiri dari: z z
Algoritma konfersi Infix ke Postfix Algoritma Evaluasi Postfix
Sehingga dapat dibuat program komputer dimana string Infix diketik papan tombol, ditayangkan layar monitor, tekan enter, dan pada baris berikutnya dicetak hasil. 6 + 2 x 2 + 72 / 8 19
Latihan: 1.
Dengan algoritma Konversi Infix ke Postfix, lakukan konversi notasi Infix di bawah ini ke notasi Postfix, kemudian evaluasi hasil konversi dengan algoritma Ealuasi Postfix. 12 x (8 +(16-4)) x (23 – 18) + 48
17
