Стек, Stack загвар класс, стекийн хэрэглээ

Стек нь өгөгдөл хийх (оруулах) ба авах (гаргах) гэсэн үндсэн хоёр үйлдэлтэй шугаман бүтэц юм. Эдгээр үйлдлүүдийг стекийн орой гэгдэх зөвхөн нэг төгсгөлд гүйцэтгэдэг. Өөрөөр хэбэл, хамгийн сүүлд орсон элемент эхэлж гарах зарчмаар ажиллана. Стекийг "сүүлд орсон нь эхэлж гарах" LIFO (Last in, First out) жагсаалт ч гэж нэрлэх нь бий.
Стекийг массив болон жагсаалтаар нэвтрүүлж болдог.
Стек загвар класс
Гишүүн функцүүд:
empty: хоосон эсэхийг шалгана.
size: хэмжээг нь буцаана.
top: оройн элемент.
push: элемент оруулах.
pop: элемент гаргах.
эдгээр функцүүд бүгд public хандалттай.
Стекийг маш олон бодлогонд ашиглаж болно. Хамгийн өргөн ашигладаг жшиээ гэвэл илэрхийлэл бодох, хаалтны баланс тогтоох, тоог тооллын системүүдийн хооронд хөрвүүлэх г.м.
Хаалтны баланс тогтоох бодлогыг stack загвар класс ашиглан бодъё. Хаалтны баланс тогтоох гэдэг маань илэрхийлэлд орсон (), [], {} хаалтууд зөв логик дараалалтай орсон эсэхийг шалгана гэсэн үг. Жишээлбэл, 2*{10+5-3*(2*a[5] - 7)} гэвэл зөв баланслагдсан байна, харин 2*{10+5-3*(2*a[5] - 7}) тохиолдолд буруу.

Хаалт зөв баланслагдаагүй байх тохиолдлууд:
1. Хаах хаалт тааралдахад стек хоосон байх
2. Бүх тэмдэгтүүдийг уншиж дуусахад стек хоосон биш байх
3. Тухайн хаах хаалтны хувьд стекийн оройгоос авсан нээх хаалт нь харгалзахгүй байх.

#include <iostream>
#include <string>
#include <stack>
using namespace std;

int main() {
stack<char> st;
char ch[100], c;
int l, i;
bool ok = true;

string errorMessage = "";

cout<<" Ilerkhiillee oruulna uu?\n -> ";
gets(ch);
l = strlen(ch);
for(i=0; i<l; i++) {
if(ch[i] == '(' || ch[i] == '{' || ch[i] == '[')
st.push(ch[i]);
if(ch[i] == ')' || ch[i] == '}' || ch[i] == ']') {
if(!st.empty()) {
c = st.top();
if((c == '(' && ch[i] == ')') || (c == '{' && ch[i] == '}') || (c == '[' && ch[i] == ']'))
st.pop();
else {
ok = false;
errorMessage.push_back(c);
errorMessage.append("-iin khaakh khaalt buruu baina!");
break;
}
}
else {
ok = false;
errorMessage.push_back(ch[i]);
errorMessage.append("-iin neekh khaalt baikhgui baina!");
break;
}
}
}

cout<<"\n Khariu: ";
if(ok) {
if(!st.empty()) {
ok = false;
errorMessage.push_back(st.top());
errorMessage.append("-iin khaakh khaalt baikhgui baina!");
}
else
cout<<"Khaaltny balans zov baina";
}
if(!ok)
cout<<"Khaaltny balans buruu baina.\n Aldaa: "<<errorMessage;
cout<<"\n\n";
system("pause");
}

Сэтгэгдэл үлдээх