O’zbekiston Respublikasi Oliy va O’rta maxsus ta’lim vazirligi Muhammad Al-Xorazmiy nomidagi Toshkent Axborot Texnologiyalari Universititeti Farg’ona filliali

1+((2+3)*5+3)*7 
Bunday hollarda eng oddiy usul ochiluvchi qavslar uchun nest hisoblagichini 
kiritish kerak. Bu hisoblagich boshida nolga teng, har bir ochiluvchi qavs uchraganda 
uni bir birlikka oshiramiz, yopiluvchi qavs uchraganda esa bir birlikka kamaytiramiz. 
Bunda nest=0 bo’lgandagi amalni qarab chiqamiz, ya’ni qavs ichidagi amallar 
bajariladi. 
Agar bunda birorta ham amal topilmasa, u holda biz qavs bilan chegaralangan 
ifodani qidiramiz, buning uchun esa from+1..last-1 oraliq uchun rekursiv 
protsedurani chaqirishimiz kerak (bunda arifmetik ifodani to’g’ri kiritilgan deb 
hisoblaymiz). Yozuvni kamaytirish uchun protseduraning o’zgartirish kiritish 
mumkin bo’lgan qismini keltiramiz: 
PNode MakeTree (char Expr[], int first, int last) { 
int MinPrt, i, k, prt; 
int nest = 0; // ochilgan qavs hisoblagichi 
PNode Tree = new Node; 
... 
MinPrt = 100; 
for (i = first; i<=last; i++ ){ 
if (Expr[i] ==’(’) //ochiluvchi qavs 
{nest ++; continue;} 
if ( Expr[i] ==’)’) //yopiluvchi qavs 
{nest --; continue;} 

---

if (nest>0) continue; //qavs ichida 
prt = Priority (Expr[i]); 
if (prt<=MinPrt) { 
MinPrt=prt; k=i; 
} 
} 
if (MinPrt==100 && //ifodani to’liq qavsga olish 
Expr[first]==’(’ && Expr[last]==')'){ 
delete Tree; 
return MakeTree (Expr, first+1, last-1); 
} 
... 
return Tree; 
} 
Yangi tugun funktsiyaning boshida hosil qilinadi, agar ifoda to’liq qavs ichiga 
olingan bo’lsa, uni o’chirish kerak. 
Ko’pxonali sonlar va o’zgaruvchilar. Ko’pxonali sonlar yoki o’zgaruvchilar 
nomini saqlash uchun tugunning ma’lumotlar maydonida belgili massivni qo’llash 
kerak bo’ladi. 
struct Node { 
char data[40]; 
Node *left, *right; 
}; 
typedef Node *PNode; 
Yuqoridagidek, arifmetik ifoda to’g’ri yozilgan deb qaraymiz. Agar satrda 
birorta ham arifmetik amal belgisi (qavs belgisidan tashqari) va qavslar uchramasa, u 
holda butun ifodani bitta element (operand deb ataladi) – son yoki o’zgaruvchi nomi 
deb hisoblaymiz. Bu elementni tugunning ma’lumotlar maydoniga yozish uchun 
berilgan sondagi belgilarni nusxalovchi strncpy funktsiyasidan foydalanamiz. Bu 
funktsiya satr oxiriga belgi qo’ymaydi, shuning uchun ham uni qo’lda bajaramiz. 

---

PNode MakeTree (char Expr[], int first, int last) { 
int MinPrt, i, k, prt; 
PNode Tree = new Node; 
MinPrt = 100; 
for (i=first; i<=last; i++) { 
prt=Priority (Expr[i]); 
if (prt<=MinPrt) { 
MinPrt=prt; 
k=i; 
} 
} 
if (MinPrt==100) 
if (Expr[first]==’(’ && Expr[last]==')' ) { 
delete Tree; 
return MakeTree (Expr, first+1, last-1); 
} 
else { // son yoki o’zgaruvchi 
k=last - first + 1; 
strncpy (Tree->data, Expr+first, k); 
Tree->data[k]='\0'; 
Tree->left=NULL; 
Tree->right=NULL; 
return Tree; 
} 
Tree->data[0]=Expr[k]; //arifmetik amal belgisi 
Tree->data[1]='\0'; 
Tree->left=MakeTree (Expr, first, k-1); 

---

Tree->right=MakeTree (Expr, k+1, last); 
return Tree; 
} 
Agar son yoki o’zgaruvchi uchrasa, birinchi o’rinda uning uzunligini 
hisoblaymiz va k o’zgaruvchisiga yozamiz. 
Daraxt bo’yicha bunday ifodalarni hisoblash uchun CalcTree funktsiyasiga 
tugunning ma’lumotlar maydonida belgili satr yozilganligi uchun bir qancha 
o’zgartirishlar kiritishimiz kerak bo’ladi. Belgili satrni sonli ko’rinishga o’tkazish 
uchun atoi standart 
funktsiyasini 
qo’llaymiz 
(buning 
uchun 
djasturning 
sarlavhasiga stdlib.h kutubxonasini qo’shish kerak. 
int CalcTree(PNode Tree) { 
int num1, num2; 
if (!Tree->left) //agar avlodi mavjud bo’lmasa, 
return atoi(Tree->data); //songa aylantirish ...qolganlari o’zgarishsiz qoladi... 
} 
Bunday ifodalar o’zgaruvchi nomlarisiz berilgan bo’lsa, to’g’ridan-to’g’ri 
hisoblash mumkin. 
Daraxt yordamida ifodani soddalashtirish. Ba’zi bir ifodalarni quyidagi 
ayniyatlar yordamida soddalashtirish mumkin. Ixtiyoriy x uchun: 
0+x=x x+0=x 0*x=0 
0-x=-x x-0=x 1*x=x 
Faraz qilaylik, a) rasmda tasvirlangan ifoda berilgan bo’lsin. Birinchi amal 
natijasi a ga teng, shuning uchun quyidagilarni bajarish mumkin: p ko’rsatkichni a 
tugunga o’rnatish, qolgan ikkita keraksiz tugunni xotiradan o’chirib tashlash kerak. 
9-rasm. 

---

9-rasmdagi b) holat uchun mos ravishda p ko’rsatkichni 0 qiymatli tugunga o’rnatish 
kerak. Buning uchun ikkinchi (a qiymatli) tugunni o’chirib tashlashdan oldin uning 
avlodi bo’lishi mumkinligini e’tiborga olish kerak. Bu rekursiv ravishda bajariladi: 
void DeleteNode (PNode Tree) { 
if (Tree==NULL) return; 
DeleteNode(Tree->left); 
DeleteNode(Tree->right); 
delete Tree; 
} 
Bundan tashqari, qandaydir tugunning ikkala avlodi barg bo’lsa va sonli 
qiymatga ega bo’lsa, bunday ifodani hisoblash kerak, yoki xuddi shunday keraksiz 
ikkita tugunni o’chirish kerak. Bu amalni bajarishning bitta varianti quyida 
keltirilgan. Bu yerda agar tugun barg bo’lsa va sonni saqlab turgan bo’lsa 1 
qiymatini, aks holda 0 ni qaytaruvchi IsNumber funktsiyasi qo’llanilgan: 
int IsNumber (PNode Tree) { 
int i=0; 
if(!Tree) return 0; //bo’sh daraxt 
while (Tree->data[i]) //satr oxirigacha yetmagan 
if(!strchr(“0123456789”, Tree->data[i+1]) 
return 0; 
return 1; 
} 
Ifodani hisoblash protsedurasi quyidagicha bo’ladi: 
void Calculate (PNode Tree) 
{ 
int num1, num2, result=0; 
if (!Tree || //hisoblash mumkin bo’lmasa, chiqish 
!IsNumber(Tree->left) || 
!IsNumber(Tree->right) return; 

---

num1=atoi(Tree->left-data); //ma’lumotni olish 
num1=atoi(Tree->left-data); 
switch (Tree->data[0]) { //amallarni bajarish 
case ‘+’: result=num1+num2; break; 
case ‘–’: result=num1-num2; break; 
case ‘*’: result=num1*num2; break; 
case ‘/’: result=num1/num2; break; 
} 
delete Tree->left; //keraksiz qismdaraxtni o’chirish 
delete Tree->right; 
sprint (Tree->data, “%d”, result); 
Tree->left=NULL; 
Tree->right=NULL; 
}