Trieからの印刷

Question

私は文の単語を保持するように設計されたC++でトライを構築しました。各センテンスには、出力する順序を決定する重みがあります。私は他の再帰関数を呼び出すいくつかの再帰関数を持っています。私が直面するジレンマは、リストを1回だけ印刷したいということです。

私のget関数はprintFromNode関数を呼び出します。この関数は、ソートして印刷したいペアpのベクトルを作成します。もし誰かが正しい方向に私を向けることができれば、それは大いに感謝されます。

コード： 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

あなたは再帰的なメソッドを削除し、以下のようなものをやってすることができます

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

そして、使用/テスト：

int main(int argc, char* argv[]) { 
    const std::vector<std::vector<std::string>> sentences = { 
     {"My", "name", "is", "John"}, 
     {"My", "house", "is", "small"}, 
     {"Hello", "world"}, 
     {"Hello", "world", "!"} 
    }; 

    Trie trie; 
    int i = 0; 
    for (const auto& sentence : sentences) { 
     trie.add(i, sentence); 
     ++i; 
    } 

    const std::vector<std::vector<std::string>> queries = { 
     {"My", "name", "is", "John"}, 
     {"My", "house"}, 
     {"Hello", "world"} 
    }; 

    for (const auto& query : queries) { 
     std::cout << trie.contains(query) << std::endl; 
    } 

    trie.print_all(); 
} 

Demo