Databases
StackOverflow2013
Postsdbo
PO
Body
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    text
    copied!<p>Somewhat following <a href="https://stackoverflow.com/users/15852/kieveli">Kieveli</a>'s advice, I have come up with a working solution. Although not previously mentioned, it was important for me to also get a count of how many results could potentially be generated. I was using a python script called "<a href="https://github.com/asciimoo/exrex" rel="nofollow noreferrer">exrex</a>" which I had found on github. Embarrassingly, I did not realize that it had the capability to also count. Nonetheless, I implemented it the best I could in C++ using my simplified regular expression language. If interested in my solution, please read on.</p> <p>From an object oriented stand point, I wrote a scanner to take the regular expression(string), and convert it into a list of tokens(vector of strings). The list of tokens was then sent to a parser which generated an n-ary tree. All of this was packed inside an "expression generator" class that could take an expression and hold the parse tree, as well as the generated count.<br> <img src="https://i.stack.imgur.com/GxmAe.png" alt="object overview"><br> The scanner was important because it tokenized the empty string case which you can see in my question appearing as "|)". Scanning also created a pattern of [word] [operation] [word] [operation] ... [word].<br> For example, scanning: <code>"(hello|goodbye) (world(s|)|)"</code><br> will create: <code>[][(][hello][|][goodbye][)][ ][(][world][(][s][|][][)][][|][][)][]</code></p> <p>The parse tree was a vector of nodes. Nodes contain a vector of vector of nodes. <img src="https://i.stack.imgur.com/Kpb36.jpg" alt="parse structure"><br> The orange cells represent the "or"s, and the other boxes that draw the connections, represent the "and"s. Below is my code.</p> <p><strong>Node header</strong></p> <pre><code>#pragma once #include &lt;string&gt; #include &lt;vector&gt; class Function_Expression_Node{ public: Function_Expression_Node(std::string const&amp; value_in = "", bool const&amp; more_in = false); std::string value; bool more; std::vector&lt;std::vector&lt;Function_Expression_Node&gt;&gt; children; }; </code></pre> <p><strong>Node source</strong></p> <pre><code>#include "function_expression_node.hpp" Function_Expression_Node::Function_Expression_Node(std::string const&amp; value_in, bool const&amp; more_in) : value(value_in) , more(more_in) {} </code></pre> <p><strong>Scanner header</strong></p> <pre><code>#pragma once #include &lt;vector&gt; #include &lt;string&gt; class Function_Expression_Scanner{ public: Function_Expression_Scanner() = delete; public: static std::vector&lt;std::string&gt; Scan(std::string const&amp; expression); }; </code></pre> <p><strong>Scanner source</strong></p> <pre><code>#include "function_expression_scanner.hpp" std::vector&lt;std::string&gt; Function_Expression_Scanner::Scan(std::string const&amp; expression){ std::vector&lt;std::string&gt; tokens; std::string temp; for (auto const&amp; 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; } </code></pre> <p><strong>Parser header</strong></p> <pre><code>#pragma once #include &lt;string&gt; #include &lt;vector&gt; #include "function_expression_node.hpp" class Function_Expression_Parser{ Function_Expression_Parser() = delete; //get parse tree public: static std::vector&lt;std::vector&lt;Function_Expression_Node&gt;&gt; Parse(std::vector&lt;std::string&gt; const&amp; tokens, unsigned int &amp; amount); private: static std::vector&lt;std::vector&lt;Function_Expression_Node&gt;&gt; Build_Parse_Tree(std::vector&lt;std::string&gt;::const_iterator &amp; it, std::vector&lt;std::string&gt;::const_iterator const&amp; end, unsigned int &amp; amount); private: static Function_Expression_Node Recursive_Build(std::vector&lt;std::string&gt;::const_iterator &amp; it, int &amp; total); //&lt;- recursive //utility private: static bool Is_Word(std::string const&amp; it); }; </code></pre> <p><strong>Parser source</strong></p> <pre><code>#include "function_expression_parser.hpp" bool Function_Expression_Parser::Is_Word(std::string const&amp; it){ return (it != "(" &amp;&amp; it != "|" &amp;&amp; it != ")"); } Function_Expression_Node Function_Expression_Parser::Recursive_Build(std::vector&lt;std::string&gt;::const_iterator &amp; it, int &amp; total){ Function_Expression_Node sub_root("",true); //&lt;- contains the full root std::vector&lt;Function_Expression_Node&gt; root; const auto begin = it; //calculate the amount std::vector&lt;std::vector&lt;int&gt;&gt; multiplies; std::vector&lt;int&gt; 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&amp; it: multiplies){ for (auto const&amp; it2: it){ or_count+=it2; } if (or_count &gt; 0){ total*=or_count; } or_count = 0; } /* std::cout &lt;&lt; "---SUB FUNCTION---\n"; for (auto it: multiplies){for (auto it2: it){std::cout &lt;&lt; "{" &lt;&lt; it2 &lt;&lt; "} ";}std::cout &lt;&lt; "\n";}std::cout &lt;&lt; "--\n"; std::cout &lt;&lt; total &lt;&lt; std::endl &lt;&lt; '\n'; */ return sub_root; } std::vector&lt;std::vector&lt;Function_Expression_Node&gt;&gt; Function_Expression_Parser::Build_Parse_Tree(std::vector&lt;std::string&gt;::const_iterator &amp; it, std::vector&lt;std::string&gt;::const_iterator const&amp; end, unsigned int &amp; amount){ std::vector&lt;std::vector&lt;Function_Expression_Node&gt;&gt; full_root; std::vector&lt;Function_Expression_Node&gt; root; const auto begin = it; //calculate the amount std::vector&lt;int&gt; 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&amp; it: adds){ total+=it; } /* std::cout &lt;&lt; "---ROOT FUNCTION---\n"; for (auto it: adds){std::cout &lt;&lt; "[" &lt;&lt; it &lt;&lt; "] ";}std::cout &lt;&lt; '\n'; std::cout &lt;&lt; total &lt;&lt; std::endl &lt;&lt; '\n'; */ amount = total; return full_root; } std::vector&lt;std::vector&lt;Function_Expression_Node&gt;&gt; Function_Expression_Parser::Parse(std::vector&lt;std::string&gt; const&amp; tokens, unsigned int &amp; amount){ auto it = tokens.cbegin(); auto end = tokens.cend(); auto parse_tree = Build_Parse_Tree(it,end,amount); return parse_tree; } </code></pre> <p><strong>Generator header</strong></p> <pre><code>#pragma once #include "function_expression_node.hpp" class Function_Expression_Generator{ //constructors public: Function_Expression_Generator(std::string const&amp; expression); public: Function_Expression_Generator(); //transformer void Set_New_Expression(std::string const&amp; expression); //observers public: unsigned int Get_Count(); //public: unsigned int Get_One_Word_Name_Count(); public: std::vector&lt;std::string&gt; Get_Generations(); private: std::vector&lt;std::string&gt; Generate(std::vector&lt;std::vector&lt;Function_Expression_Node&gt;&gt; const&amp; parse_tree); private: std::vector&lt;std::string&gt; Sub_Generate(std::vector&lt;Function_Expression_Node&gt; const&amp; nodes); private: std::vector&lt;std::vector&lt;Function_Expression_Node&gt;&gt; m_parse_tree; unsigned int amount; }; </code></pre> <p><strong>Generator source</strong></p> <pre><code>#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&amp; 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&amp; 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&lt;std::string&gt; Function_Expression_Generator::Get_Generations(){ return Generate(m_parse_tree); } std::vector&lt;std::string&gt; Function_Expression_Generator::Generate(std::vector&lt;std::vector&lt;Function_Expression_Node&gt;&gt; const&amp; parse_tree){ std::vector&lt;std::string&gt; results; std::vector&lt;std::string&gt; more; for (auto it: parse_tree){ more = Sub_Generate(it); results.insert(results.end(), more.begin(), more.end()); } return results; } std::vector&lt;std::string&gt; Function_Expression_Generator::Sub_Generate(std::vector&lt;Function_Expression_Node&gt; const&amp; nodes){ std::vector&lt;std::string&gt; results; std::vector&lt;std::string&gt; more; std::vector&lt;std::string&gt; new_results; results.push_back(""); for (auto it: nodes){ if (!it.more){ for (auto &amp; 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; } </code></pre> <p>In conclusion, I recommend using <a href="https://github.com/asciimoo/exrex" rel="nofollow noreferrer">exrex</a>, or any other programs mentioned in this thread, if you need to generate matches for regular expressions.</p>
 

Querying!

 
Guidance
An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload