Struktur Data - Studi Kasus Stack
Nama : Aga Nafta Filadelfiano
NRP : 5025251055
Kelas : Struktur Data (D)
NRP : 5025251055
Kelas : Struktur Data (D)
Studi Kasus Stack
1. Konversi Infix ke Postfix
Infix adalah notasi yang menempatkan operator di antara dua operand (A + B), sedangkan Postfix menempatkan operator setelah operand (contoh: A B +).
Prosedur Konversi Infix ke Postfix
- Baca (scan) ekspresi infix dari kiri ke kanan.
- Jika simbol yang dibaca adalah tanda kurung buka '(' , maka Push ke dalam stack.
- Jika simbol adalah operand (nilai/variabel) tambahkan ke hasil postfix (output).
- Jika simbol adalah tanda kurung tutup ')' :
- Pop semua elemen dari stack
- Tambahkan ke postfix
- Lakukan sampai ditemukan pasangan tanda kurung buka '('
- Buang tanda kurung buka tersebut (tidak dimasukkan ke output)
- Jika simbol adalah operator (+, -, *, /, dll):
- Selama Stack tidak kosong, dan Operator di atas stack memiliki prioritas lebih tinggi atau sama, maka Pop operator dari stack dan tambahkan ke postfix
- Setelah itu Push operator yang sedang dibaca ke dalam stack
- Setelah seluruh ekspresi selesai dibaca:
- Pop semua operator yang tersisa di stack
- Tambahkan ke postfix
Syntax Program:
Output:
Penjelasan Code:
a) Menentukan Prioritas
int precedence(char op) {
if (op == '^') return 3;
else if (op == '*' || op == '/') return 2;
else if (op == '+' || op == '-') return 1;
else return 0;
}
- Nilai 3 diberikan untuk pangkat (^) sebagai prioritas tertinggi
- Nilai 2 diberikan untuk perkalian (*) dan pembagian (/)
- Nilai 1 diberikan untuk penjumlahan (+) dan pengurangan (-)
- Nilai 0 diberikan untuk karakter lain agar tidak mengganggu pembandingan prioritas di dalam stack
b) Mengidentifikasi Operator
bool isOperator(char c) {
return (c == '+' || c == '-' || c == '*' || c == '/' || c == '^');
}
Fungsi boolean bertugas untuk memastikan apakah karakter yang sedang diproses termasuk dalam kategori operator yang didukung oleh program atau tidak.
c) Mengonversi Infix ke Postfix
if (isalnum(c)) {
postfix += c;
}
Jika karakter adalah alphanumeric (A-Z, 0-9), maka karakter tersebut tidak perlu masuk ke stack dan langsung ditambahkan ke string hasil (postfix).
else if (c == '(') {
st.push(c);
}
Kurung buka selalu dimasukkan ke dalam stack sebagai penanda awal blok operasi yang harus diprioritaskan.
else if (c == ')') {
while (!st.empty() && st.top() != '(') {
postfix += st.top();
st.pop();
}
if (!st.empty()) st.pop();
}
Saat bertemu kurung tutup, semua operator yang ada di dalam stack dipindahkan ke output satu per satu hingga bertemu kurung buka yang berpasangan. Tanda kurung itu sendiri kemudian dibuang (pop).
else if (isOperator(c)) {
while (!st.empty() && precedence(st.top()) >= precedence(c)) {
postfix += st.top();
st.pop();
}
st.push(c);
}
Sebelum operator baru masuk ke stack, program memeriksa puncak stack. Jika operator di puncak stack memiliki prioritas yang lebih tinggi atau sama, maka operator lama tersebut harus di pop ke output terlebih dahulu. Setelah itu, operator baru baru boleh push ke stack.
while (!st.empty()) {
postfix += st.top();
st.pop();
}
Setelah seluruh string input selesai dibaca, semua operator yang masih tertinggal di dalam stack dipindahkan ke string output untuk menyelesaikan ekspresi.
Visualisasi:
2. Evaluasi Postfix
Prosedur Evaluasi Postfix:
- Scan ekspresi Postfix dari kiri ke kanan.
- Jika ditemukan Operand, maka Push ke dalam Stack.
- Jika ditemukan Operator, maka Pop pada dua elemen teratas Stack, operasikan keduanya, lalu masukkan kembali hasilnya ke dalam Stack.
- Setelah proses selesai, nilai akhir dalam Stack adalah hasil dari ekspresi tersebut.
Syntax Program:
Output:
Penjelasan Code:
a) Inisialisasi Stack
stack<int> st;
Stack ini digunakan untuk menyimpan nilai integer hasil pembacaan string maupun hasil perhitungan sementara.
b) Mengiterasi Karakter
for (char c : exp) { ... }
Program membaca ekspresi postfix karakter demi karakter dari kiri ke kanan.
c) Menangani Operand
if (isdigit(c)) {
st.push(c - '0');
}
- Fungsi isdigit(c) memeriksa apakah karakter tersebut adalah angka (0-9).
- Logika (c - '0') adalah cara mengubah tipe data 'char' menjadi 'int' berdasarkan nilai ASCII-nya.
- Hasilnya dimasukkan (push) ke dalam stack.
d) Menangani Operator
else {
int val2 = st.top(); st.pop();
int val1 = st.top(); st.pop();
- Saat bertemu operator (+, -, *, /), program akan mengambil dua angka teratas dari stack.
- Angka yang pertama di-pop menjadi val2 (kanan), dan yang kedua menjadi val1 (kiri).
switch (c) {
case '+': st.push(val1 + val2); break;
case '-': st.push(val1 - val2); break;
case '*': st.push(val1 * val2); break;
case '/': st.push(val1 / val2); break;
}
- Berdasarkan simbol operator, program melakukan operasi matematika yang sesuai.
- Hasil dari perhitungan tersebut langsung dimasukkan (push) kembali ke stack sebagai operand untuk operasi selanjutnya.
e) Hasil Akhir
return st.top();
Setelah seluruh karakter diproses, stack hanya akan menyisakan satu nilai. Nilai inilah yang merupakan hasil akhir dari ekspresi tersebut.
Visualisasi:
3. Multi Digit Postfix
Prosedur Multi Digit Postfix
- Baca (scan) ekspresi postfix dari kiri ke kanan secara bertahap.
- Jika simbol adalah operand (angka):
- Ubah string angka tersebut menjadi nilai numerik (int)
- Push nilai tersebut ke dalam stack.
- Jika simbol adalah operator (+, -, *, /):
- Pop elemen teratas stack sebagai operand kedua (val2).
- Pop elemen berikutnya dari stack sebagai operand pertama (val1).
- Hitung hasil operasi berdasarkan operator yang ditemukan (misal: val1 + val2).
- Push kembali hasil perhitungan tersebut ke dalam stack.
- Ulangi langkah 2 dan 3 sampai seluruh simbol dalam ekspresi selesai dibaca.
- Setelah proses selesai, nilai akhir dalam Stack adalah hasil dari ekspresi tersebut.
Syntax Program:
Output:
Penjelasan Code:
a) Penggunaan <sstream>
stringstream ss(exp);
Objek stringstream bertindak sebagai buffer yang memperlakukan string seperti aliran data (stream). Ini memungkinkan program memecah string menjadi potongan-potongan kecil (token) berdasarkan spasi secara otomatis.
b) Proses Pengambilan Token
while (ss >> token) { ... }
Kode ini akan terus berjalan selama masih ada "kata" atau angka yang bisa dibaca di dalam string.
c) Memisahkan Operator dan Operand
if (token == "+" || token == "-" || token == "*" || token == "/") {
int val2 = st.top(); st.pop();
int val1 = st.top(); st.pop();
Jika token yang dibaca adalah simbol matematika:
1. Program mengambil angka teratas stack sebagai operand kedua (val2)
2. Program mengambil angka berikutnya sebagai operand pertama (val1)
3. Dilakukan operasi matematika (val1 [operator] val2)
4. Hasilnya dimasukkan (push) kembali ke stack
else {
st.push(stoi(token));
}
Jika token bukan operator, maka dianggap sebagai angka. Angka tersebut kemudian dimasukkan (push) ke stack.
d) Mengambil Hasil Akhir
return st.top();
Setelah seluruh karakter diproses, stack hanya akan menyisakan satu nilai. Nilai inilah yang merupakan hasil akhir dari ekspresi tersebut.
Visualisasi:
Source Code: GitHub
