C++ chaîne diff (à la difflib de Python)

Question

J'essaie de comparer deux chaînes pour déterminer si elles varient uniquement dans un sous-ensemble numérique de la structure de chaîne; par exemple,

varies_in_single_number_field('foo7bar', 'foo123bar') 
# Returns True, because 7 != 123, and there's only one varying 
# number region between the two strings. 

En Python je peux utiliser le difflib pour accomplir ceci:

import difflib, doctest 

def varies_in_single_number_field(str1, str2): 
    """ 
    A typical use case is as follows: 
     >>> varies_in_single_number_field('foo7bar00', 'foo123bar00') 
     True 

    Numerical variation in two dimensions is no good: 
     >>> varies_in_single_number_field('foo7bar00', 'foo123bar01') 
     False 

    Varying in a nonexistent field is okay: 
     >>> varies_in_single_number_field('foobar00', 'foo123bar00') 
     True 

    Identical strings don't *vary* in any number field: 
     >>> varies_in_single_number_field('foobar00', 'foobar00') 
     False 
    """ 
    in_differing_substring = False 
    passed_differing_substring = False # There should be only one. 
    differ = difflib.Differ() 
    for letter_diff in differ.compare(str1, str2): 
     letter = letter_diff[2:] 
     if letter_diff.startswith(('-', '+')): 
      if passed_differing_substring: # Already saw a varying field. 
       return False 
      in_differing_substring = True 
      if not letter.isdigit(): return False # Non-digit diff character. 
     elif in_differing_substring: # Diff character not found - end of diff. 
      in_differing_substring = False 
      passed_differing_substring = True 
    return passed_differing_substring # No variation if no diff was passed. 

if __name__ == '__main__': doctest.testmod() 

Mais je ne sais pas comment trouver quelque chose comme difflib C++. Des approches alternatives bienvenues. :)

Answer 1

Cela peut fonctionner, il passe au moins votre test de démonstration: EDIT: J'ai apporté quelques modifications pour résoudre certains problèmes d'indexation de chaînes. Je crois que ça devrait être bon maintenant.

#include <iostream> 
#include <string> 
#include <vector> 
#include <algorithm> 
#include <cctype> 

bool starts_with(const std::string &s1, const std::string &s2) { 
    return (s1.length() <= s2.length()) && (s2.substr(0, s1.length()) == s1); 
} 

bool ends_with(const std::string &s1, const std::string &s2) { 
    return (s1.length() <= s2.length()) && (s2.substr(s2.length() - s1.length()) == s1); 
} 

bool is_numeric(const std::string &s) { 
    for(std::string::const_iterator it = s.begin(); it != s.end(); ++it) { 
     if(!std::isdigit(*it)) { 
       return false; 
     } 
    } 
    return true; 
} 

bool varies_in_single_number_field(std::string s1, std::string s2) { 

    size_t index1 = 0; 
    size_t index2 = s1.length() - 1; 

    if(s1 == s2) { 
     return false; 
    } 

    if((s1.empty() && is_numeric(s2)) || (s2.empty() && is_numeric(s1))) { 
     return true; 
    } 

    if(s1.length() < s2.length()) { 
     s1.swap(s2); 
    } 

    while(index1 < s1.length() && starts_with(s1.substr(0, index1), s2)) { index1++; } 
    while(ends_with(s1.substr(index2), s2)) { index2--; } 

    return is_numeric(s1.substr(index1 - 1, (index2 + 1) - (index1 - 1))); 

} 

int main() { 
    std::cout << std::boolalpha << varies_in_single_number_field("foo7bar00", "foo123bar00") << std::endl; 
    std::cout << std::boolalpha << varies_in_single_number_field("foo7bar00", "foo123bar01") << std::endl; 
    std::cout << std::boolalpha << varies_in_single_number_field("foobar00", "foo123bar00") << std::endl; 
    std::cout << std::boolalpha << varies_in_single_number_field("foobar00", "foobar00") << std::endl; 
    std::cout << std::boolalpha << varies_in_single_number_field("7aaa", "aaa") << std::endl; 
    std::cout << std::boolalpha << varies_in_single_number_field("aaa7", "aaa") << std::endl; 
    std::cout << std::boolalpha << varies_in_single_number_field("aaa", "7aaa") << std::endl; 
    std::cout << std::boolalpha << varies_in_single_number_field("aaa", "aaa7") << std::endl; 
} 

Fondamentalement, il recherche une chaîne qui a 3 parties, chaine2 commence par part1, chaîne2 se termine par part3 et part2 est que des chiffres.

Answer 2

C'est probablement un peu exagéré, mais vous pouvez utiliser boost pour s'interfacer avec python. Au pire, difflib est implémenté en python pur, et ce n'est pas trop long. Il devrait être possible de porter de python à C ...

Answer 3

Vous pouvez faire une approche ad hoc: Vous cherchez à faire correspondre les chaînes s et s ', où s = abc et s' = ab'c, et les b et b 'doivent être deux nombres distincts (possible vide). Donc:

1. Comparez les chaînes de gauche, char par char, jusqu'à ce que vous frappiez différents caractères, puis arrêtez. De même, comparez les chaînes de droite jusqu'à ce que vous frappiez des caractères différents, ou frappez ce marqueur gauche.
2. Ensuite, vérifiez les restes au milieu pour voir si ce sont les deux nombres.

Answer 4

Teran @ Evan: ressemble à ce que nous avons fait en parallèle - j'ai une mise en oeuvre O (n) nettement moins lisible:

#include <cassert> 
#include <cctype> 
#include <string> 
#include <sstream> 
#include <iostream> 

using namespace std; 

ostringstream debug; 
const bool DEBUG = true; 

bool varies_in_single_number_field(const string &str1, const string &str2) { 
    bool in_difference = false; 
    bool passed_difference = false; 
    string str1_digits, str2_digits; 
    size_t str1_iter = 0, str2_iter = 0; 
    while (str1_iter < str1.size() && str2_iter < str2.size()) { 
     const char &str1_char = str1.at(str1_iter); 
     const char &str2_char = str2.at(str2_iter); 
     debug << "str1: " << str1_char << "; str2: " << str2_char << endl; 
     if (str1_char == str2_char) { 
      if (in_difference) { 
       in_difference = false; 
       passed_difference = true; 
      } 
      ++str1_iter, ++str2_iter; 
      continue; 
     } 
     in_difference = true; 
     if (passed_difference) { /* Already passed a difference. */ 
      debug << "Already passed a difference." << endl; 
      return false; 
     } 
     bool str1_char_is_digit = isdigit(str1_char); 
     bool str2_char_is_digit = isdigit(str2_char); 
     if (str1_char_is_digit && !str2_char_is_digit) { 
      ++str1_iter; 
      str1_digits.push_back(str1_char); 
     } else if (!str1_char_is_digit && str2_char_is_digit) { 
      ++str2_iter; 
      str2_digits.push_back(str2_char); 
     } else if (str1_char_is_digit && str2_char_is_digit) { 
      ++str1_iter, ++str2_iter; 
      str1_digits.push_back(str1_char); 
      str2_digits.push_back(str2_char); 
     } else { /* Both are non-digits and they're different. */ 
      return false; 
     } 
    } 
    if (in_difference) { 
     in_difference = false; 
     passed_difference = true; 
    } 
    string str1_remainder = str1.substr(str1_iter); 
    string str2_remainder = str2.substr(str2_iter); 
    debug << "Got to exit point; passed difference: " << passed_difference 
     << "; str1 digits: " << str1_digits 
     << "; str2 digits: " << str2_digits 
     << "; str1 remainder: " << str1_remainder 
     << "; str2 remainder: " << str2_remainder 
     << endl; 
    return passed_difference 
     && (str1_digits != str2_digits) 
     && (str1_remainder == str2_remainder); 
} 

int main() { 
    assert(varies_in_single_number_field("foo7bar00", "foo123bar00") == true); 
    assert(varies_in_single_number_field("foo7bar00", "foo123bar01") == false); 
    assert(varies_in_single_number_field("foobar00", "foo123bar00") == true); 
    assert(varies_in_single_number_field("foobar00", "foobar00") == false); 
    assert(varies_in_single_number_field("foobar00", "foobaz00") == false); 
    assert(varies_in_single_number_field("foo00bar", "foo01barz") == false); 
    assert(varies_in_single_number_field("foo01barz", "foo00bar") == false); 
    if (DEBUG) { 
     cout << debug.str(); 
    } 
    return 0; 
} 

Answer 5

Que diriez-vous d'utiliser quelque chose comme boost :: regex?

 
// pseudo code, may or may not compile 
bool match_except_numbers(const std::string& s1, const std::string& s2) 
{ 
    static const boost::regex fooNumberBar("foo\\d+bar"); 
    return boost::match(s1, fooNumberBar) && boost::match(s2, fooNumberBar); 
}