Studi kasus Stack
Aplikasi penggunaan stack
Nama : Fakhrian Elanta
NRP : 5025251019
Konversi Notasi Infix ke postfix
#include <iostream>
#include <stack>
#include <string>
#include <cctype>
using namespace std;
// Fungsi untuk menentukan prioritas operator
int precedence(char op) {
if (op == '^')
return 3;
else if (op == '*' || op == '/')
return 2;
else if (op == '+' || op == '-')
return 1;
else
return 0;
}
// Fungsi untuk cek apakah karakter adalah operator
bool isOperator(char c) {
return (c == '+' || c == '-' || c == '*' || c == '/' || c == '^');
}
// Fungsi utama konversi infix ke postfix
string infixToPostfix(string infix) {
stack<char> st;
string postfix = "";
for (int i = 0; i < infix.length(); i++) {
char c = infix[i];
// Jika operand (huruf/angka)
if (isalnum(c)) {
postfix += c;
}
// Jika '('
else if (c == '(') {
st.push(c);
}
// Jika ')'
else if (c == ')') {
while (!st.empty() && st.top() != '(') {
postfix += st.top();
st.pop();
}
if (!st.empty())
st.pop(); // hapus '('
}
// Jika operator
else if (isOperator(c)) {
while (!st.empty() && precedence(st.top()) >= precedence(c)) {
postfix += st.top();
st.pop();
}
st.push(c);
}
}
// Pop semua operator tersisa
while (!st.empty()) {
postfix += st.top();
st.pop();
}
return postfix;
}
// Main function
int main() {
string infix;
cout << "Masukkan ekspresi infix: ";
cin >> infix;
string postfix = infixToPostfix(infix);
cout << "Postfix: " << postfix << endl;
return 0;
}
Visualisasi A+B*C-D
| Baca | Aksi | Stack | Hasil |
|---|---|---|---|
A | Operand → langsung ke hasil | [] | A |
+ | Stack kosong → push | [+] | A |
B | Operand → langsung ke hasil | [+] | AB |
* | Prioritas * > + → push | [+, *] | AB |
C | Operand → langsung ke hasil | [+, *] | ABC |
- | Prioritas - ≤ * → pop * | [+] | ABC* |
- | Prioritas - ≤ + → pop + | [] | ABC*+ |
- | Push - | [-] | ABC*+ |
D | Operand → langsung ke hasil | [-] | ABC*+D |
| (end) | Keluarkan sisa stack | [] | ABC*+D- |
Hasil akhir ABC*+D-
Evaluasi Notasi postfix single digit
#include <iostream>
#include <stack>
#include <cctype>
using namespace std;
// Fungsi evaluasi postfix
int evaluatePostfix(string exp) {
stack<int> st;
for (char c : exp) {
// Jika operand (angka)
if (isdigit(c)) {
st.push(c - '0'); // konversi char ke int
}
// Jika operator
else {
int val2 = st.top(); st.pop();
int val1 = st.top(); st.pop();
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;
}
}
}
return st.top();
}
// Main
int main() {
string postfix;
cout << "Masukkan ekspresi postfix: ";
cin >> postfix;
cout << "Hasil evaluasi: " << evaluatePostfix(postfix) << endl;
return 0;
}
Contoh Input: 23+5*
| Baca | Aksi | Stack |
|---|---|---|
| 2 | Angka → push | [2] |
3 | Angka → push | [2, 3] |
+ | Pop 3 (val2), pop 2 (val1) → 2+3=5 → push | [5] |
| 5 | Angka → push | [5, 5] |
| * | Pop 5 (val2), pop 5 (val1) → 5*5=25 push | [25] |
Hasil akhir 25
Evaluasi Notasi postfix multi digit
#include <iostream>
#include <stack>
#include <sstream>
using namespace std;
int evaluatePostfix(string exp) {
stack<int> st;
stringstream ss(exp);
string token;
while (ss >> token) {
// Jika operator
if (token == "+" || token == "-" || token == "*" || token == "/") {
int val2 = st.top(); st.pop();
int val1 = st.top(); st.pop();
if (token == "+") st.push(val1 + val2);
else if (token == "-") st.push(val1 - val2);
else if (token == "*") st.push(val1 * val2);
else if (token == "/") st.push(val1 / val2);
}
// Jika operand
else {
st.push(stoi(token));
}
}
return st.top();
}
int main() {
string postfix;
cout << "Masukkan postfix (pisahkan dengan spasi): ";
getline(cin, postfix);
cout << "Hasil: " << evaluatePostfix(postfix) << endl;
return 0;
}
Contoh Input: 2 4 * 5 + 7 *
Komentar
Posting Komentar