我使用了一个仅包含()、|、空格和字母的简单语言。
给定如下的正则表达式：
(hello|goodbye) (world(s|)|)
我该如何生成以下数据？
hello worlds
hello world
hello
goodbye worlds
goodbye world
goodbye
我不确定我是先需要构建一棵树，还是可以使用递归来完成。我卡在了要使用哪些数据结构以及如何在遍历过程中生成字符串。我是否需要保留一堆标记，并且重新索引到部分构建的字符串中以连接更多的数据？我不知道最好的解决方法是什么。我需要先读取整个表达式，然后按某种方式重新排序吗？
函数签名将如下所示：
std::vector<std::string> Generate(std::string const&){
//...
}
你有什么建议？
编辑：
让我澄清一下，在这里结果始终应该是有限的。在我的特定示例中，只有6个字符串会对表达式返回True。我不确定我的术语是否正确，但我要找的是表达式的完全匹配-不是任何包含与其子字符串匹配的字符串。
在某种程度上遵循Kieveli的建议，我想出了一个可行的解决方案。虽然之前没有提到，但对我来说也很重要，需要知道潜在结果的数量。我使用了一个名为 "exrex" 的Python脚本，我在github上找到了它。尴尬的是，我没有意识到它也有计数功能。尽管如此，我尽力用我的简化正则表达式语言在C++中实现了它。如果您对我的解决方案感兴趣，请继续阅读。
从面向对象的角度来看，我编写了一个扫描器，将正则表达式（字符串）转换为令牌列表（字符串向量）。然后将令牌列表发送到解析器，生成一个n叉树。所有这些都被封装在一个“表达式生成器”类中，该类可以接受表达式并保存解析树以及生成的计数。
"(hello|goodbye) (world(s|)|)"[][(][hello][|][goodbye][)][ ][(][world][(][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 tree
public: 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, std::vector<std::string>::const_iterator const& end, 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", 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));
}
//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"
//constructors
Function_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(){}
//transformer
void 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);
}
//observers
unsigned 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;
}
Node:
list of string values
isRequired
list of child Nodes
Node1:
hello, goodbye
true
[] (no child nodes)
Node2:
world,
false
[
Node3:
s,
false
[]
]
recursiveGenerate( node_list, parital )
if ( node_list is null or is empty )
add partial to an output list
for the first node
if ( ! node.isRequired )
recursiveGenrate( remaining nodes, partial )
for each value
recursiveGenerate( child Nodes + remaining nodes, partial + value )
import dictionary
words, endings = dictionary.expand_expression('colou?r', {})
print words
这里，第二个参数是用于引用（即命名块），结束符为例如look{s,ed,ing}
它的工作原理...
lex_expression将字符串分割成由正则表达式标记[]<>|(){}?分隔的标记。因此，a(b|cd)efg变成了['a', '(', 'b', '|', 'cd', ')', 'efg']。这使得解析正则表达式更容易。
parse_XYZ_expr函数（以及顶级parse_expr）解析正则表达式元素，构建表示正则表达式的对象层次结构。这些对象是：
a?）ab(cd|e)?被表示为Sequence(Literal('ab'), Optional(Choice(Literal('cd'), Literal('e'))))。expr.expand(words) => expanded的扩展方法，例如：expr = Optional('cd')
print expr.expand(['ab', 'ef'])
ab
abcd
ef
efcd
让我重新发布我以前的一个答案：
我曾经写过一个小程序，它可以做到这一点：
它的工作原理如下：
所有的 ? {} + * | () 运算符都被展开（到最大限度），以便只剩下字符类和反向引用。
例如：[a-c]+|t*|([x-z]){2}foo\1|(a|b)(t|u) 变成 [a-c]|[a-c][a-c]|[a-c][a-c][a-c]|[a-c][a-c][a-c][a-c]||t|tt|tt|ttt|ttt|([x-z][x-z])foo\1|at|au|bt|bu
（后面表达式中的 | 仅为符号，程序将每个备选子正则表达式保留在列表中）
多字符反向引用被替换为单字符反向引用。
例如，上述表达式变成了 [a-c]|[a-c][a-c]|[a-c][a-c][a-c]|[a-c][a-c][a-c][a-c]||t|tt|tt|ttt|ttt|([x-z])([x-z])foo\1\2|at|au|bt|bu
现在，每个备选子正则表达式匹配一个固定长度的字符串。
对于每个备选项，打印出从类中选择字符的所有组合：
例如，上述表达式变成了 a|b|c|aa|ba|..|cc|aaa|baa|...|ccc|aaaa|...|cccc||t|tt|tt|ttt|ttt|xxfooxx|yxfooyx|...|zzfoozz|at|au|bt|bu
foo hello bar。 - p.s.w.g