Masala: [], {} va () uchta tiplardan tashkil topgan satr berilgan. Qavslar to’g’ri qo’yilganligini tekshiring (boshqa simvollarga qaramagan holda). Masalan:
[()]{} ][ [({)]}
Yechim: qavslar ichma ichligini hisoblagich. Agarda hisoblagich 0 bo’lsa, qavs to’gri qo’yilgan bo’ladi.
Bu masalani uchta hisoblagich bilan qilsa bo’ladimi?
?
[ ( { ) ] }
(: 0 1 0
[: 0 1 0
{: 0 1 0
[ ( { ) ] }
( ( ) ) ( )
1 2 1 0 1 0
( ( ) ) ( )
( ( ) ) ) (
1 2 1 0 -1 0
( ( ) ) ) (
( ( ) ) (
1 2 1 0 1
( ( ) ) (
Qavslar masalasi
Algoritm:
Boshida stek bo’sh;
Sikl boshida satr barcha simvollarini tartib bo’yiicha ko’rib chiqamiz;
Agar navbatdagi simvol ochiladigan qavs bo’lsa, uni stek boshiga o’tkazamiz;
Agar simvol yopiladigan qavs bo’lsa, stek boshini tekshiramiz: u yerda berilgan qavsga mos ochiluvchi qavs bo’lishi lozim (agarda bunday bo’lmasa, u holda xatolik);
Agar stek oxiri bo’sh bo’lmasa, u holda ifoda noto’g’ri.
[ ( ( ) ) ] { }
[
[
(
[
(
(
[
(
(
[
(
[
{
{
Struktura-stek:
const MAXSIZE = 100;
struct Stack {
char data[MAXSIZE]; // 100 ta simvolli stek
int size; // elementlar soni
};
Element qo’shish:
int Push ( Stack &S, char x )
{
if ( S.size == MAXSIZE ) return 0;
S.data[S.size] = x;
S.size ++;
return 1;
}
xatolik: stekni to’ldirish
Element qo’shish
Xatolik yo’q
Stekni amalga oshirish (massiv)
Stekni amalga oshirish (massiv)
char Pop ( Stack &S )
{
if ( S.size == 0 ) return char(255);
S.size --;
return S.data[S.size];
}
Boshidan elementni o’chirish:
Bo’shmi yoki yo’q?
int isEmpty ( Stack &S )
{
if ( S.size == 0 )
return 1;
else return 0;
}
xatolik: stek bo’sh
int isEmpty ( Stack &S )
{
return (S.size == 0);
}
Dastur
void main()
{
char br1[3] = { '(', '[', '{' };
char br2[3] = { ')', ']', '}' };
char s[80], upper;
int i, k, error = 0;
Stack S;
S.size = 0;
printf(“Qavsli ifodani kiriting > ");
gets ( s );
... // qayta ishlovchi asosiy sikl
if ( ! error && (S.size == 0) )
printf("\nIfoda to’g’ri\n");
else printf("\nnIfoda noto’g’ri\n");
}
Ochuvchi qavslar
Yopuvchi qavslar
U holda stekdan chiqarish
Xatolik belgisi
Satrni qayta ishlash (asosiy sikl)
for ( i = 0; i < strlen(s); i++ )
{
for ( k = 0; k < 3; k++ )
{
if ( s[i] == br1[k] ) // agar ochilivchi qavs bo’lsa
{
Push ( S, s[i] ); // stekka kiritish
break;
}
if ( s[i] == br2[k] ) // agar yopilivchi qavs bo’lsa
{
upper = Pop ( S ); // yoqori elementni olish
if ( upper != br1[k] ) error = 1;
break;
}
}
if ( error ) break;
}
s satr barcha simvollari bo’yicha sikl
Barcha qavslar bo’yicha sikl
xatolik: stek bo’sh yoki kerakli qavs emas
Xatolik bormi: u holda tekshirishga xojat yo’q
Stekni amalga oshirish (ro’yxat)
Element qo’shish:
Struktura tuguni:
struct Node {
char data;
Node *next;
};
typedef Node *PNode;
void Push (PNode &Head, char x)
{
PNode NewNode = new Node;
NewNode->data = x;
NewNode->next = Head;
Head = NewNode;
}
Boshidan elementni olish:
char Pop (PNode &Head) {
char x;
PNode q = Head;
if ( Head == NULL ) return char(255);
x = Head->data;
Head = Head->next;
delete q;
return x;
}
Asosiy dasturni o’zgartirish:
Stack S;
S.size = 0;
...
if ( ! error && (S.size == 0) )
printf("\Ifoda to’g’ri\n");
else printf("\nIfoda noto’g’ri \n");
PNode S = NULL;
(S == NULL)
stek bo’sh
Stekni amalga oshirish (ro’yxat)
Navbat
Biz navbat bilan ko’p joylarda duch kelamiz: magazinda, o’qishda, ishda va hokazo. Odatda biz unga e’tibor bermaymiz. Dasturiy tizimlarda ham bu navbat tushunchasi ishlatiladi.
Masalan, hujjatni chop etish uchun printerga jo’natsak, u navbatga turadi.
Navbat bizga nima uchun kerak!
!
Alabatta navbat 1-o’rinda tartib o’rnatish uchun zarur.
Navbat qanday ishlaydi!
!
Navbat
Biz hammamiz magazinda navbatga turganmiz. Navbatni har xil turlari mavjud. Masalan, prioritet bo’yicha navbat.
Hayotdan misol: veteranlar va nogironlar navbatsiz o’tkaziladi (ularni prioriteti yuqori).
Klassik navbatni ko’rib chiqamiz:
birinchi kelgan birinchi ketadi (FIFO – first input, first output)
Navbat har ikkala tomondan ochiq bo’ladi.
Navbat
Universal navbat har bir tuguni axborot qismi void turidagi ko’rsatkichdan iborat strukturadir:
struct slist_node
{
void* info;
struct slist_node* next;
};
struct que
{
struct slist_node* beg;
struct slist_node* end;
int size;
int width;
};
Bu yerda beg birinchi tugunga ko’rsatkich, end oxirgi tugunga ko’rsatkich, width ma’lumot hajmi, size navbatdagi elementlar soni
