Infix Postfix Stack Implementation
Pada blog ini akan menyajikan penerapan stack dalam operasi infix postfix dan juga cara kerja stack untuk reverse string.
Convert Infix to Postfix
Pada program ini, akan dilakukan konversi operasi matematika bentuk infix ke bentuk postfix.
#include <bits/stdc++.h>
using namespace std;
int precendence(char op){
if (op == '^') return 3;
else if (op == '*' || op == '/') return 2;
else if (op == '+' || op == '-') return 3;
else return 0;
}
bool isOperator(char c){
return (c == '+' || c == '-' || c == '^' || c == '*' || c == '/');
}
string infixtopostfix(string infix){
stack<char> s;
string postfix = "";
for (int i = 0; i < infix.length(); i++){
char c = infix[i];
if (isalnum(c)){
postfix += c;
}
else if (c == '('){
s.push(c);
}
else if (c == ')'){
while (!s.empty() && s.top() != '('){
postfix += s.top();
s.pop();
}
if (!s.empty()) s.pop();
}
else if (isOperator(c)){
while (!s.empty() && precendence(s.top()) >= precendence(c)){
postfix += s.top();
s.pop();
}
s.push(c);
}
}
while (!s.empty()){
postfix += s.top();
s.pop();
}
return postfix;
}
int main(){
string infix;
cout << "Masukkan ekspresi infix: ";
cin >> infix;
string postfix = infixtopostfix(infix);
cout << "Postfix: " << postfix << endl;
return 0;
}
Mari kita coba sebuah testcase beserta outputnya.
Fungsi dapat berjalan dengan baik, berikut visualisasi cara kerjanya.
| SYMBOL | POSTFIX STRING | STACK | REMARKS |
|---|---|---|---|
| ( | ( | Push ( ke dalam stack. | |
| A | A | ( | Tambahkan operand ke postfix string. |
| + | A | ( + | Push operator ke dalam stack. |
| B | A B | ( + | Tambahkan operand ke postfix string. |
| ) | A B + | Ketemu ), pop isi stack ke postfix string sampai menemukan (. | |
| * | A B + | * | Stack kosong, push * ke dalam stack. |
| C | A B + C | * | Tambahkan operand ke postfix string. |
| End of string | A B + C * | Input habis. Pop semua sisa operator dari stack ke postfix string. |
Evaluate Postfix Operations
Program ini akan menghitung operasi postfix.
using namespace std;
int evaluatePostfix(string exp){
stack<int> s;
for (char c : exp){
if(isdigit(c)) s.push(c - '0');
else {
int val2 = s.top(); s.pop();
int val1 = s.top(); s.pop();
switch(c){
case '+': s.push(val1 + val2); break;
case '-': s.push(val1 - val2); break;
case '*': s.push(val1 * val2); break;
case '/': s.push(val1 / val2); break;
}
}
}
return s.top();
}
int main(){
string postfix;
cout << "Masukkan ekspresi postfix: ";
cin >> postfix;
cout << "Hasil evaluasi: " << evaluatePostfix(postfix) << endl;
return 0;
}
Kita masukkan testcase beserta outputnya.
Fungsi dapat berjalan dengan baik, berikut visualisasi cara kerjanya.
| SYMBOL | STACK (Bottom → Top) | REMARKS |
|---|---|---|
| 2 | 2 | Angka (operand). Push 2 ke dalam stack. |
| 3 | 2, 3 | Angka (operand). Push 3 ke dalam stack. |
| + | 5 | Operator. Pop 3 (val2) dan 2 (val1). Hitung 2 + 3 = 5. Push 5 ke dalam stack. |
| 5 | 5, 5 | Angka (operand). Push 5 ke dalam stack. |
| * | 25 | Operator. Pop 5 (val2) dan 5 (val1). Hitung 5 * 5 = 25. Push 25 ke dalam stack. |
| End of string | 25 | Input habis. Hasil evaluasi adalah nilai tunggal yang tersisa di dalam stack (25). |
Multidigit Postfix Evaluation
Program ini akan menghitung operasi postfix dengan digit angka yang lebih dari satu digit, kita pakai stringstream untuk memisahkan tiap karakternya dengan spasi.
#include <bits/stdc++.h>
using namespace std;
int evaluatePostfix(string exp){
stack<int> s;
stringstream ss(exp);
string token;
while (ss >> token){
if (token == "+" || token == "-" || token == "*" || token == "/"){
int val2 = s.top(); s.pop();
int val1 = s.top(); s.top();
if (token == "+") s.push(val1 + val2);
if (token == "-") s.push(val1 - val2);
if (token == "*") s.push(val1 * val2);
if (token == "/") s.push(val1 / val2);
}
else s.push(stoi(token));
}
return s.top();
}
int main(void){
string postfix;
cout << "Masukkan postfix (pisahkan dengan spasi): ";
getline(cin, postfix);
cout << "Hasil: " << evaluatePostfix(postfix) << endl;
return 0;
}
Berikut adalah testcase dan outputnya.
Fungsi dapat berjalan dengan baik, berikut adalah cara kerjanya.
| TOKEN | STACK | REMARKS |
|---|---|---|
| 12 | 12 | Bukan operator. Konversi string "12" menjadi integer dan push ke dalam stack. |
| 3 | 12, 3 | Bukan operator. Konversi string "3" menjadi integer dan push ke dalam stack. |
| + | 15 | Operator. Pop 3 (val2) dan 12 (val1). Hitung 12 + 3 = 15. Push 15 ke dalam stack. |
| 4 | 15, 4 | Bukan operator. Konversi string "4" menjadi integer dan push ke dalam stack. |
| * | 60 | Operator. Pop 4 (val2) dan 15 (val1). Hitung 15 * 4 = 60. Push 60 ke dalam stack. |
| End of string | 60 | Input habis. Hasil evaluasi adalah nilai terakhir di stack (60). |
String Inversion
Program ini akan membalik urutan kata dari string yang kita masukkan, ini adalah modifikasi sederhana dari contoh program membalik string di ppt.
#include <bits/stdc++.h>
using namespace std;
int main(){
string kata;
stack<char> s;
cin >> kata;
for (int i = 0; i < kata.size(); i++){
s.push(kata[i]);
}
while (!s.empty()){
cout << s.top();
s.pop();
}
}
Ini adalah contoh input dan outputnya.
Pada input diwajibkan hanya ada satu kata tanpa spasi, nantinya setiap karakter string akan dimasukkan stack. Stack tersebut akan dikeluarkan isinya mulai dari top sehingga outputnya akan membalik string input.
Komentar
Posting Komentar