सी ++ एन-आरी पेड़ कार्यान्वयन रिकर्सिव वंश पार्सिंग

Question

में उपयोग के लिए कार्यान्वयन के लिए मैं अभी भी सी ++ के लिए थोड़ा नया हूं इसलिए मेरे साथ भालू। मैं एक बीएनएफ व्याकरण द्वारा वर्णित कोर नामक एक कल्पित भाषा के लिए एक दुभाषिया लागू कर रहा हूं। अब तक मैंने एक टोकननाइज़र लागू किया है जो मुझे कोर प्रोग्राम का प्रतिनिधित्व करने वाले टोकन की एक अच्छी कतार देता है। अब मैं पार्सर/एक्सेक्यूटर लिखने की प्रक्रिया में हूं जो टोकननाइज़र से आउटपुट लेता है और रिकर्सिव वंश पार्सिंग का उपयोग करके पारसी ट्री क्लास (जिसे मुझे डिजाइन करना है) के ऑब्जेक्ट को पॉप्युलेट करने के लिए इसका उपयोग करता है। मैं इसे कैसे करना है इसके बुनियादी सिद्धांतों को समझता हूं लेकिन पारसीट्री कक्षा को लागू करने में परेशानी हो रही है। कोर बीएनएफ द्वारा वर्णित प्रोडक्शंस में आमतौर पर 2-5 टर्मिनल/गैर-टर्मिनल प्रतीकों होते हैं लेकिन कुछ में 20 तक हो सकते हैं इसलिए मुझे एक एन-आरी पेड़ की आवश्यकता होती है जहां प्रत्येक नोड में बच्चों की एक अलग संख्या हो सकती है।

मुझे लगता है कि पारसीट्री कक्षा को इसके कार्यान्वयन के लिए एक पेड़ का उपयोग करने की आवश्यकता नहीं है, लेकिन ऐसा लगता है कि यह सबसे अधिक समझ में आता है (क्या कोई अलग डेटा संरचना है जो बेहतर/आसान हो सकती है?)। मैं एसटीएल में किसी भी कंटेनर से अवगत नहीं हूं जो मुझे आवश्यकतानुसार बिल फिट बैठता है। मैंने बूस्ट संपत्ति के पेड़ को देखा है लेकिन मैं जो कह सकता हूं उससे वह काम नहीं करेगा। मैं पहिया को फिर से शुरू नहीं करना चाहता हूं और यदि संभव हो तो खरोंच से पेड़ को लागू करना पसंद नहीं करता। इसके अलावा, मैं बूस्ट से अलग बाहरी पुस्तकालयों का उपयोग करने में सक्षम नहीं होने के कारण सीमित हूं। मेरे पारसी ट्री को लागू करने का सबसे अच्छा तरीका क्या है? क्या कोई अच्छा प्री-पेड़ वृक्ष कार्यान्वयन मैं उपयोग कर सकता हूं?

Answer 1

मैं पार्स पेड़ का प्रतिनिधित्व करने के लिए 'बाएं बच्चे, दाएं भाई' बाइनरी पेड़ का उपयोग करने का सुझाव देता हूं। यह एक एन-आरी पेड़ का प्रतिस्थापन है। किसी भी एन-आरी पेड़ को 'पहला बच्चा, अगले भाई' बिनरी पेड़ का उपयोग करके दर्शाया जा सकता है।

अवधारणा इस प्रकार है: अगर एक तीन बच्चे हैं: बी, सी और डी और सी 2 बच्चों के ई और एफ के रूप में

   A 
      /| \ 
      B C D 
       /\ 
      E F 

इस

   A 
      /
      B 
       \ 
       C 
      /\ 
      E D 
       \ 
       F 

के रूप में प्रतिनिधित्व किया जा सकता है इस प्रकार है

यानी बच्चे हमेशा बाएं नोड और भाई बहनों को सही नोड पर जाते हैं। यह भी बनाना आसान है और इस पेड़ का प्री-ऑर्डर ट्रैवर्सल एन-आरी पेड़ के प्री-ऑर्डर ट्रैवर्सल जैसा ही है।

n-ary पेड़: प्री-ऑर्डर ट्रेवर्सल:

display (node, level) { 
    if (!node) return; 
    print node; 
    display (node->left, level+1); 
    display (node->right, level+1); 
} 

बच्चा सहोदर द्विआधारी पेड़: प्री-ऑर्डर travesal

display (node, level) { 
    if (!node) return; 
    print node; 
    display (node->left, level+1); 
    display (node->right, level); 
} 

इस पेड़ का निर्माण करने के लिए:

1. Throw your terminals and non-terminals in a Stack. 
2. When you want to combine n nodes under parent node 'p', pop 'n' elements from stack, making the last pop as the right child of the current pop. 
3. Finally make the nth pop the left child of node 'p'.