Studi Kasus Stack
Nama: Hadryan Rizky Dimas Saputra
NRP: 5025251027
Kelas: Struktur Data (D) 2026
Pertemuan: 6
1. System Call Stack: Fungsi Rekursif Faktorial
Deskripsi (Fungsi) Program:
Program ini berfungsi untuk meminta pengguna memasukkan sebuah angka, lalu menghitung nilai faktorial dari angka tersebut, dan menampilkan hasilnya ke layar.
Code:
Hasil/Output Program:
Penjelasan Program:
Baris Kode | Penjelasan |
#include <bits/stdc++.h> | Memasukkan semua perlengkapan (pustaka) standar C++ agar kode bisa berjalan. |
using namespace std; | Agar kita tidak perlu menulis awalan std:: berulang kali setiap memanggil perintah standar. |
int faktorial(int n) { | Membuat sebuah fungsi bernama faktorial yang menerima sebuah angka (n). |
if(n == 1) { | Mengecek apakah angka n adalah 1. Ini adalah batasan agar program tidak berhitung selamanya. |
return 1; | Jika n adalah 1, maka langsung berikan nilai 1 (karena faktorial 1 adalah 1). |
} else { | Jika angka n bukan 1, maka lakukan perintah di bawah ini. |
return n * faktorial(n - 1); | Kalikan nilai n dengan hasil fungsi faktorial dari angka tepat di bawahnya (n - 1). |
} | Menutup blok perintah else. |
} | Menutup blok fungsi faktorial. |
int main(void) { | Ini adalah fungsi utama. Semua program C++ mulai berjalan dari sini. |
int a; | Membuat "wadah" bernama a untuk menyimpan angka yang akan dimasukkan pengguna. |
cout << "Masukkan Bilangan: "; | Menampilkan teks "Masukkan Bilangan: " ke layar komputer. |
cin >> a; | Membaca ketikan angka dari pengguna, lalu menyimpannya ke dalam wadah a. |
cout << '\n' << faktorial(a); | Membuat baris baru/enter (\n), lalu menghitung nilai faktorial dari a dan menampilkannya. |
return 0; | Menandakan bahwa program utama telah selesai berjalan dengan sukses tanpa error. |
} | Menutup blok fungsi utama main. |
Visualisasi:
Langkah | Aksi / Pemanggilan | Kondisi Call Stack (Dari Atas ke Bawah) | Keterangan (Remarks) |
1 | faktorial(5) | f(5) | n=5 (bukan 1). Fungsi ditunda, masuk Stack. Panggil f(4). |
2 | faktorial(4) | f(4)
f(5) | n=4 (bukan 1). Fungsi ditunda, masuk Stack. Panggil f(3). |
3 | faktorial(3) | f(3)
f(4)
f(5) | n=3 (bukan 1). Fungsi ditunda, masuk Stack. Panggil f(2). |
4 | faktorial(2) | f(2)
f(3)
f(4)
f(5) | n=2 (bukan 1). Fungsi ditunda, masuk Stack. Panggil f(1). |
5 | faktorial(1) | f(1)
f(2)
f(3)
f(4)
f(5) | Base Case tercapai! n=1. Langsung mengembalikan (return) nilai 1 ke fungsi yang memanggilnya. |
6 | Kembali ke faktorial(2) | f(2)
f(3)
f(4)
f(5) | f(1) dihapus (Pop) dari Stack. f(2) menghitung: 2 * 1 = 2. Mengembalikan nilai 2. |
7 | Kembali ke faktorial(3) | f(3)
f(4)
f(5) | f(2) dihapus (Pop) dari Stack. f(3) menghitung: 3 * 2 = 6. Mengembalikan nilai 6. |
8 | Kembali ke faktorial(4) | f(4)
f(5) | f(3) dihapus (Pop) dari Stack. f(4) menghitung: 4 * 6 = 24. Mengembalikan nilai 24. |
9 | Kembali ke faktorial(5) | f(5) | f(4) dihapus (Pop) dari Stack. f(5) menghitung: 5 * 24 = 120. Mengembalikan nilai 120. |
10 | Selesai (End) | (Stack Kosong) | f(5) dihapus dari Stack. Program utama (main) menerima hasil akhir 120 dan mencetaknya ke layar. |
2. Reverse String
Deskripsi (Fungsi) Program:
Jika program ini dijalankan, ia akan mengubah kata "HELLO" menjadi "OLLEH". Sifat dasar dari Stack adalah LIFO (Last-In, First-Out) atau "Yang Terakhir Masuk, Yang Pertama Keluar". Karena huruf 'O' dimasukkan paling akhir, ia akan menjadi huruf pertama yang dikeluarkan dan dicetak ke layar.
Code:
Hasil/Output Program:
Penjelasan Program:
Baris Kode | Penjelasan |
string str = "HELLO"; | Membuat variabel teks bernama str dan mengisinya dengan kata "HELLO". |
stack<char> st; | Membuat sebuah tumpukan (stack) kosong bernama st yang khusus untuk menyimpan karakter/huruf (char). |
int jml = 0; | Membuat variabel jml bernilai 0 untuk menghitung jumlah huruf yang dimasukkan. |
for(char s : str) { | Memulai perulangan: mengambil setiap huruf dari kata "HELLO" satu per satu (disimpan sementara di s). |
st.push(s); | Fase PUSH: Memasukkan huruf tersebut (s) ke posisi paling atas tumpukan (stack). |
jml++; | Menambah nilai hitungan jml sebanyak 1. |
} | Menutup blok perulangan pemasukan huruf. Saat ini tumpukan berisi: H (paling bawah), E, L, L, O (paling atas). |
while(jml != 0) { | Memulai perulangan baru: selama jumlah huruf (jml) belum habis (0), lakukan perintah di bawah. |
cout << st.top(); | Melihat huruf paling atas di tumpukan menggunakan st.top(), lalu mencetaknya ke layar. |
st.pop(); | Fase POP: Menghapus/mengeluarkan huruf yang paling atas dari tumpukan. |
jml--; | Mengurangi nilai hitungan jml sebanyak 1 karena satu huruf sudah dikeluarkan. |
} | Menutup blok perulangan pengeluaran. Ini akan mencetak huruf dari atas ke bawah: O, L, L, E, H. |
Visualisasi:
Langkah | Aksi (Kode) | Kondisi Stack (Bawah → Atas) | Teks Tercetak | Keterangan |
FASE 1 | Memasukkan Huruf (Perulangan for) |
1 | push('H') | H | (kosong) | Huruf 'H' masuk. jml = 1 |
2 | push('E') | H, E | (kosong) | Huruf 'E' masuk. jml = 2 |
3 | push('L') | H, E, L | (kosong) | Huruf 'L' masuk. jml = 3 |
4 | push('L') | H, E, L, L | (kosong) | Huruf 'L' masuk. jml = 4 |
5 | push('O') | H, E, L, L, O | (kosong) | Huruf 'O' masuk. jml = 5. Loop selesai. |
FASE 2 | Mengeluarkan Huruf (Perulangan while) |
6 | top() & pop() | H, E, L, L | O | Cetak huruf teratas ('O'). Hapus 'O'. jml = 4 |
7 | top() & pop() | H, E, L | O L | Cetak huruf teratas ('L'). Hapus 'L'. jml = 3 |
8 | top() & pop() | H, E | O L L | Cetak huruf teratas ('L'). Hapus 'L'. jml = 2 |
9 | top() & pop() | H | O L L E | Cetak huruf teratas ('E'). Hapus 'E'. jml = 1 |
10 | top() & pop() | (kosong) | O L L E H | Cetak huruf teratas ('H'). Hapus 'H'. jml = 0. Selesai. |
3. Konversi Infix ke Postfix
Deskripsi (Fungsi) Program:
Kode ini bertujuan untuk mengubah ekspresi matematika biasa yang sering kita tulis (disebut Infix, contoh: A + B) menjadi format yang lebih mudah diproses oleh komputer/mesin (disebut Postfix, contoh: A B +). Proses konversi ini menggunakan struktur data Stack.
Code:
Hasil/Output Program:
Penjelasan Program:
Baris / Blok Kode | Penjelasan |
int prioritas(char op) { ... } | Membuat fungsi untuk memberi nilai prioritas operator. Pangkat (^) bernilai 3, kali/bagi bernilai 2, tambah/kurang bernilai 1. Selain itu 0. |
bool isOp(char c) { ... } | Membuat fungsi untuk mengecek apakah karakter yang sedang dibaca adalah operator matematika. Jika iya, kembalikan true (benar). |
string infixToPostfix(string infix) { | Membuat fungsi utama pengubah Infix ke Postfix yang menerima satu kalimat (string) infix. |
stack<char> st; | Membuat sebuah tumpukan (Stack) kosong untuk menyimpan sementara para operator (seperti +, *, (). |
string postfix = ""; | Membuat wadah teks kosong bernama postfix untuk menyusun hasil akhir. |
for(i = 0; i < infix.length(); i++) { | Memulai perulangan untuk membaca karakter di dalam infix satu per satu dari kiri ke kanan. |
char c = infix[i]; | Menyimpan karakter yang sedang dibaca saat ini ke dalam variabel c. |
Aturan 1 (Huruf/Angka): |
if(isalnum(c)) { | Mengecek apakah c adalah huruf atau angka (operand). |
postfix += c; | Jika iya, jangan masukkan ke Stack, tapi langsung tempelkan ke hasil postfix. |
Aturan 2 (Kurung Buka): |
} else if(c == '(') { | Mengecek apakah c adalah tanda kurung buka (. |
st.push(c); | Jika iya, masukkan (Push) tanda ( tersebut ke dalam Stack. |
Aturan 3 (Kurung Tutup): |
} else if(c == ')') { | Mengecek apakah c adalah tanda kurung tutup ). |
while(!st.empty() && st.top() != '(') { | Jika iya, lakukan perulangan: selama Stack tidak kosong dan bagian teratasnya bukan (, maka... |
postfix += st.top(); st.pop(); | ...pindahkan operator dari atas Stack ke hasil postfix, lalu hapus dari Stack (Pop). |
if(!st.empty()) { st.pop(); } | Setelah menemukan (, keluarkan tanda ( tersebut dari Stack dan buang (tidak dimasukkan ke postfix). |
Aturan 4 (Operator): |
} else if(isOp(c)) { | Mengecek apakah c adalah operator (+, -, *, dll). |
while(!st.empty() && prioritas(st.top()) >= prioritas(c)) | Jika iya, cek: apakah ada operator lain di pucuk Stack yang prioritasnya lebih tinggi atau sama dengan c? |
postfix += st.top(); st.pop(); | Jika ada, pindahkan operator tersebut dari Stack ke hasil postfix (Pop). Lakukan terus selama syarat di atas terpenuhi. |
st.push(c); | Setelah selesai dicek, masukkan (Push) operator c yang baru ini ke dalam Stack. |
Penyelesaian Akhir: |
while(!st.empty()) { | Setelah semua karakter selesai dibaca, jika masih ada sisa operator di dalam Stack... |
postfix += st.top(); st.pop(); } | ...keluarkan semuanya satu per satu dan tempelkan ke ujung hasil postfix. |
return postfix; | Kembalikan teks postfix yang sudah jadi sebagai hasil akhir fungsi. |
int main(void) { ... } | Fungsi utama. Meminta masukan teks infix, memprosesnya menggunakan fungsi di atas, lalu mencetak postfix-nya ke layar. |
Visualisasi:
Langkah | Karakter Dibaca | Kondisi Stack (Bawah → Atas) | Hasil Postfix Sementara | Keterangan |
1 | ( | ( | (kosong) | Tanda kurung buka ( selalu dimasukkan (Push) ke Stack. |
2 | A | ( | A | Huruf langsung masuk ke hasil Postfix. |
3 | + | ( , + | A | Operator + dimasukkan ke Stack di atas (. |
4 | B | ( , + | A B | Huruf langsung masuk ke hasil Postfix. |
5 | ) | (kosong) | A B + | Tanda kurung tutup )! Keluarkan (Pop) semua isi Stack ke Postfix sampai bertemu (. Tanda kurung kemudian dibuang. |
6 | * | * | A B + | Stack dalam keadaan kosong, operator * langsung dimasukkan ke Stack. |
7 | C | * | A B + C | Huruf langsung masuk ke hasil Postfix. |
8 | Selesai (End) | (kosong) | A B + C * | Karakter habis. Keluarkan (Pop) semua sisa operator di Stack ke bagian akhir Postfix. |
4. Evaluasi (Menghitung) Postfix
Deskripsi (Fungsi) Program:
Program ini menggunakan Stack digunakan untuk menahan angka (operand). Sehingga, kode ini bertugas untuk menghitung (mengevaluasi) hasil akhir dari ekspresi postfix.
Code:
Hasil/Output Program:
Penjelasan Program:
Baris / Blok Kode | Penjelasan |
int evaluatePostfix(string exp) { | Membuat fungsi bernama evaluatePostfix yang menerima teks Postfix (exp). |
stack<int> st; | Membuat tumpukan (Stack) yang khusus untuk menyimpan angka bulat (int). |
for(char c : exp) { | Memulai perulangan untuk membaca setiap karakter c dari teks exp. |
Kondisi 1: Jika Angka |
if(isdigit(c)) { | Mengecek apakah karakter c adalah angka (0-9). |
st.push(c - '0'); | Mengubah karakter teks menjadi nilai angka sungguhan (mengurangi nilai ASCII '0'), lalu memasukkannya ke Stack. |
Kondisi 2: Jika Operator |
} else { | Jika karakter bukan angka (berarti operator matematika). |
int val2 = st.top(); st.pop(); | Ambil angka teratas Stack, simpan sebagai val2 (angka kanan), lalu hapus dari Stack. |
int val1 = st.top(); st.pop(); | Ambil angka teratas berikutnya, simpan sebagai val1 (angka kiri), lalu hapus dari Stack. |
Proses Perhitungan |
switch (c) { | Mengecek jenis operatornya. |
case '+': | Jika operatornya +. |
st.push(val1 + val2); break; | Tambahkan val1 dengan val2, lalu masukkan hasilnya ke Stack. break untuk berhenti mengecek. |
case '-': | Jika operatornya -. |
st.push(val1 - val2); break; | Kurangi val1 dengan val2, lalu masukkan hasilnya ke Stack. |
case '*': | (Sama seperti di atas, namun untuk perkalian). |
case '/': | (Sama seperti di atas, namun untuk pembagian). |
} | Menutup blok pengecekan operator (switch). |
Penyelesaian Akhir |
return st.top(); | Setelah semua teks dibaca, kembalikan 1 angka terakhir yang tersisa di Stack sebagai hasil akhir. |
int main(void) { ... } | Fungsi utama. Meminta masukan teks Postfix dari pengguna, lalu mencetak hasil evaluasinya ke layar. |
Visualisasi:
Langkah | Karakter Dibaca | Kondisi Stack (Bawah → Atas) | Keterangan |
1 | 2 | 2 | Angka. Masukkan (Push) ke Stack. |
2 | 3 | 2, 3 | Angka. Masukkan (Push) ke Stack. |
3 | + | 5 | Operator! Keluarkan 3 (val2) dan 2 (val1). Hitung: 2 + 3 = 5. Masukkan 5 ke Stack. |
4 | 5 | 5, 5 | Angka. Masukkan (Push) ke Stack. |
5 | * | 25 | Operator! Keluarkan 5 (val2) dan 5 (val1). Hitung: 5 * 5 = 25. Masukkan 25 ke Stack. |
6 | Selesai | 25 | Teks habis. Hasil akhirnya adalah angka teratas: 25. |
5. Multi Digit Postfix
Deskripsi (Fungsi) Program:
Program ini berfungsi untuk membaca, memproses, dan menghitung hasil akhir dari sebuah operasi matematika yang ditulis dalam format Postfix (di mana operator diletakkan setelah angka, contohnya 10 20 +) dan mampu untuk mengenali dan menghitung angka multi-digit dengan syarat setiap angka dan operator dipisahkan oleh spasi.
Code:
Hasil/Output Program:
Penjelasan Program:
Baris / Blok Kode | Penjelasan |
stringstream ss(exp); | Memanggil fungsi "pemecah kalimat" bernama ss (String Stream). Tugasnya membelah teks panjang exp menjadi potongan-potongan kecil berdasarkan spasi. |
string token; | Membuat wadah teks bernama token untuk menyimpan setiap potongan kata/angka yang sudah dibelah tadi. |
while(ss >> token) { | Memulai perulangan: Mengambil potongan teks satu per satu dari ss dan memasukkannya ke token sampai teksnya habis. |
if(token == "+" ... ) { | Mengecek apakah potongan teks token tersebut adalah operator matematika (+, -, *, /). |
(Blok st.top() & st.pop()) | Mengambil 2 angka teratas dari Stack |
(Blok if-else perhitungan) | Menggantikan fungsi switch untuk menghitung hasil berdasarkan operatornya). |
} else { | Jika potongan teks tersebut bukan operator (berarti teks tersebut adalah sebuah angka, misal "150"). |
st.push(stoi(token)); | Mengubah teks angka "150" menjadi angka sungguhan 150 menggunakan perintah stoi (String to Integer), lalu memasukkannya ke Stack. |
getline(cin, postfix); | getline digunakan agar program membaca seluruh kalimat utuh beserta spasi-spasinya. |
Visualisasi:
Langkah | Karakter Dibaca (Token) | Kondisi Stack (Bawah → Atas) | Keterangan |
1 | 12 | 12 | Token berupa angka. Ubah ke integer (stoi) dan Push ke Stack. |
2 | 3 | 12, 3 | Token berupa angka. Ubah ke integer (stoi) dan Push ke Stack. |
3 | + | 15 | Operator! Keluarkan 3 (val2) dan 12 (val1). Hitung: 12 + 3 = 15. Push 15 ke Stack. |
4 | 4 | 15, 4 | Token berupa angka. Ubah ke integer (stoi) dan Push ke Stack. |
5 | * | 60 | Operator! Keluarkan 4 (val2) dan 15 (val1). Hitung: 15 * 4 = 60. Push 60 ke Stack. |
6 | Selesai | 60 | Teks habis. Stack menyisakan hasil akhir 60. |
Komentar
Posting Komentar