3/5/2024
Auli Damayanti, [Link]., [Link]
Secara sederhana diartikan dengan :
sebagai tumpukan dari benda
sekumpulan data yang seolah-olah
diletakkan di atas data yang lain
koleksi dari objek-objek homogen
1
3/5/2024
S TACK = TUMPUKAN
Stack disebut juga tumpukan dimana data
hanya dapat dimasukkan dan diambil dari satu
sisi
Suatu susunan koleksi data dimana data dapat
ditambahkan dan dihapus selalu dilakukan pada
bagian akhir data, yang disebut dengan top of
stack
Stack bersifat LIFO (Last In First Out)
“Benda yang terakhir masuk ke dalam stack
akan menjadi yang pertama keluar dari stack
4 I LUSTRASI S TACK
Terdapat dua buah kotak yang ditumpuk, kotak
yang satu akan ditumpuk diatas kotak yang
lainnya. Jika kemudian stack 2 kotak tadi,
ditambah kotak ketiga, keempat, kelima, dan
seterusnya, maka akan diperoleh sebuah stack
kotak yang terdiri dari N kotak.
Compo Compo
VCD Compo
VCD VCD
TV TV TV TV
2
3/5/2024
I LUSTRASI S TACK -
5
C ONT.
Push : digunakan untuk menambah
item pada stack pada
tumpukan paling atas
Pop : digunakan untuk mengambil
item pada stack pada 4 1
tumpukan paling atas O
I
U
N
Clear : digunakan untuk T 3 2
mengosongkan stack
IsEmpty : fungsi yang digunakan untuk 2 3
mengecek apakah stack
sudah kosong
1 4
IsFull : fungsi yang digunakan untuk
mengecek apakah stack
sudah penuh
3
3/5/2024
A LGORITMA P USH AND P OP
S TACK WITH A RRAY OF
S TRUCT
Definisikan Stack dengan menggunakan suatu
struct
Definisikan konstanta MAX_STACK untuk
menyimpan maksimum isi stack
Elemen struct Stack adalah array data dan top
untuk menadakan posisi data teratas
Buatlah variabel tumpuk sebagai implementasi
dari struct Stack
Deklarasikan operasi-operasi/function di atas
dan buat implemetasinya
4
3/5/2024
P ROGRAM S TACK
Contoh deklarasi MAX_STACK
#define MAX_STACK 10
Contoh deklarasi STACK dengan struct dan
array data
typedef struct STACK{
int top;
int data[10];
};
Deklarasi/buat variabel dari struct
STACK tumpuk;
P ROGRAM S TACK (2)
Inisialisasi Stack
Pada mulanya isi top dengan -1, karena
array dalam bahasa C dimulai dari 0, yang
berarti bahwa data stack adalah KOSONG!
Top adalah suatu variabel penanda dalam
Stack yang menunjukkan elemen teratas
data Stack sekarang. Top Of Stack akan
selalu bergerak hingga mencapai MAX of
STACK yang menyebabkan stack PENUH!
5
3/5/2024
P ROGRAM S TACK (2)
Ilustrasi Stack pada saat inisialisasi!
P ROGRAM S TACK (3)
Fungsi IsFull
Untuk memeriksa apakah stack sudah
penuh?
Dengan cara memeriksa top of stack, jika
sudah sama dengan MAX_STACK-1 maka
full, jika belum (masih lebih kecil dari
MAX_STACK-1) maka belum full
6
3/5/2024
P ROGRAM S TACK (4)
Ilustrasi Stack pada kondisi Full
P ROGRAM S TACK (5)
Fungsi IsEmpty
Untuk memeriksa apakah data Stack masih
kosong?
Dengan cara memeriksa top of stack, jika masih -
1 maka berarti data Stack masih kosong!
7
3/5/2024
P ROGRAM S TACK (6)
Fungsi Push
Untuk memasukkan elemen ke data Stack.
Data yang diinputkan selalu menjadi elemen
teratas Stack (yang ditunjuk oleh ToS)
Jika data belum penuh,
Tambah satu (increment) nilai top of stack lebih
dahulu setiap kali ada penambahan ke dalam
array data Stack.
Isikan data baru ke stack berdasarkan indeks top
of stack yang telah di-increment sebelumnya.
Jika tidak, outputkan “Penuh”
P ROGRAM S TACK (7)
8
3/5/2024
P ROGRAM S TACK (8)
Fungsi Pop
Untuk mengambil data Stack yang terletak
paling atas (data yang ditunjuk oleh TOS).
Tampilkan terlebih dahulu nilai elemen
teratas stack dengan mengakses indeksnya
sesuai dengan top of stacknya, baru
dilakukan di-decrement nilai top of
stacknya sehingga jumlah elemen stack
berkurang.
P ROGRAM S TACK (9)
9
3/5/2024
P ROGRAM S TACK (10)
Fungsi Print
Untuk menampilkan semua
elemen-elemen data Stack
Dengan cara me-loop semua nilai
array secara terbalik, karena kita
harus mengakses dari indeks array
tertinggi terlebih dahulu baru ke
indeks yang lebih kecil!
P ROGRAM S TACK (11)
10
3/5/2024
F UNGSI P EEK
Digunakan untuk melihat top of stack
#include <stdio.h>
#include <conio.h>
#include <string.h>
#define MAX_STACK 10
typedef struct STACK { int top;
char data[10][10];
};
STACK tumpuk;
void inisialisasi()
{ [Link] = -1;} P ROGRAM LENGKAP STACK
int IsFull()
{ if([Link] == MAX_STACK-1) return 1; else return 0;}
int IsEmpty()
{ if([Link] == -1) return 1;
else return 0;}
void Push(char d[10])
{ [Link]++;
strcpy([Link][[Link]],d); }
void Pop()
{ cout<<"Data yang terambil=“<<endl<<[Link][[Link]]);
[Link]--; }
void Clear()
{ [Link]=-1; }
void TampilStack()
{ for(int i=[Link];i>=0;i--)
{ printf("Data : %s\n",[Link][i]); }
}
11
3/5/2024
int main()
{ int pil;
inisialisasi();
char dt[10];
do{ printf("1. push\n");
printf("2. pop\n");
printf("3. print\n");
printf("4. clear\n");
printf("5. exit\n");
printf("Pilihan : ");
scanf("%d",&pil);
switch(pil)
P ROGRAM LENGKAP STACK
{
case 1: if(IsFull() != 1)
{ printf("Data = ");scanf("%s",dt);
Push(dt); }
else printf("\nSudah penuh!\n");
break;
case 2: if(IsEmpty() != 1)
Pop();
else printf("\nMasih kosong!\n");
break;
case 3: if(IsEmpty() != 1)
TampilStack();
else printf("\nMasih kosong!\n");
break;
case 4: Clear();
printf("\nSudah kosong!\n");
break;
}
getch();
} while(pil != 5);
getch();
}
Prefix, infix, dan postfix adalah suatu cara penulisan ungkapan-
ungkapan yang rumit, misalnya pemakaian tanda kurung dalam operasi
matematika.
Prefix adalah metode penulisan dengan meletakkan operator di
depan operand dan tanpa menuliskan tanda kurung.
Contoh pemakaian prefix adalah +AB, – +ABC, * + AB – CD.
Infix adalah cara penulisan ungkapan dengan meletakkan operator di
antara dua operand dalam hal ini pemakaian tanda kurung
sangat menentukan hasil operasi.
Contoh pemakaian infix adalah A+B, A+B-C, (A+B)*(C-D).
Postfix adalah metode penulisan dengan menuliskan operator setelah
operand dan tanpa menuliskan tanda kurung.
Contoh penulisan sufix adalah AB + , AB + C – , AB + CD -*.
12
3/5/2024
Mengapa sih mesti ada notasi Prefix atau Postfix?
Kenapa nggak gunakan infix aja, seperti yang sudah kita
pelajari sejak zaman TK ??
Karena infix memiliki beberapa kekurangan, yaitu :
Urutan pengerjaan tidak berdasarkan letak kiri atau kananya,
tetapi berdasarkan precedence-nya
Contoh : 3 + 4 x 2
3 + 4 x 2, maka urutan pengerjaan adalah 4 x 2 dahulu.
3+8 , baru hasilnya ditambah 3
11
1. Urutan precedence (dari prioritas tertinggi) adalah sbb :
Pemangkatan
Perkalian dan Pembagian
Penjumlahan dan Pengurangan.
Kecuali kalau ada tanda kurung.
2. Menggunakan tanda kurung. Betul, infix bisa menggunakan tanda
kurung. Repotnya, si tanda kurung ini bisa ngacak-ngacak urutan
precedence.
Contoh : Tanpa penggunaan tanda kurung :
9–5–3
9 – 5 – 3, maka urutan pengerjaan adalah 9 - 5 dahulu.
4–3
1
Bandingkan dengan penggunaan tanda kurung berikut :
9–(5–3)
9 – ( 5 – 3 ) , maka urutan pengerjaan adalah 5 – 3 dahulu.
9–2
7
13
3/5/2024
3. Jika suatu program akan mengevaluasi (mencari hasil) suatu infix,
maka komputer perlu men-scan berulang-ulang mencari urutan
pengerjaannya dahulu.
Contoh : 7 + 4 x 2 – 6 / 3
Jika kita diminta untuk menghitung soal seperti itu, maka kita tahu
bahwa yang pertama kali harus kita kerjakan adalah 4 x 2.
Lalu 6 / 3 dsb, seperti langkah-langkah berikut :
7+4x2–6/3
7+8–6/3
7+8–2
15 – 2
13 (Bingung pada tahapan ini? Tanyakan segera ke teman anda)
Pembuatan Kalkulator SCIENTIFIC
Misalkan operasi: 3 + 2 * 5
Operasi di atas disebut notasi infiks, notasi infiks
tersebut harus diubah lebih dahulu menjadi notas
postfix
3 + 2 * 5 notasi postfiksnya adalah 3 2 5 * +
14
3/5/2024
Infix to Postfix
Baca soal dari depan ke belakang
Jika berupa operand, maka masukkan ke posftix
Jika berupa operator, maka:
Jika stack masih kosong, push ke stack
Jika derajat operator soal > derajat operator top of stack
Push operator soal ke stack
Selama derajat operator soal <= derajat operator top of stack
Pop top of stack dan masukkan ke dalam posfix
Setelah semua dilakukan, push operator soal ke stack
Jika sudah semua soal dibaca, pop semua isi stack dan push
ke postfix sesuai dengan urutannya
3+2*5
stack
posftix
S TUDI K ASUS S TACK (3)
15
3/5/2024
KONVERSI I NFIX P OSTFIX
Langkah-langkah pengerjaan :
1. Scan Infix dari kiri ke kanan.
2. Jika berupa operand, maka tulis di Postfix.
3. Jika berupa operator, maka bandingkan operator NEW tsb dgn TOP
pada Stack :
a) WHILE precedence TOP >= NEW, maka POP Stack pindahkan ke
Postfix.
b) Lalu Push NEW ke dalam Stack.
4. Jika berupa “(“, maka Push “(“ ke Stack.
5. Jika berupa “)”, maka Pop Stack pindahkan ke Postfix sampai ketemu
“(“.
6. Ulangi terus dari langkah 1 sampai seluruh Infix sudah di-scan.
7. POP semua isi Stack, pindahkan ke Postfix.
Perlu diingat!! tanda kurung “(“ ataupun “)” tidak dimasukkan ke Postfix.
Contoh : A ^ B / ( C – D )
Infix Postfix Stack
1. A^B/(C–D) A
2. A^B/(C–D) A ^
3. A^B/(C–D) AB ^
4. A^B/(C–D) AB^ /
5. A^B/(C–D) AB^ /(
6. A^B/(C–D) AB^C /(
7. A^B/(C–D) AB^C /(–
8. A^B/(C–D) AB^CD /(–
9. A^B/(C–D) AB^CD– /
10. A^B/(C–D) AB^CD–/
Keterangan :
Tanda kurung “(“ dan “)”, dapat dianggap tidak memiliki
precedence, sehingga pada langkah ke-7, operator “–“ tidak perlu
dibandingkan lagi dengan “(“ dan langsung di Push ke Stack.
Pada langkah ke-8, tanda “)” dibaca dari Infix, maka Stack di Pop
terus sampai ketemu tanda “(“. Sehingga pada contoh di atas
operator “–“ di Pop dan dipindahkan ke Postfix.
16
3/5/2024
a+b*c-d
Stack (kosong) dan Postfik (kosong)
Scan a
• Postfik: a
Scan +
• Stack: +
Scan b
• Postfik: ab
Scan *, karena ToS (+) < *, maka add ke Stack
• Stack: +*
• Scan c
– Postfik: abc
• Scan –, karena * > -, maka pop Stack, dan add ke Postfik
– Stack: +
– Postfik: abc*
– Karena + >= -, maka pop Stack, dan add ke Postfik,
karena Stack kosong, maka push – ke stack
– Stack: -
– Postfik: abc*+
• Scan d
– Postfik: abc*+d
• Karena sudah habis, push ToS stack ke Posfix
– Postfix: abc*+d-
17
3/5/2024
Scan Postfix string dari kiri kekanan.
Siapkan sebuah stack kosong.
Jika soal adalah operand, tambahkan ke stack. Jika
operator, maka pasti akan ada minimal 2 operand
pada stack
Pop dua kali stack, pop pertama disimpan dalam y, dan
pop kedua ke dalam x. Lalu evaluasi x <operator> y.
Simpan hasilnya dan push ke dalam stack lagi.
Ulangi hingga seluruh soal discan.
Jika sudah semua, elemen terakhir pada stack
adalah hasilnya.
Jika lebih dari satu elemen, berarti error!
18
3/5/2024
KONVERSIKAN DARI INFIX MENJADI POSTFIX
1. A + B – C * D 9. A + B * ( C – D ^ E / F ) / H
2. A * B ^ C – D 10. ( A ^ B – C / F ) + G ^ H * I
3. A + ( B – C ) * D
4. A + (B – C * D) ^ E / F
5. A * ( B + C ) / D ^ E – F
6. ( A + B ) – ( C * D )
7. A * ( B + C ) / ( D – E )
8. ( ( ( S + T ) * U ) – V ) / W
Kali ini kita menggunakan 2 Stack, yang satu untuk menampung operand
(saya sebut aja namanya Stack “Pre”) dan yang satunya lagi untuk
menampung operator (yang ini saya sebut Stack “Opr” deh).
Langkah – langkah :
1. Scan Infix dari kanan ke kiri.
2. Jika berupa operand, maka Push ke Stack “Pre”.
3. Jika berupa operator, maka bandingkan operator NEW tersebut
dengan TOP pada Stack “Opr”:
a) WHILE precedence TOP > NEW, maka POP Stack “Opr”
pindahkan ke Stack “Pre”.
b) Lalu Push NEW ke dalam Stack “Opr”.
4. Jika berupa “)“, maka Push “)“ ke Stack “Opr”.
5. Jika berupa “(”, maka Pop Stack “Opr” pindahkan ke stack “Pre”
sampai ketemu “)“.
6. Ulangi terus dari langkah 1 sampai seluruh Infix sudah di-scan.
7. POP semua isi Stack “Opr”, pindahkan ke Stack “Pre”.
8. POP semua isi Stack “Pre”, pindahkan ke Prefix.
19
3/5/2024
1.A + B * C (Baca dari kanan ke kiri => tulis
dari kanan ke kiri)
C
BC
+ BC
* *BC
+A* B C
2. A ^ B / ( C – D )
Infix Stack “Pre” Stack “Opr”
1. A^B/(C–D) )
2. A^B/(C–D) D )
3. A^B/(C–D) D )–
4. A^B/(C–D) DC )–
5. A^B/(C–D) DC–
6. A^B/(C–D) DC– /
7. A^B/(C–D) DC–B /
8. A^B/(C–D) DC–B /^
9. A^B/(C–D) DC–BA /^
10. A^B/(C–D) DC–BA^ /
11. A^B/(C–D) DC–BA^/
12. Prefix-nya menjadi / ^ A B – C D
Keterangan :
Setelah Stack “Opr” dikosongkan. Jangan lupa untuk memindahkan
isi Stack “Pre” ke Prefix. Sehingga urutan peletakkan operand pada
hasil akhirnya tetap sama
20
3/5/2024
KONVERSIKAN DARI INFIX MENJADI PREFIX
1. A + B – C * D 9. A + B * ( C – D ^ E / F ) / H
2. A * B ^ C – D 10. ( A ^ B – C / F ) + G ^ H * I
3. A + ( B – C ) * D
4. A + (B – C * D) ^ E / F
5. A *( B+C )/ D^ E– F
6. (A+B)–(C*D)
7. A *( B+C )/ (D – E)
8. ( ( ( S + T ) * U ) – V ) / W
INFIX to PREFIX : (A+B) – (C*D)
Do the first brace: (A+B), the PREFIX is +AB
Do the second brace: (C*D), the PREFIX is *CD
The end is operator -: +AB - *CD,
the PREFIX is - + A B * C D
INFIX to POSTFIX : (A+B) – (C*D)
Do the first brace: (A+B), the POSTFIX is AB+
Do the second brace: (C*D), the POSTFIX is CD*
The end is operator -: AB+ - CD*,
the POSTFIX is A B + C D * -
21
3/5/2024
PREFIX to INFIX : +/*A B C D
1. Find the first operator : * ,
take 2 operands before the operator (A and B),
the INFIX is (A*B)
2. Find the second operator : /,
take 2 operands before the operator (A*B and C),
the INFIX is ((A*B)/C)
3. Find the third operator: +,
take 2 operands before the operator (((A*B)/C) and D),
the INFIX is ((A*B)/C)+D
PREFIX to POSTFIX : +/*A B C D
1. Find the first operator: *, take 2 operands before
the operator (A and B),
the POSTFIX is AB*
2. Find the second operator: /, take 2 operands before
the operator (AB* and C),
the POSTFIX is AB*C/
3. Find the third operator: +, take 2 operands before
the operator (AB*C/ and D), the POSTFIX is
AB*C/D+
22
3/5/2024
POSTFIX to INFIX : ABCD*/-
1. Find the first operator: *, take 2 operands before
the operator (C and D),
the INFIX is (C*D)
2. Find the second operator: /, take 2 operands
before the operator ((C*D) and B),
the INFIX is (B/(C*D)
3. Find the third operator: -, take 2 operands before
the operator ((B/(C*D) and A),
the INFIX is A – (B/(C*D)
POSTFIX to PREFIX : ABCD*/-
1. Find the first operator: *, take 2 operands before
the operator (C and D),
the PREFIX is * C D
2. Find the second operator: /, take 2 operands before
the operator (*CD and B),
the PREFIX is / B * C D
3. Find the third operator: -, take 2 operands before
the operator (/B*CD and A),
the PREFIX is – A / B * C D
23
3/5/2024
1. Convert these INFIX to PREFIX and POSTFIX :
a) A / B – C / D
b) (A + B) ^ 3 – C * D
c) A ^ (B + C)
2. Convert these PREFIX to INFIX and POSTFIX :
a) + – / A B C ^ D E
b) – + D E / X Y
c) ^ + 2 3 – C D
d ) * + A-B C / - D E + - F G H
3. Convert these POSTFIX to INFIX and PREFIX :
a) A B C + –
b) G H + I J / *
c) A B ^ C D + –
d) X Y ^ 5 Z * / 10 +
24