fork(4) download
copy 
  1. #include <iostream>
  2. #include <string>
  3.  
  4. typedef std::string::const_iterator It;
  5.  
  6. /*
  7.  * Extract sequences of non-wildcard characters from pattern range
  8.  */
  9. std::string extract_token(It &s, It e) // [s,e) is (sub)pattern
  10. {
  11.     It wcard;
  12.     for (wcard=s; wcard!=e; ++wcard)
  13.         if ('?' == *wcard) break;
  14.  
  15.     std::string token(s,wcard);
  16.  
  17.     for (s=wcard; s!=e; ++s)
  18.         if ('?' != *s) break; // treat '??' as '?' in pattern
  19.  
  20.     return token;
  21. }
  22.  
  23. /*
  24.  * Match a (sub)pattern against a (sub)input
  25.  *
  26.  * Strategy:
  27.  *    - extract first token from pattern
  28.  *    - exit with success for no (more) tokens
  29.  *    - for each token match in input
  30.  *        - match the remainder of the pattern against the remainder of the
  31.  *          input
  32.  *        - if no successful submatch, fail, otherwise done
  33.  *
  34.  * There is recursion (the matching of the remainder class match(....)
  35.  * recursively).
  36.  *
  37.  * There is backtracking (if the recursive match doesn't succeed, we try the
  38.  * next token submatch)
  39.  */
  40. bool match(It patb, It pate, const std::string& input)
  41. {
  42.     while (patb != pate)
  43.     {
  44.         // get next token from pattern, advancing patb
  45.         std::string token = extract_token(patb, pate); // updates patb
  46.  
  47.         if (!token.empty()) // could happen if pattern begins/ends with redundant '?'
  48.         {
  49.             size_t submatch = input.find(token);  // first submatch please
  50.  
  51.             while (std::string::npos != submatch)  // while we have a submatch
  52.             {
  53.                 if (match(patb, pate, input.substr(token.size())))
  54.                     return true; // match completed successfully
  55.  
  56.                 // look for later potential submatches (*backtrack*)
  57.                 submatch = input.find(token, submatch+1);
  58.             }
  59.             return false; // required token not found
  60.         }
  61.     }
  62.     return true; // no (remaining) pattern, always match
  63. }
  64.  
  65. bool match(const std::string& pattern, const std::string& input)
  66. {
  67.     // just relay to overload more suited for recursion
  68.     return match(pattern.begin(), pattern.end(), input); 
  69. }
  70.  
  71. //////////////////////
  72. // TEST PROGRAM
  73.  
  74. void test(const std::string& pattern, const std::string& input)
  75. {
  76.     std::cout << std::boolalpha;
  77.     std::cout << "match(\"" << pattern << "\", \"" << input << "\") => " 
  78.               << match(pattern, input) << std::endl;
  79. }
  80.  
  81. int main()
  82. {
  83.     // matches
  84.     test("?????",               "");
  85.     test("?????",               "?????");
  86.     test("",                    "");
  87.     test("",                    "glorious");
  88.     test("?r?o",                "glorious");
  89.     test("some?words?exist",    "some silly words should, most definitely, be existing");
  90.     test("some??words?exist?",  "some silly words should, most definitely, be existing");
  91.  
  92.     // failing matches
  93.     test("_",                   "");
  94.     test("_",                   "glorious");
  95.     test("_",                   "glorious");
  96.     test("glorious",            "glo?ious");
  97.     test("?some??words?exist?", "bogus");
  98. }
  99.  
Success #stdin #stdout 0s 2864KB
comments ()
stdin
copy 
Standard input is empty
stdout
copy 
match("?????", "") => true
match("?????", "?????") => true
match("", "") => true
match("", "glorious") => true
match("?r?o", "glorious") => true
match("some?words?exist", "some silly words should, most definitely, be existing") => true
match("some??words?exist?", "some silly words should, most definitely, be existing") => true
match("_", "") => false
match("_", "glorious") => false
match("_", "glorious") => false
match("glorious", "glo?ious") => false
match("?some??words?exist?", "bogus") => false
https://ideone.com/yApYp
language:
C++ (gcc 8.3)
created:
13 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!