उपग्रह

निर्देश

कल्पना कीजिए कि आपको एक बाइनरी ट्री अल्फा सेंटॉरी की ओर बढ़ते एक सैटेलाइट तक भेजना है, और आपके पास बैंडविड्थ सीमित है। चूँकि इस ट्री में कोई चीज़ दोहराई नहीं जाती, इसलिए इसे उसके प्री-ऑर्डर और इन-ऑर्डर ट्रैवर्सल से अद्वितीय रूप से दर्शाया जा सकता है।

सैटेलाइट के लिए ऐसा सॉफ्टवेयर लिखिए जो इन ट्रैवर्सल से ट्री फिर से बना सके।

प्री-ऑर्डर ट्रैवर्सल में सबसे पहले मौजूदा नोड की वैल्यू पढ़ी जाती है, इसीलिए इसके नाम में "pre" है। इसके बाद बाएँ सबट्री को प्री-ऑर्डर में पढ़ा जाता है, और फिर दाएँ सबट्री को भी प्री-ऑर्डर में पढ़ा जाता है।

इन-ऑर्डर ट्रैवर्सल पहले बाएँ सबट्री को इन-ऑर्डर में पढ़ता है, फिर मौजूदा नोड को, और अंत में दाएँ सबट्री को इन-ऑर्डर में पढ़ता है। यानी बाएँ से दाएँ के क्रम में।

उदाहरण के लिए, इस ट्री का प्री-ऑर्डर ट्रैवर्सल [a, i, x, f, r] है। इस ट्री का इन-ऑर्डर ट्रैवर्सल [i, a, f, x, r] है।

  a
 / \
i   x
   / \
  f   r

ध्यान दीजिए: प्री-ऑर्डर ट्रैवर्सल में सबसे पहला एलिमेंट हमेशा रूट होता है।

यह अभ्यास आपको डेफिनिट क्लॉज़ ग्रामर (DCG) की मदद से हल करना है। DCG का उपयोग सिर्फ सीक्वेंस (ऐरे) पार्स करने के लिए ही नहीं, बल्कि उन्हें बनाने, पूरा करने और जाँचने के लिए भी किया जा सकता है।

लाइब्रेरी

स्टब इम्प्लीमेंटेशन फाइलों में यह लाइन शामिल है:

:- use_module(library(dcg/basics)).

इससे dcg/basics लाइब्रेरी इस्तेमाल की जा सकती है। इस अभ्यास को हल करने के लिए यह काफी होनी चाहिए।

संसाधन

Prolog में DCG से शुरुआत करने के लिए ये संसाधन उपयोगी हैं:

• metalevel.at
• wikipedia
• swipl