给出一个如下的正则表达式：
(hello|goodbye) (world(s|)|)
我将如何生成以下数据？
hello worldshello worldhello goodbye worldsgoodbye worldgoodbye
我不太确定我是否需要首先构建树,或者是否可以递归地完成.我坚持使用什么数据结构,以及如何在我去时生成字符串.我必须保留一堆标记,并索引到部分构建的字符串中以连接更多的数据吗？我不知道如何最好地解决这个问题.我是否需要首先阅读整个表达,并以某种方式重新排列？
函数签名将以下列方式：
std::vector<std::string> Generate(std::string const&){ //...} 你建议我做什么？
编辑：
让我澄清一下结果应该是有限的.在我的具体例子中,只有6个字符串对于表达式将是真实的.我不知道我的术语在这里是否正确,但我正在寻找的是表达式的完美匹配 – 而不是包含与子字符串匹配的任何字符串.
从面向对象的立场来看,我写了一个扫描仪来获取正则表达式(string),并将其转换为令牌列表(字符串向量).然后将令牌列表发送到生成n-ary树的解析器.所有这些都被打包在一个“表达式生成器”类中,它可以采用表达式并保持解析树以及生成的计数.
扫描仪很重要,因为它标记了空字符串的情况,您可以在我的问题中看到,显示为“|)”.扫描也创建了[word] [operation] [word] [operation] … [word]的模式.
例如,扫描：“(hello | goodbye)(world(s |)|)”
将创建：[] [(] [hello] [|] [再见] []] [] [(] [世界] [(] [s] [|] [] []] [] [|] [] [ )] []
解析树是节点的向量.节点包含节点向量的向量.
橙色单元格表示“或”,而绘制连接的其他框代表“和”.以下是我的代码
节点头
#pragma once#include <string>#include <vector>class Function_Expression_Node{public: Function_Expression_Node(std::string const& value_in = "",bool const& more_in = false); std::string value; bool more; std::vector<std::vector<Function_Expression_Node>> children;}; 节点源
#include "function_Expression_node.hpp" Function_Expression_Node::Function_Expression_Node(std::string const& value_in,bool const& more_in) : value(value_in),more(more_in) {} 扫描仪标题
#pragma once#include <vector>#include <string>class Function_Expression_Scanner{ public: Function_Expression_Scanner() = delete; public: static std::vector<std::string> Scan(std::string const& Expression);}; 扫描仪来源
#include "function_Expression_scanner.hpp"std::vector<std::string> Function_Expression_Scanner::Scan(std::string const& Expression){ std::vector<std::string> tokens; std::string temp; for (auto const& it: Expression){ if (it == '('){ tokens.push_back(temp); tokens.push_back("("); temp.clear(); } else if (it == '|'){ tokens.push_back(temp); tokens.push_back("|"); temp.clear(); } else if (it == ')'){ tokens.push_back(temp); tokens.push_back(")"); temp.clear(); } else if (isAlpha(it) || it == ' '){ temp+=it; } } tokens.push_back(temp); return tokens; } 解析器标题
#pragma once#include <string>#include <vector>#include "function_Expression_node.hpp"class Function_Expression_Parser{ Function_Expression_Parser() = delete;//get parse treepublic: static std::vector<std::vector<Function_Expression_Node>> Parse(std::vector<std::string> const& tokens,unsigned int & amount); private: static std::vector<std::vector<Function_Expression_Node>> Build_Parse_Tree(std::vector<std::string>::const_iterator & it,std::vector<std::string>::const_iterator const& end,unsigned int & amount); private: static Function_Expression_Node Recursive_Build(std::vector<std::string>::const_iterator & it,int & total); //<- recursive //utility private: static bool Is_Word(std::string const& it);}; 解析源
#include "function_Expression_parser.hpp"bool Function_Expression_Parser::Is_Word(std::string const& it){ return (it != "(" && it != "|" && it != ")"); }Function_Expression_Node Function_Expression_Parser::Recursive_Build(std::vector<std::string>::const_iterator & it,int & total){ Function_Expression_Node sub_root("",true); //<- contains the full root std::vector<Function_Expression_Node> root; const auto begin = it; //calculate the amount std::vector<std::vector<int>> multiplIEs; std::vector<int> adds; int sub_amount = 1; while(*it != ")"){ //when we see a "WORD",add it. if(Is_Word(*it)){ root.push_back(Function_Expression_Node(*it)); } //when we see a "(",build the subtree,else if (*it == "("){ ++it; root.push_back(Recursive_Build(it,sub_amount)); //adds.push_back(sub_amount); //sub_amount = 1; } //else we see an "OR" and we do the split else{ sub_root.children.push_back(root); root.clear(); //store the sub amount adds.push_back(sub_amount); sub_amount = 1; } ++it; } //add the last bit,if there is any if (!root.empty()){ sub_root.children.push_back(root); //store the sub amount adds.push_back(sub_amount); } if (!adds.empty()){ multiplIEs.push_back(adds); } //calculate sub total int or_count = 0; for (auto const& it: multiplIEs){ for (auto const& it2: it){ or_count+=it2; } if (or_count > 0){ total*=or_count; } or_count = 0; } /* std::cout << "---SUB FUNCTION---\n"; for (auto it: multiplIEs){for (auto it2: it){std::cout << "{" << it2 << "} ";}std::cout << "\n";}std::cout << "--\n"; std::cout << total << std::endl << '\n'; */ return sub_root;}std::vector<std::vector<Function_Expression_Node>> Function_Expression_Parser::Build_Parse_Tree(std::vector<std::string>::const_iterator & it,unsigned int & amount){ std::vector<std::vector<Function_Expression_Node>> full_root; std::vector<Function_Expression_Node> root; const auto begin = it; //calculate the amount std::vector<int> adds; int sub_amount = 1; int total = 0; while (it != end){ //when we see a "WORD",sub_amount)); } //else we see an "OR" and we do the split else{ full_root.push_back(root); root.clear(); //store the sub amount adds.push_back(sub_amount); sub_amount = 1; } ++it; } //add the last bit,if there is any if (!root.empty()){ full_root.push_back(root); //store the sub amount adds.push_back(sub_amount); sub_amount = 1; } //calculate sub total for (auto const& it: adds){ total+=it; } /* std::cout << "---ROOT FUNCTION---\n"; for (auto it: adds){std::cout << "[" << it << "] ";}std::cout << '\n'; std::cout << total << std::endl << '\n'; */ amount = total; return full_root;}std::vector<std::vector<Function_Expression_Node>> Function_Expression_Parser::Parse(std::vector<std::string> const& tokens,unsigned int & amount){ auto it = tokens.cbegin(); auto end = tokens.cend(); auto parse_tree = Build_Parse_Tree(it,end,amount); return parse_tree;} 发电机头
#pragma once#include "function_Expression_node.hpp"class Function_Expression_Generator{ //constructors public: Function_Expression_Generator(std::string const& Expression); public: Function_Expression_Generator(); //transformer voID Set_New_Expression(std::string const& Expression); //observers public: unsigned int Get_Count(); //public: unsigned int Get_One_Word_name_Count(); public: std::vector<std::string> Get_Generations(); private: std::vector<std::string> Generate(std::vector<std::vector<Function_Expression_Node>> const& parse_tree); private: std::vector<std::string> Sub_Generate(std::vector<Function_Expression_Node> const& nodes);private: std::vector<std::vector<Function_Expression_Node>> m_parse_tree; unsigned int amount;}; 发电机源
#include "function_Expression_generator.hpp"#include "function_Expression_scanner.hpp"#include "function_Expression_parser.hpp"//constructorsFunction_Expression_Generator::Function_Expression_Generator(std::string const& Expression){ auto tokens = Function_Expression_Scanner::Scan(Expression); m_parse_tree = Function_Expression_Parser::Parse(tokens,amount);}Function_Expression_Generator::Function_Expression_Generator(){}//transformervoID Function_Expression_Generator::Set_New_Expression(std::string const& Expression){ auto tokens = Function_Expression_Scanner::Scan(Expression); m_parse_tree = Function_Expression_Parser::Parse(tokens,amount);}//observersunsigned int Function_Expression_Generator::Get_Count(){ return amount;}std::vector<std::string> Function_Expression_Generator::Get_Generations(){ return Generate(m_parse_tree);}std::vector<std::string> Function_Expression_Generator::Generate(std::vector<std::vector<Function_Expression_Node>> const& parse_tree){ std::vector<std::string> results; std::vector<std::string> more; for (auto it: parse_tree){ more = Sub_Generate(it); results.insert(results.end(),more.begin(),more.end()); } return results;}std::vector<std::string> Function_Expression_Generator::Sub_Generate(std::vector<Function_Expression_Node> const& nodes){ std::vector<std::string> results; std::vector<std::string> more; std::vector<std::string> new_results; results.push_back(""); for (auto it: nodes){ if (!it.more){ for (auto & result: results){ result+=it.value; } } else{ more = Generate(it.children); for (auto m: more){ for (auto r: results){ new_results.push_back(r+m); } } more.clear(); results = new_results; new_results.clear(); } } return results;} 总之,如果需要为正则表达式生成匹配,我建议使用exrex或本线程中提到的任何其他程序.
总结以上是内存溢出为你收集整理的c – 给定一个正则表达式,如何生成与之匹配的所有字符串？全部内容，希望文章能够帮你解决c – 给定一个正则表达式,如何生成与之匹配的所有字符串？所遇到的程序开发问题。
如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）