Implementasi Stack dalam C++
Implementasi Stack dalam Konversi dan Evaluasi Ekspresi
Definisi Stack
Stack adalah struktur data linear yang menggunakan prinsip LIFO (Last In, First Out), yaitu elemen terakhir yang masuk akan menjadi elemen pertama yang keluar. Dalam pemrograman, stack sering digunakan untuk berbagai kebutuhan, salah satunya dalam pengolahan ekspresi matematika.
Penerapan Stack pada Ekspresi Matematika
Dalam ekspresi matematika, terdapat beberapa bentuk penulisan, seperti:
-
Infix → contoh:
A + B -
Postfix → contoh:
AB+
Bentuk infix lebih mudah dipahami manusia, tetapi lebih kompleks untuk diproses oleh komputer karena melibatkan prioritas operator. Oleh karena itu, digunakan postfix yang lebih sederhana dalam proses evaluasi. Dalam proses ini, stack berperan penting baik saat konversi maupun evaluasi.
Konversi Infix ke Postfix
Pada tahap ini, ekspresi infix diubah menjadi postfix menggunakan stack. Operator akan disimpan sementara di dalam stack sesuai dengan prioritasnya.
Kode Program
#include <iostream>
#include <stack>
#include <string>
#include <cctype>
using namespace std;
int precedence(char op) {
if (op == '^')
return 3;
else if (op == '*' || op == '/')
return 2;
else if (op == '+' || op == '-')
return 1;
else
return 0;
}
bool isOperator(char c) {
return (c == '+' || c == '-' || c == '*' || c == '/' || c == '^');
}
string infixToPostfix(string infix) {
stack<char> st;
string postfix = "";
for (int i = 0; i < infix.length(); i++) {
char c = infix[i];
if (isalnum(c)) {
postfix += c;
}
else if (c == '(') {
st.push(c);
}
else if (c == ')') {
while (!st.empty() && st.top() != '(') {
postfix += st.top();
st.pop();
}
if (!st.empty())
st.pop();
}
else if (isOperator(c)) {
while (!st.empty() && precedence(st.top()) >= precedence(c)) {
postfix += st.top();
st.pop();
}
st.push(c);
}
}
while (!st.empty()) {
postfix += st.top();
st.pop();
}
return postfix;
}
int main() {
string infix;
cout << "Masukkan ekspresi infix: ";
cin >> infix;
string postfix = infixToPostfix(infix);
cout << "Postfix: " << postfix << endl;
return 0;
}
Output:
 |
| Source code:Konversi Infix ke Postfix |
Evaluasi Postfix
Setelah mendapatkan bentuk postfix, langkah selanjutnya adalah menghitung hasilnya. Proses ini juga menggunakan stack.
Kode Program
#include <iostream>
#include <stack>
#include <cctype>
using namespace std;
int evaluatePostfix(string exp) {
stack<int> st;
for (int i = 0; i < exp.length(); i++) {
char c = exp[i];
if (isdigit(c)) {
st.push(c - '0');
}
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();
}
int main() {
string postfix;
cout << "Masukkan ekspresi postfix: ";
cin >> postfix;
cout << "Hasil evaluasi: " << evaluatePostfix(postfix) << endl;
return 0;
}
Output:
 |
| Source code:Evaluasi Postfix |
Program ini membaca ekspresi postfix, kemudian:
- Jika angka → dimasukkan ke stack
- Jika operator → mengambil dua nilai dari stack, lalu dihitung
Multi Digit Postfix
Program sebelumnya hanya mendukung satu digit. Untuk mengatasi angka lebih dari satu digit, digunakan stringstream.
Kode Program
#include <iostream>
#include <stack>
#include <sstream>
using namespace std;
int evaluatePostfix(string exp) {
stack<int> st;
stringstream ss(exp);
string token;
while (ss >> token) {
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);
}
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;
}
Output:
 |
| Source code:Multi Digit Postfix |
Dengan menggunakan
stringstream, input dapat dipisahkan berdasarkan spasi sehingga mendukung angka seperti 12, 100, dan lainnya.
Comments
Post a Comment