Umumiy ma'lumot

Daraxt tuzilishini qurish

Ushbu bo'limda biz taklif qilingan algoritm doirasida ob'ektlar "daraxti" ni shakllantirish ketma -ketligini batafsil tahlil qilamiz.

Keling, "daraxt" ning dastlabki uchta ob'ektini, shu jumladan ildiz ob'ektini va uning ikkita "vorislarini" qurish tartibini ko'rib chiqaylik. Kirish joyida butun arifmetik ifodaning ajralmas leksemalari majmuasini olgan holda, biz undan "burilish" nuqtasini topamiz. Eslatib o'taman, bu har doim operator (arifmetik operatsiya). Topilgan "burilish nuqtasi" ning qiymati strukturaning yuqori qismidagi ob'ekt sinfini aniq aniqlash imkonini beradi. Keyinchalik, biz yuqorida aytib o'tilganidek, tokenlar qatorini ikki qismga ajratamiz. Har ikkala qismda biz chap va o'ng "merosxo'rlar" ob'ektlarining sinfini ko'rsatadigan "burilish nuqtalarini" topamiz. Endi siz uchta ob'ektni shakllantira olasiz va ular orasidagi aloqalarni ko'rsatasiz. Nihoyat, ob'ektlar keyingi manipulyatsiya qilish uchun arNode qatoriga joylashtiriladi.

Bizning kiritish ifodamiz uchun: (x + 10.2) ^ 2 + 5 * y-z, ta'riflangan protsedura quyidagicha. Burilish nuqtasi ta'rifi ikkita operatorni o'z ichiga oladi: "+" ("2" va "5" raqamlari orasida) va "-". Biz ro'yxatdagi oxirgi operatorni tanlaymiz: "-". Bu operatorning qiymati ildiz ob'ektining kerakli sinfini va uning nomini tanlash imkonini beradi. Xususan, Minus1 nomli Minus sinfining ob'ekti hosil bo'ladi. Asl tokenlar massivini ikki qismga bo'lgandan so'ng, biz ikkita elementlar massivini olamiz: (x + 10.2) ^ 2 + 5 * y va z. Birinchi belgi uchun burilish nuqtasi "+", ikkinchisi faqat bitta z elementidan iborat. Bu shuni anglatadiki, Plus1 va Constant1 nomli Plus va Constant sinflari moslamalari ildiz ob'ektining "avlodlari" sifatida shakllanishi kerak. Daraxt tuzilishini shakllantirish va ob'ektlarni arNode qatoriga qo'shish uchun yangi yaratilgan ob'ektlar maydonlarini to'ldirish qoladi: childrenLeft, childrenRight va ota.

"Daraxt" ning keyingi shakllanishi birinchi uchlikni yaratish tartibiga juda o'xshaydi, lekin uning o'ziga xos nozikliklari bor. ArNode majmuasida, faqat elementlar elementlarini takrorlash orqali, biz qatorda bir nechta elementni o'z ichiga olgan lec maydoniga ega ob'ektni qidiramiz va shu bilan birga childrenLeft va childrenRight bo'sh maydonlari bilan. Biz tanlangan ob'ektdan lec maydonining qiymatini o'qiymiz, uni "burilish" nuqtasida ikki qismga ajratamiz. Keyinchalik, biz hosil bo'lgan ikkala qismdan ham "burilish nuqtalarini" topamiz va yuqorida ko'rsatilgan mantiqqa muvofiq tanlangan ob'ekt uchun ikkita meros qilib olingan ob'ektni hosil qilamiz. Ob'ektlar o'rtasida aloqa o'rnatishni va ob'ektlarni arNode qatoriga qo'shishni unutmang.

Daraxt tuzilishi ob'ektlarining hech biri belgilangan shartlarga javob bermaguncha, biz belgilangan harakatlar ketma -ketligini takrorlaymiz. Endi biz kiritish ifodamiz uchun daraxt qurilgan va qiymatlarni hisoblashga tayyor deb taxmin qilishimiz mumkin.