पाठ पार्स एक पेड़ डेटा संरचना

Question

चलो कहते हैं कि मैं एक फ़ाइल से एक लाइन पढ़ रहा हूँ चलो बनाने के लिए:

{Parent{{ChildA}{ChildB}}} 

अधिक जटिल उदाहरण:

{Parent{{ChildA{ChildC}{ChildD}}{ChildB{ChildE}{ChildF}}}} 

कौन सा एक पेड़ के निर्माण के लिए प्रयोग किया जाता है व्याकरण ।

{} ब्रैकेट के अंदर कोई भी नाम एक नोड है, और यदि उस ब्रैकेट के भीतर अन्य नोड्स (ब्रैकेट) हैं, तो वे नोड बच्चे हैं।

मैं काउंटर का उपयोग करके पहले विशिष्ट उदाहरण को पार्स करने में सक्षम हूं, लेकिन केवल नोड्स के टेक्स्ट नामों को ढूंढने में सक्षम हूं। मैं इसे कैसे पार्स कर सकता हूं ताकि मैं यह निर्धारित कर सकूं कि नोड्स एक दूसरे के बच्चे कौन हैं? मैं अपने दिमाग को उस कोड के चारों ओर लपेट नहीं सकता जो मैं उपयोग करूंगा। मुझे लगता है कि मैं रिकर्सन का उपयोग करूंगा।

कोई भी मदद या सलाह की सराहना की जाएगी।

सी ++ को प्राथमिकता दी जाती है।

बहुत बहुत धन्यवाद।

Answer 1

एक जवाब तुम वैसे भी उपयोग नहीं कर सकते अगर यह होमवर्क के साथ मज़ा बिगाड़ कोड :)

---

यह प्रिंट होगा:

{ 
    Parent 
    { 
     { 
      ChildA 
      { 
       ChildC 
      } 
      { 
       ChildD 
      } 
     } 
     { 
      ChildB 
      { 
       ChildE 
      } 
      { 
       ChildF 
      } 
     } 
    } 
} 

_{यहाँ dump(const ast_t&) की परिभाषा है:}

struct dump_visitor : boost::static_visitor<> 
{ 
    dump_visitor(int indent=0) : _indent(indent) {} 

    void operator()(const std::string& s) const { print(s); } 

    template <class V> 
     void operator()(const V& vec) const 
    { 
     print("{"); 
     for(typename V::const_iterator it=vec.begin(); it!=vec.end(); it++) 
      boost::apply_visitor(dump_visitor(_indent+1), *it); 
     print("}"); 
    } 

    private: 
    template <typename T> void print(const T& v) const 
     { std::cout << std::string(_indent*4, ' ') << v << std::endl; } 
    int _indent; 
}; 

void dump(const ast_t& tree) 
{ 
    boost::apply_visitor(dump_visitor(), tree); 
} 

Answer 2

चूंकि यह होमवर्क है, तो मुझे लगता है कि आपको हाथ से समाधान लागू करना होगा, इसलिए आप इनपुट को पार्स करते समय डेटा को पकड़ने के लिए शायद स्टैक का उपयोग करना चाहेंगे।

प्रत्येक बार जब आप { देखते हैं तो आप इसके बाद वाले डेटा के साथ एक नया नोड बनाते हैं, और इसे स्टैक पर दबाते हैं।

प्रत्येक बार जब आप } देखते हैं तो आप स्टैक से अंतिम नोड पॉप करते हैं, और इसे अपने पेड़ के आकार में जोड़ते हैं।

इस दृष्टिकोण के लिए आपको जिस चीज की आवश्यकता होगी वह एक नोड पॉइंटर है, हम इसे currentNode कहते हैं, ताकि हम वास्तविक पदानुक्रम हो सकें। आरंभ करने के लिए, currentNode शून्य होगा; पहली बार एक नोड स्टैक से पॉप हो गया है, तो आप उस नोड को currentNode में डाल दें। अन्यथा, जब आप एक मूल्य पॉप करते हैं, तो हम जानते हैं कि हमारे पास अगले नोड के दोनों बच्चे हैं जो ढेर पर हैं।

मैं आपको वहां से इसके साथ दौड़ने दूँगा, लेकिन यदि आपको और अधिक चाहिए तो मैं खड़ा रहूंगा।

Answer 3

आपको वर्तमान घोंसले का ट्रैक रखना होगा। इसके लिए आप एक ढेर का उपयोग कर सकते हैं।

प्रत्येक बार, आपको { (नोड नाम के बाद) का सामना करना पड़ता है, आप जानते हैं कि यह एक नए नोड की शुरुआत है। यह नया नोड वर्तमान नोड का बच्चा है।

प्रत्येक बार जब आप } पर आते हैं, तो आप जानते हैं कि वर्तमान नोड अब समाप्त हो गया है, जिसका अर्थ है कि आपको अपने प्रोग्राम को यह बताना होगा कि वर्तमान नोड अब वर्तमान नोड के पैरेंट में बदल गया है।

उदाहरण:

{A{B{C}{D}{E}}{F{G}{H}}} Stack: 
^ 

{A{B{C}{D}{E}}{F{G}{H}}} Stack: A // A is root 
^ 

{A{B{C}{D}{E}}{F{G}{H}}} Stack: A, B // B is child of A 
^

{A{B{C}{D}{E}}{F{G}{H}}} Stack: A, B, C // C is child of B 
    ^

{A{B{C}{D}{E}}{F{G}{H}}} Stack: A, B, // C has no child, C done 
    ^

{A{B{C}{D}{E}}{F{G}{H}}} Stack: A, B, D // D is child of B 
     ^

{A{B{C}{D}{E}}{F{G}{H}}} Stack: A, B, 
     ^

{A{B{C}{D}{E}}{F{G}{H}}} Stack: A, B, E // E child of B 
     ^

{A{B{C}{D}{E}}{F{G}{H}}} Stack: A, B, 
      ^

{A{B{C}{D}{E}}{F{G}{H}}} Stack: A, // B has no more children, B done 
      ^

{A{B{C}{D}{E}}{F{G}{H}}} Stack: A, F // F child of A 
      ^

{A{B{C}{D}{E}}{F{G}{H}}} Stack: A, F, G // G child of F 
       ^

{A{B{C}{D}{E}}{F{G}{H}}} Stack: A, F, 
       ^

{A{B{C}{D}{E}}{F{G}{H}}} Stack: A, F, H 
        ^

{A{B{C}{D}{E}}{F{G}{H}}} Stack: A, F, 
        ^

{A{B{C}{D}{E}}{F{G}{H}}} Stack: A, 
        ^

{A{B{C}{D}{E}}{F{G}{H}}} Stack: 
        ^

DONE. 

Answer 4

कल्पना कीजिए इस कुछ इस तरह होना करने के लिए (भले ही यह फ़ाइल है कि आप से पढ़ रहे हैं से रेखीय है, बस इसे इस तरह से दृश्यमान करने की कोशिश)

{ 
Parent 
    { 
    { 
    ChildA 
     { 
     ChildC 
     } 
     { 
     ChildD 
     } 
    } 
    { 
     ChildB 
     { 
     ChildE 
     } 
     { 
     ChildF 
     } 
    } 
    } 
} 

तो अब यह और अधिक दिखाई देता है कि जब भी आपको अपना '{' मिलता है तो आपका बच्चा होता है।तो अंधे जाओ और जब भी आपको एक बच्चा पैदा होता है (रिकर्सली लेकिन यदि आप जिस लाइन से पढ़ रहे हैं वह बहुत लंबा है तो मैं सुझाव दूंगा कि आप पुनरावृत्ति से जाएं) और जब भी आप '}' को एक स्तर ऊपर ले जाते हैं (अभिभावक को)।

मुझे लगता है कि आप पेड़ पर नोड जोड़ने और अपने पेड़ को एक स्तर तक ले जाने के लिए एक समारोह करेंगे। यदि आपके पास यह सब कुछ है तो आपको केवल टुकड़ों को एक साथ रखना होगा।

मुझे उम्मीद है कि यह कुछ समझ में आता है।

Answer 5

आपके पास व्याकरण अपेक्षाकृत सरल है।

अपने उदाहरण नोड्स दो अलग अलग तरीकों में से एक में घोषित किया जा सकता है के आधार पर:

{nodename} 

जो साधारण एक और

{nodename{childnodes}} 

जो परिसर में एक

अब है इसे अधिक औपचारिक व्याकरण में बदलने के लिए हम पहले घटक भागों के बारे में लिखते हैं:

"{" nodename "}" 
"{" nodename "{" childnodes "}" "}" 

फिर हम व्याकरण (गैर टर्मिनलों बड़े रहेंगे) को परिभाषित कर सकते

नोड :: = "{" nodename "}" | "{" nodename "{" childNodes "}" nodename :: = कम से कम एक पत्र childNodes :: = एक या अधिक नोड

मानक तरीका एक पार्सर में से चालू करने के लिए (आप यह सोचते हैं कि यह लिखने के लिए हाथ से, जो आप ठीक से करेंगे क्योंकि यह बहुत छोटा है) एक ऐसी विधि लिखना है जो प्रत्येक गैर टर्मिनलों को पार्स कर सके (जो आप: == चिह्न के बाईं ओर देखते हैं)।

एकमात्र कांटेदार मुद्दा यह है कि आपको "{" (जिस स्थिति में नोड का बच्चा है) या "}" है (जिस स्थिति में उसके पास कोई नहीं है) को जांचने के लिए आपको नोडनाम फ़ंक्शन लिखना है बच्चे) नोड नाम के अंत के बाद।

इसके अलावा मैंने नोडनाम के रूप में सभी संभावित एसीआई तारों को लिखने की स्वतंत्रता ली।

बूस्ट आत्मा क्यूई के साथ एक न्यूनतम कार्यान्वयन:

#include <boost/spirit/include/qi.hpp> 
namespace qi = boost::spirit::qi; 

typedef boost::make_recursive_variant< 
    std::vector<boost::recursive_variant_>, 
    std::string>::type ast_t; 

void dump(const ast_t&); 

// adhoc parser rule: 
static const qi::rule<std::string::iterator, ast_t()> node = 
    '{' >> *node >> '}' | +~qi::char_("{}"); 

int main() 
{ 
    std::string input = "{Parent{{ChildA{ChildC}{ChildD}}{ChildB{ChildE}{ChildF}}}}"; 
    std::string::iterator f(input.begin()), l(input.end()); 

    ast_t tree; 
    if (qi::parse(f, l, node, tree)) 
     dump(tree); 
    else 
     std::cerr << "Unparsed: " << std::string(f, l) << std::endl; 
} 

dump के कार्यान्वयन खेद लगभग के बराबर राशि है

Answer 6

हर बार जब आप पाते हैं "{" तो फिर हर बार जब आप पाते हैं माता-पिता के लिए बच्चे को जोड़ने "}" वर्तमान सेट पेड़ पैरेंट पेड़ होने के लिए।

public class Tree 
    { 
     public Tree Parent { get; set; } 
     public string Value { get; set; } 
     public List<Tree> Children { get; set; } 
    } 

    public Tree Parsing() 
    { 
     string rawString = this._rawData; 
     Tree parent = new Tree { Parent = null,Value = "",Children = new List<Tree>()}; 
     Tree child = parent; 

     foreach (char c in rawString) 
      { 
      if (c == '{') 
      { 
       child = new Tree { Parent = child, Value = string.Empty, Children = new List<Tree>() }; 
       child.Parent.Children.Add(child); 
      } 
      else if (c == '}') 
      { 
       child = new Tree { Parent = child.Parent.Parent, Value = string.Empty, Children = new List<Tree>() }; 
       if (child.Parent != null) 
       { 
        child.Parent.Children.Add(child); 
       } 
       } 
      else 
      { 
        child.Value += c; 
      } 
     } 

      return parent; 
} 

public void RenderTree(Tree tree, string level) 
{ 
    if (tree.Value.Length > 0) 
     Console.WriteLine(level + tree.Value); 

    foreach (Tree t in tree.Children) 
    { 
     RenderTree(t, level + " "); 
    } 
}