Drucken von Trie

Question

Ich habe einen Trie in C++ erstellt, um Wörter von Sätzen zu halten. Jeder Satz hat eine Gewichtung, die die Reihenfolge bestimmt, in der sie ausgegeben werden sollen. Ich habe mehrere rekursive Funktionen, die andere rekursive Funktionen aufrufen, und das Dilemma, mit dem ich konfrontiert bin, ist, dass ich meine Liste nur einmal ausdrucken möchte.

Im Grunde ruft meine get-Funktion die Funktion printFromNode auf, die den Vektor der Paare p erzeugt, die ich sortieren und drucken möchte. Wenn mir jemand in die richtige Richtung zeigen könnte, wäre das sehr zu begrüßen.

Code: Trie.cpp:

//#include "Trie.h" 
#include <iostream> 
#include <cstdlib> 
#include <cstring> 
#include <string> 
#include <vector> 
#include <sstream> 
#include <stack> 



using namespace std; 


class Node 
{ 
private: 
    string word = ""; 
    bool endOfSentence = false; 
    int weight = -1; 


public: 

    vector<Node> children = {}; 

    Node() { 
     this->setWord(""); 
    } 

    Node(string s){ 
     this->setWord(s); 
    } 

    string getWord(){ 
     return this->word; 
    } 

    void setWord(string s) { 
     this->word = s; 
    } 

    void setEOS(){ 
     this->endOfSentence = true; 
    } 

    void setWeight(int weight){ 
     this->weight = weight; 
    } 

    int getWeight() { 
     return this->weight; 
    } 
}; 


class Trie 
{ 
public: 
    Node root; 

    void add(vector<string> phrase, int weight, Node* n){ 
     Node* current = n; 
     int w = weight; 
     int found = -1; 

     for (int i = 0; i < current->children.size(); i++) { 
      if (phrase[0] == current->children[i].getWord()) { 
       found = i; 
      } 
     } 
     if (found > -1) { 
      current = &current->children[found]; 
      phrase.erase(phrase.begin()); 
      add(phrase, w, current); 
     } 
     else { 
      addPhrase(phrase, w, current); 
     } 
    } 

    void addPhrase(vector<string> phrase, int weight, Node* n) { 
     Node* current = n; 
     for (int i = 0; i < phrase.size(); i++) { 
      Node temp = *new Node(phrase[i]); 
      current->children.push_back(temp); 
      current = &current->children.back(); 
      if (i == phrase.size() - 1) { 
       current->setEOS(); 
       current->setWeight(weight); 
      } 
     } 
    } 

    void get(vector<string> search) { 
     Node* current = &this->root; 
     get(search, current); 
    } 

    void get(vector<string> search, Node* n) { 

     Node* current = n; 
     int found = -1; 

     //test search size 
     if (search.size() == 0) { 
      cout << "Please enter a valid search" << endl; 
     } 

     for (int i = 0; i < current->children.size(); i++) { 
      if (search[0] == current->children[i].getWord()) { 
       found = i; 
      } 
     } 
     if (found > -1 && search.size() == 1) { 
      current = &current->children[found]; 
      printFromNode(*current); 
      maxNode(*current); 
     } 
     else if (found > -1 && search.size() != 1) { 
      current = &current->children[found]; 
      search.erase(search.begin()); 
      get(search, current); 

     } 
     else { 
      cout << "Not Found" << endl; 
     } 
    } 

    void printOutput(vector<pair<int,string>> p){ 
     sort(p.begin(), p.end()); 
     cout << p.size() << endl; 
     for (int i = 0; i < p.size(); i++) { 
      cout << p[i].second << " " << endl; 
     } 
    } 


    void printFromNode(Node n) { 
     vector<string> phrase = {}; 
     vector <pair < int, string>> final = {}; 
     printFromNode(n,phrase,final); 
    } 

    void printFromNode(Node n, vector<string> &v, vector<pair<int,string>> &p) { 
     string output; 
     if (n.getWord() == "") { 
      return; 
     } 

     for (int i = 0; i < n.children.size(); i++) { 
      if (n.children[i].getWeight() > 0) { 
       for (int i = 0; i < v.size(); i++) 
       { 
        output.append(v[i] + " "); 
       } 
       output.append(n.children[i].getWord()); 
       p.push_back(make_pair(n.children[i].getWeight(), output)); 
      } 
      v.push_back(n.children[i].getWord()); 
      printFromNode(n.children[i], v, p); 
      v.pop_back(); 
      sort(p.begin(), p.end()); 
     } 
     return; 

    } 


    void maxNode(Node n) { 
     int max = 0; 
     int index = 0; 
     int temp = 0; 
     for (int i = 0; i < n.children.size(); i++) { 
      temp = n.children[i].children.size(); 
      if (temp > max) { 
       max = temp; 
       index = i; 
      } 
     } 
     cout << n.children[index].getWord() << " " << max << endl; 
    } 

}; 

Main.cpp:

#include "Trie.cpp" 
#include <iostream> 
#include <sstream> 
#include <string> 
#include <vector> 

using namespace std; 

int main(int argc, char* argv[]) { 
    // Initialize trie up here 
    Trie myTrie = *new Trie(); 

    // parse input lines until I find newline 
    for(string line; getline(cin, line) && line.compare("");) { 
     stringstream ss(line); 
     string string_weight; 
     ss >> string_weight; 
     int weight = stoi(string_weight); 

     // I am just going to put these words into a vector 
     // you probably want to put them in your trie 

     vector<string> phrase = {}; 
     for(string word; ss >> word;) { 
      phrase.push_back(word); 
     } 


     myTrie.add(phrase, weight, &myTrie.root); 

     vector<string> ans = {}; 



    } 
    // parse query line 
    string query; 
    getline(cin, query); 
    stringstream ss(query); 
    vector<string> search = {}; 
    for (string query; ss >> query;) { 
     search.push_back(query); 
    } 

    myTrie.get(search); 

    return 0; 
} 

Answer 1

können Sie rekursive Methoden entfernen, und etwas zu tun, wie folgt aus:

#include <algorithm> 
#include <iostream> 
#include <map> 
#include <string> 
#include <vector> 
#include <set> 

class Node 
{ 
public: 
    bool endOfSentence = false; 
    std::set<int> weights; 
    std::map<std::string, Node> children; 

    Node() = default; 

    const Node* get(const std::string& word) const 
    { 
     auto it = children.find(word); 

     if (it == children.end()) { 
      return nullptr; 
     } 
     return &it->second; 
    } 

    auto find_by_weight(int weight) const 
    { 
     return std::find_if(children.begin(), 
          children.end(), 
          [=](const auto& p){ return p.second.weights.count(weight);}); 
    } 

}; 


class Trie 
{ 
    Node root; 
public: 

    void add(int weight, const std::vector<std::string>& phrase) 
    { 
     Node* node = &root; 
     for (const auto& word : phrase) { 
      node->weights.insert(weight); 
      node = &node->children[word]; 
     } 
     node->weights.insert(weight); 
     node->endOfSentence = true; 
    } 

    bool contains(const std::vector<std::string>& phrase) const 
    { 
     const Node* node = &root; 
     for (const auto& word : phrase) { 
      node = node->get(word); 
      if (node == nullptr) { 
       return false; 
      } 
     } 
     return node->endOfSentence; 
    } 

    void print(int weight) const 
    { 
     const Node* node = &root; 
     const char* sep = ""; 
     while (node) { 
      const auto it = node->find_by_weight(weight); 

      if (it == node->children.end()) { 
       break; 
      } 
      std::cout << sep << it->first; 
      sep = " "; 
      node = &it->second; 
     } 
     std::cout << std::endl; 
    } 

    void print_all() const 
    { 
     for (int i : root.weights) { 
      print(i); 
     } 
    } 
}; 

Und Verwendung/Test:

Demo