Phân tích văn bản để Thực hiện một cấu trúc cây dữ liệu

Question

Hãy nói rằng tôi đang đọc một dòng từ một tập tin:

{Parent{{ChildA}{ChildB}}} 

More phức tạp ví dụ:

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

Đó là ngữ pháp sử dụng để xây dựng một cây .

Bất kỳ tên nào trong ngoặc đơn {} là một nút và nếu trong khung đó có các nút (dấu ngoặc) khác, các nút đó là con.

Tôi có thể phân tích ví dụ cụ thể đầu tiên bằng bộ đếm, nhưng chỉ để tìm tên văn bản của các nút. Làm thế nào tôi có thể phân tích cú pháp này để tôi có thể xác định các nút nào là con của nhau? Tôi dường như không thể bao bọc tâm trí của mình xung quanh mã tôi sẽ sử dụng. Tôi có cảm giác tôi sẽ sử dụng đệ quy.

Bất kỳ trợ giúp hoặc lời khuyên nào sẽ được đánh giá cao.

C++ được ưu tiên.

Cảm ơn bạn rất nhiều.

Answer 1

làm hư những niềm vui với một câu trả lời bạn không thể sử dụng anyway nếu đó là bài tập về nhà:

Một thực hiện tối thiểu với Boost Thần Qi:

#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; 
} 

Việc thực hiện dump là đáng tiếc hầu hết số tiền tương đương của code :)

---

Nó sẽ in:

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

_{Dưới đây là định nghĩa của 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

Vì đó là bài tập về nhà, tôi cho rằng bạn phải thực hiện giải pháp bằng tay, vì vậy bạn có thể muốn sử dụng ngăn xếp để giữ dữ liệu trong khi phân tích cú pháp đầu vào.

Mỗi khi bạn nhìn thấy một { bạn tạo một nút mới có dữ liệu theo sau nó và đẩy nó vào ngăn xếp.

Mỗi khi bạn nhìn thấy một } bạn bật nút cuối cùng khỏi ngăn xếp và thêm nó vào hình dạng cây của bạn.

Điều khác bạn cần cho phương pháp này là con trỏ Nút, chúng tôi sẽ gọi nó là currentNode, để chúng tôi có thể thực hiện phân cấp thực tế. Để bắt đầu, currentNode sẽ là rỗng; lần đầu tiên một nút được bật ra khỏi ngăn xếp, bạn đặt nút đó vào currentNode. Nếu không, khi bạn bật một giá trị, chúng tôi biết chúng tôi có cả hai con của nút tiếp theo trên ngăn xếp.

Tôi sẽ cho phép bạn chạy với nó từ đó, nhưng nếu bạn cần nhiều hơn, tôi sẽ đứng bên cạnh.

Answer 3

Bạn sẽ phải theo dõi việc lồng hiện tại. Đối với điều này, bạn có thể sử dụng một ngăn xếp.

Mỗi lần, bạn gặp một số { (theo sau là tên nút), bạn biết rằng đây là khởi đầu của một nút mới. Nút mới này là một nút con của nút hiện tại.

Mỗi khi bạn đi qua }, bạn biết rằng nút hiện tại đã kết thúc ngay bây giờ, nghĩa là bạn phải thông báo cho chương trình biết rằng nút hiện tại đã được thay đổi thành nút gốc của nút hiện tại.

Ví dụ:

{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

Hãy tưởng tượng điều này là một cái gì đó như thế này (Mặc dù nó là tuyến tính từ các tập tin mà bạn đang đọc từ, chỉ cần thử hình dung nó theo cách này)

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

Vì vậy, bây giờ nó có thể nhìn thấy nhiều hơn bất cứ khi nào bạn nhận được '{' bạn có một đứa trẻ.Vì vậy, đi mù và bất cứ khi nào bạn nhận được một '{' đẻ trứng một đứa trẻ (đệ quy nhưng nếu dòng mà bạn đang đọc từ quá dài thì tôi sẽ đề nghị bạn đi bằng cách lặp lại) và bất cứ khi nào bạn gặp một '}' di chuyển một cấp lên (cho phụ huynh).

Tôi cho rằng bạn sẽ có một chức năng để thêm nút vào cây và di chuyển lên cây của bạn một cấp. Nếu đó là tất cả các bạn có thì tất cả các bạn cần làm là chỉ cần đặt các mảnh với nhau.

Tôi hy vọng điều này có ý nghĩa gì đó.

Answer 5

Ngữ pháp bạn có là tương đối đơn giản.

Dựa trên ví dụ của bạn các nút có thể được khai báo theo một trong hai cách khác nhau:

{nodename} 

đó là một đơn giản và

{nodename{childnodes}} 

đó là phức tạp một

Bây giờ để biến điều này thành ngữ pháp chính thức hơn, trước tiên chúng tôi viết các phần cấu thành:

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

Sau đó, chúng tôi có thể xác định ngữ pháp (các thiết bị đầu cuối không được viết hoa)

Nút :: = "{" Nodename "}" | "{" nodename "{" childNodes "}" nodename :: = ít nhất một lá thư childNodes :: = một hoặc Node hơn

Cách thông thường để biến hơn vào một phân tích cú pháp (giả sử bạn đã viết nó bằng tay, mà bạn sẽ đúng bởi vì nó quá nhỏ) là viết một phương thức có thể phân tích cú pháp của mỗi thiết bị đầu cuối không (những gì bạn thấy ở bên trái của dấu = =).

Vấn đề gai góc duy nhất là bạn phải viết hàm Nodename để kiểm tra xem có "{" (trong trường hợp này nút có con) hoặc "}" (trong trường hợp này nó không có con) sau khi kết thúc tên nút.

Ngoài ra, tôi đã tự do không viết ra tất cả các chuỗi ascii có thể là Nodename.

Answer 6

Mỗi lần bạn tìm thấy "{" sau đó thêm con cho phụ huynh sau đó mỗi lần bạn tìm thấy "}" thiết lập hiện tại cây là cây bố mẹ.

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 + " "); 
    } 
}