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

6. Arifmetik ifodalarni daraxt yordamida yoyish 
Bu mavzuda kompyuter dasturlari arifmetik ifodalardagi amallar ketma-
ketligini qanday tartibda bajarishi mumkinligini o’rganamiz. Bulardan biri – 
arifmetik ifodalarni ikkilik daraxt ko’rinishida ifodalab olishdan iborat. Masalan, 
quyidagi ifoda berilgan bo’lsin: 
(a + b) / (c - d + 1) 

---

ushbu ifodaga mos ikkilik daraxt rasmda ko’rsatilgan. 
7-rasm. Arifmetik ifodaning daraxt yordamida yoyilishi 
Rasmga e’tibor bersak daraxt barglarida sonlar va o’zgaruvchilarning nomlari 
(operandlar) joylashgan, ichki tugunlar va ildizda esa, arfimetik amallar va 
funktsiyalarni chaqiruv joylashgan. Bunday ifodalarni hisoblash barglardan 
boshlanadi. Ko’rib turganimizdek, qavslar tugunlarga joylashtirilmagan, ikkilik 
daraxt amallarning bajarilish tartibini belgilab beradi. 
Arifmetik ifodalarni yozish shakllari. Endi bunday ikkilik daraxtni aylanib 
o’tish natijasida qanday natija olishimizni ko’rib chiqamiz. Daraxrtni eniga (kengligi 
bo’yicha) (ildiz – chap – o’ng) qoidasi bo’yicha o’qisak quyidagi natijani olamiz: 
/ + a b + - c d 1 
ya’ni arifmetik amal belgisi (ildiz)dagi o’zining operandlari bilan keladi. Arifmetik 
ifodalarni yozishning bunday shakli prefiksli deb ataladi. Daraxtni to’g’ri o’tish (chap 
– ildiz – o’ng) qoidasi bo’yicha o’qisak oddiy matematik ifodalashga (qavslarsiz) 
mos arifmetik ifodalarni yozishning infiksli shaklini beradi: 
a + b / c - d + 1 
qavslar bo’lmaganligi uchun infikli yozuv amallar bajarilishining to’g’ri tartibini 
tiklash imkoniyatini bermaydi. 
Deyarli barcha translyatorlarda postfiksli yozuv qo’llaniladi. Bu daraxtni 
o’tishning CHO’I (chap – o’ng – ildiz) qoidasiga asoslanadi. Bunda arifmetik amal 
belgilari operandlardan keyin keladi: 
a b + c d - 1 / 
bunday ifodalarni bir qiymatli aniqlash stek qo’llanilgan quyidagi algoritm asosida 
amalga oshiralidi: 
Postfiksli yozuvda elementlar tanlab olinmagan, 
1) Navbatdagi elementni olish; 
2) Agar bu operand bo’lsa (ya’ni, arifmetik amal bo’lmasa), uni stekka yozish; 

---

3) Agar bu arifmetik amal belgisi bo’lsa, u holda 
• Stekdan ikkinchi operandni olish; 
• Stekdan birinchi operandni olish; 
• Bu ma’lumotlar bilan arifmetik amalni bajarish va natijani stekka 
yozish. 
Postfiksli shakldagi yozuvni stek yordamida bajarishni quyidagi rasm 
yordamida tasvirlash mumkin a b + c d - 1 /. Yuqoridagi algoritmga asosan birinchi 
stekka a operandni, keyin b operandni yozamiz: 
8-rasm. Arifmetik amallarni bajarish sxemasi 
a+b amal natijasini yana qayta stekka yozamiz, va uning yuqorisidan navbatdagi 
operandlar c va d ni yozamiz (2-qadam). Keyingi amallar ham 3- va 4-qadamlarda 
ko’rsatilgan. Stek uchun oxirgi amal (bo’lish) 4-qadamdan keyin natijani beradi. 
Arifmetik amallar daraxtini qurish algoritmi. Bizga arifmetik ifoda berilgan 
bo’lsin. Ularning sintaktik ketma-ketligi bo’yicha yoyilmasi va arifmetik ifodalarni 
turli usullarda yozish uchun daraxt qurish talab qilingan bo’lsin. 
Masalaning yechimini eng oddiy usulda quyidagi talablar bo’yicha qarab 
chiqamiz. 
1. Arifmetik ifodada faqat butun sonli qiymatli natija beruvchi amal belgilari 
qatshishish mumkin: + - * /. 
2. Funktsiyani chaqirish qo’llanilganda qavslar, manfiy va musbat sonlarni 
ifodalovchi (qo’shish va ayirish) belgilaridan foydalanish taqiqlanadi (masalan, -a+5 
yozuvi taqiqlanadi, uning o’rniga 0-a+5 kabi yozish kerak). 
3. Ifoda to’g’ri yozilgan deb taxmin qilib, uning to’g’riligini tekshirish shart 
emas. 
Biz 
bilamizki, 
ifodalarda 
arifmetik 
amallarni 
bajarilish 
tartibi 
amallarning ustunlik darajasi bilan aniqlanadi – birinchi navbatda eng yuqori 
ustunlikka ega bo’lgan amallar bajariladi. Masalan, ko’paytirish va bo’lish, qo’shish 
va ayrish amallaridan oldin bajariladi. 

---

Arifmetik 
ifodalarning 
to’g’ri 
yozilishini N uzunlikdagi 
belgili 
satri Expr ko’rinishida yozib olamiz. Massiv elementlari uchun first dan last gacha 
(to’liq daraxt massivda bu algoritmni qo’llash imkonini beradi, ya’ni first=0 va 
last=N-1 bo’lganda) daraxt quramiz. Daraxt qurish algoritmining so’zlar orqali 
ifodasi quyidagicha bo’ladi: 
1. Agar first=last (bitta element mavjud – o’zgaruvchi yoki son), u holda 
yangi tugun hosil qiling va unga ushbu elementni yozing. Aks holda... 
2. first dan last gacha (last ham kiradi) eng kichik usutnlikka ega bo’lgan 
(oxirida bajariladigan) amalni toping (masalan, topilgan elementning tartib 
raqami k bo’lsin). 
3. Yangi (ildiz) tugunni hosil qilineg va unga Expr[k]amal belgisini yozing. 
4. Ushbu algoritmni rekursiv ravishda ikki marta qo’llang: 
• ifodani 
massiv 
elementlaridan first dan k-1 gacha tartib 
raqamli 
elementlar ichidan ajratib olib chap qismdaraxtni quring, 
• ifodani massiv elementlaridan k+1 dan last gacha tartib raqamli 
elementlari ichidan ajratib olib, o’ng qismdaraxtni quring 
Shunday daraxt tugunini tavsiflovchi tuzilmani e’lon qilamiz. Tuzilmani e’lon 
qilishda birqiymatli butun son va arifmetik amal belgilaridan foydalanamiz, tuguning 
ma’lumotlar maydoni bitta belgini saqlashi mumkin. 
struct Node { 
char data; 
Node *left, *right; 
}; 
typedef Node *PNode; 
Endi amallar ustunligini qaytaruvchi funktsiyani aniqlab olamiz. Qo’shish va 
ayrish amallari uchun 1 ni, ko’paytirish va bo’lish amallari uchun esa 2 ni ustunlik 
darajasi sifatida kiritish mumkin. 
int Priority (char c) { 
switch (c) { 
case '+': case '-': return 1; case ’*’: case '/': return 2; 
} 

---

return 100; //tanlangan belgi arifmetik amal emas 
} 
Quyida talab qilingan daraxtni qurish protsedurasi keltirilgan, bu funktsiya 
xotirada qurilgan daraxt adresini qaytarish uchun qo’llaniladi. Joriy amal ustunligini 
oldingi minimal ustunlikka ega bo’lgan amal bilan taqqoslash uchun <= belgisi 
qo’llanilganligiga e’tibor bering. Buning hisobiga minimal ustunlikdagi eng oxirida 
bajariladigan amalni qidiramiz, ya’ni topilgan amal eng oxirida bajarilishi kerak. 
Agar biz < belgisidan foydalansak, u holda birinchi bajariladigan eng kichik 
ustunlikdagi amalni aniqlagan bo’lar edik va daraxt noto’g’ri qurilgan bo’lar edi 
(ya’ni hisoblash natijasida notg’o’ri yechimni olamiz). 
PNode MakeTree (char Expr[], int first, int last) { 
int MinPrt, i, k, prt; 
PNode Tree = new Node; 
if (first == last) { 
Tree->data = Expr[first]; 
Tree->left = NULL; 
Tree->right = NULL; return Tree; 
} 
MinPrt = 100; 
for (i = first; i <= last; i++) { 
prt = Priority (Expr[i]); 
if (prt <= MinPrt) { 
MinPrt = prt; 
k = i; 
} 
} 
Tree->data = Expr[k]; 
Tree->left = MakeTree (Expr, first, k-1); 
Tree->right=MakeTree (Expr,k+1,last); 

---

return Tree; 
} 
Endi ushbu daraxtni aylanib o’tish natijasida arifmetik ifodaga mos turli 
shakllar taqdim etishni ko’rib chiqamiz. 
Daraxt asosida ifodani hisoblash. Qandaydir arifmetik ifoda uchun daraxt 
qurilgan va uning Tree adresi ma’lum bo’lsin. Ushbu ifodaning natijasi bo’lgan butun 
sonni qaytaruvchi funktsiyani yozamiz. Alohida e’tiborga olish kerakki, bo’lish butun 
qiymat beradi (qoldiqni tashlab yuboramiz). 
int CalcTree (PNode Tree) { 
int num1, num2; 
if (!Tree->left) //agar avlod mavjud bo’lmasa 
return Tree -> data – ‘0’; //sonni qaytarish 
num1=CalcTree(Tree->left); //qismdaraxtni hisoblash 
num2 = CalcTree(Tree->right); 
switch (Tree->data) { //amallarni bajarish 
case ‘+’: return num1+num2; 
case ‘–’: return num1-num2; 
case ‘*’: return num1*num2; 
case ‘/’: return num1/num2; 
} 
return 32767; //noma’lum amal, xatolik! 
} 
Agar daraxtda avlod mavjud bo’lmas, u holda bu tugunda son joylashgan 
bo’ladi. Butun sonli qiymat olish uchun bu raqam kodiga ’0’kodi qo’yiladi. Agar 
avlod mavjud bo’lsa, u holda chap va o’ng qismdaraxtlarda hisoblash amallari 
(rekursiv) va daraxt ildizidagi amal bajariladi. Ushbu funktsiya qo’llanilgan asosiy 
dastur quyida keltirilgan. 
void main() { 
char s[80]; 
PNode Tree; 

---

Printf(“ifodani kiriting > “); 
gets(s); 
Tree=MakeTree(s, 0, strlen(s)-1); 
Printf(“=%d\n”, CalcTree(Tree)); 
} 
Qavsli ifodalarni yoyish. Endi masalani biroz murakkablashtiramiz, ya’ni 
qavsning birorta turi (masalan, aylana qavs) uchragan ifodalardan foydalanamiz. 
Bunday hollarda kichik ustunlikdagi amallarni berilgan oraliqdan qidirishda qavsdagi 
ifodaga diqqatni qaratish shart emas. Masalan, quyidagi ifoda berilgan bo’lsin: