Je voudrais analyser une chaîne comme "{{0, 1}, {2, 3}}" en un std::map. Je peux écrire une petite fonction pour analyser une chaîne en utilisant la bibliothèque <regex>, mais je ne sais pas comment vérifier si une chaîne donnée est dans un format valide. Comment puis-je valider le format d'une chaîne?

#include <list>
#include <map>
#include <regex>
#include <iostream>

void f(const std::string& s) {
  std::map<int, int> m;
  std::regex p {"[\\[\\{\\(](\\d+),\\s*(\\d+)[\\)\\}\\]]"};
  auto begin = std::sregex_iterator(s.begin(), s.end(), p);
  auto end = std::sregex_iterator();
  for (auto x = begin; x != end; ++x) {
    std::cout << x->str() << '\n';
    m[std::stoi(x->str(1))] = std::stoi(x->str(2));
  }
  std::cout << m.size() << '\n';
}

int main() {
  std::list<std::string> l {
    "{{0, 1},   (2,    3)}",
    "{{4,  5, {6, 7}}" // Ill-formed, so need to throw an excpetion.
  };
  for (auto x : l) {
    f(x);
  }
}

REMARQUE: je ne me sens pas obligé d'utiliser regex pour résoudre ce problème. Tout type de solution, y compris certaines manières de valider et d'insérer à la fois en soustrayant des sous-chaînes, sera apprécié.

2
Han 20 juin 2019 à 09:42

5 réponses

Meilleure réponse

À mon avis, l'analyseur basé sur Spirit est toujours beaucoup plus robuste et lisible. C'est aussi beaucoup plus amusant à analyser avec Spirit :-). Donc, en plus de la réponse de @ Aleph0, j'aimerais fournir une solution compacte basée sur Spirit-X3:

#include <string>
#include <map>
#include <iostream>
#include <boost/fusion/adapted/std_pair.hpp>
#include <boost/spirit/home/x3.hpp>

int main() {
    std::string input ="{{0, 1},  {2, 3}}";
    using namespace boost::spirit::x3;
    const auto pair = '{' > int_ > ',' > int_ > '}';
    const auto pairs = '{' > (pair % ',')  > '}';
    std::map<int, int> output;
    // ignore spaces, tabs, newlines
    phrase_parse(input.begin(), input.end(), pairs, space, output);

    for (const auto [key, value] : output) {
        std::cout << key << ":" << value << std::endl;
    }
}

Notez que j'ai utilisé l'opérateur >, qui signifie "attendre". Ainsi, si l'entrée ne correspond pas à l'attente, Spirit lève une exception. Si vous préférez une panne silencieuse, utilisez plutôt l'opérateur >>.

3
Igor R. 21 juin 2019 à 13:17

C'est peut-être un peu trop, mais si vous avez boost entre vos mains, vous pouvez utiliser boost-spirit pour faire le travail à votre place. Un avantage pourrait être que la solution est facilement extensible pour analyser d'autres types de cartes, comme std::map<std::string, int> par exemple.

Un autre avantage, qui ne doit pas être sous-estimé, est que boost-spirit vous laisse avec des exceptions saines au cas où la chaîne ne satisferait pas votre grammaire. Il est assez difficile d'y parvenir avec une solution écrite à la main.

L'endroit où l'erreur se produit est également donné par boost-spirit, afin que vous puissiez revenir en arrière vers cet endroit.

#include <map>
#include <boost/spirit/include/qi.hpp>
#include <boost/spirit/include/phoenix_operator.hpp>
#include <boost/spirit/include/phoenix_stl.hpp>
#include <boost/fusion/adapted/std_pair.hpp>

template <typename Iterator, typename Skipper>
struct mapLiteral : boost::spirit::qi::grammar<Iterator, std::map<int,int>(), Skipper>
{
    mapLiteral() : mapLiteral::base_type(map)
    {
        namespace qi = boost::spirit::qi;
        using qi::lit;

        map = (lit("{") >> pair >> *(lit(",") >> pair) >> lit("}"))|(lit("{") >> lit("}"));
        pair = (lit("{") >> boost::spirit::int_ >> lit(",") >> boost::spirit::int_ >> lit("}"));
    }

    boost::spirit::qi::rule<Iterator, std::map<int, int>(), Skipper> map;
    boost::spirit::qi::rule<Iterator, std::pair<int, int>(), Skipper> pair;
};

std::map<int,int> parse(const std::string& expression, bool& ok)
{
    std::map<int, int>  result;
    try {
        std::string formula = expression;
        boost::spirit::qi::space_type space;
        mapLiteral<std::string::const_iterator, decltype(space)> parser;
        auto b = formula.begin();
        auto e = formula.end();
        ok = boost::spirit::qi::phrase_parse(b, e, parser, space, result);
        if (b != e) {
            ok = false;
            return std::map<int, int>();
        }
        return result;
    }
    catch (const boost::spirit::qi::expectation_failure<std::string::iterator>&) {
        ok = false;
        return result;
    }
}


int main(int argc, char** args)
{
    std::vector<std::pair<std::map<int, int>,std::string>> tests = {
        {{ },"{  \t\n}"},
        {{{5,2},{2,1}},"{ {5,2},{2,1} }"},
        {{},"{{2, 6}{}}"} // Bad food
    };
    for (auto iter :tests)
    {
        bool ok;
        auto result = parse(iter.second, ok);
        if (result == iter.first)
        {
            std::cout << "Equal:" << std::endl;
        }
    }
}
3
Aleph0 20 juin 2019 à 11:21

Vous pouvez valider vos chaînes en ne vérifiant que les parenthèses comme ceci, ce n'est pas extrêmement efficace car il itère toujours chaque chaîne mais cela peut être optimisé.

#include <list>
#include <iostream>
#include <string>

bool validate(std::string s)
{
    std::list<char> parens;
    for (auto c : s) {
        if (c == '(' || c == '[' || c == '{') {
            parens.push_back(c);
        }

        if (c == ')' && parens.back() == '(') {
            parens.pop_back();
        } else if (c == ']' && parens.back() == '[') {
            parens.pop_back();
        } else if (c == '}' && parens.back() == '{') {
            parens.pop_back();
        }
    }
    return parens.size() == 0;
}


int main()
{
  std::list<std::string> l {
    "{{0, 1},   (2,    3)}",
    "{{4,  5, {6, 7}}" // Ill-formed, so need to throw an excpetion.
  };

  for (auto s : l) {
      std::cout << "'" << s << "' is " << (validate(s) ? "" : "not ") << "valid" << std::endl;
  }

  return 0;
}

La sortie du code ci-dessus est la suivante:

'{{0, 1},   (2,    3)}' is valid
'{{4,  5, {6, 7}}' is notvalid

ÉDITER:

Cette version devrait être plus efficace car elle retourne juste après avoir remarqué qu'une chaîne n'est pas valide.

bool validate(std::string s)
{
    std::list<char> parens;
    for (auto c : s) {
        if (c == '(' || c == '[' || c == '{') {
            parens.push_back(c);
        }

        if (c == ')') {
            if (parens.back() != '(') {
                return false;
            }
            parens.pop_back();
        } else if (c == ']') {
            if (parens.back() != '[') {
                return false;
            }
            parens.pop_back();
        } else if (c == '}') {
            if (parens.back() != '{') {
                return false;
            }
            parens.pop_back();
        }
    }
    return parens.size() == 0;
}
1
SilvanoCerza 20 juin 2019 à 11:01

Votre regex analyse parfaitement un seul élément de la carte. Je vous suggère de valider la chaîne avant de créer la carte et de la remplir avec des éléments analysés.

Utilisons une version légèrement améliorée de votre regex:

[\[\{\(](([\[\{\(](\d+),(\s*)(\d+)[\)\}\]])(,?)(\s*))*[\)\}\]]

Il correspond à la chaîne entière si elle est valide: elle commence par [\[\{\(], se termine par [\)\}\]], contient plusieurs (ou zéro) motif d'élément de carte à l'intérieur suivi de , et multiple (ou zéro ) les espaces.

Voici le code:

#include <list>
#include <map>
#include <regex>
#include <sstream>
#include <iostream>

void f(const std::string& s) {
  // part 1: validate string
  std::regex valid_pattern {"[\\[\\{\\(](([\\[\\{\\(](\\d+),(\\s*)(\\d+)[\\)\\}\\]])(,?)(\\s*))*[\\)\\}\\]]"};
  auto valid_begin = std::sregex_iterator(s.begin(), s.end(), valid_pattern);
  auto valid_end = std::sregex_iterator();
  if (valid_begin == valid_end || valid_begin->str().size() != s.size ()) {
    std::stringstream res;
    res << "String \"" << s << "\" doesn't satisfy pattern!";
    throw std::invalid_argument (res.str ());
  } else {
    std::cout << "String \"" << s << "\" satisfies pattern!" << std::endl;
  }

  // part 2: parse map elements
  std::map<int, int> m;
  std::regex pattern {"[\\[\\{\\(](\\d+),\\s*(\\d+)[\\)\\}\\]]"};
  auto parsed_begin = std::sregex_iterator(s.begin(), s.end(), pattern);
  auto parsed_end = std::sregex_iterator();
  for (auto x = parsed_begin; x != parsed_end; ++x) {
    m[std::stoi(x->str(1))] = std::stoi(x->str(2));
  }

  std::cout << "Number of parsed elements: " << m.size() << '\n';
}

int main() {
  std::list<std::string> l {
      "{}",
      "[]",
      "{{0, 153}, (2, 3)}",
      "{{0,      153},   (2,    3)}",
      "{[0, 153],           (2, 3), [154, 33]   }",
      "{[0, 153],           (2, 3), [154, 33]   ", // Ill-formed, so need to throw an exception.
      "{{4,  5, {6, 7}}", // Ill-formed, so need to throw an exception.
      "{{4,  5, {x, 7}}" // Ill-formed, so need to throw an exception.
  };
  for (const auto &x : l) {
    try {
      f(x);
    }
    catch (std::invalid_argument &ex) {
      std::cout << ex.what () << std::endl;
    }
    std::cout << std::endl;
  }
}

Voici la sortie:

String "{}" satisfies pattern!
Number of parsed elements: 0

String "[]" satisfies pattern!
Number of parsed elements: 0

String "{{0, 153}, (2, 3)}" satisfies pattern!
Number of parsed elements: 2

String "{{0,      153},   (2,    3)}" satisfies pattern!
Number of parsed elements: 2

String "{[0, 153],           (2, 3), [154, 33]   }" satisfies pattern!
Number of parsed elements: 3

String "{[0, 153],           (2, 3), [154, 33]   " doesn't satisfy pattern!

String "{{4,  5, {6, 7}}" doesn't satisfy pattern!

String "{{4,  5, {x, 7}}" doesn't satisfy pattern!

PS Il n'a qu'un seul défaut. Il ne vérifie pas que le crochet de fermeture correspondant est égal à celui d'ouverture. Donc, cela correspond à ceci: {], {(1,2]) etc. Si cela ne vous convient pas, le moyen le plus simple de résoudre ce problème est d'ajouter un code de validation supplémentaire avant de mettre la paire analysée dans la carte.

PPS Si vous êtes en mesure d'éviter les expressions régulières, votre problème pourrait être résolu beaucoup plus efficacement avec une analyse de chaîne unique pour chaque chaîne. @SilvanoCerza a proposé une implémentation pour ce cas.

0
gimme_danger 20 juin 2019 à 09:32

Puisque Han a mentionné dans ses commentaires qu'il aimerait attendre d'autres idées, je vais montrer une solution supplémentaire.

Et comme tout le monde avant, je pense que c'est la solution la plus appropriée :-)

De plus, je déballerai le "gros marteau", et parlerai de "langues" et de "grammaires" et, euh oh, de Chomsky Hierachy.

Tout d'abord, une réponse très simple: les expressions régulières pures ne peuvent pas compter. Ainsi, ils ne peuvent pas vérifier les accolades correspondantes, comme 3 accolades ouvertes et 3 accolades fermées.

Ils sont principalement implémentés sous le nom de DFA (Deterministic Finite Automaton), également connu sous le nom de FSA (Finite State Automaton). L'une des propriétés pertinentes ici est qu'ils ne connaissent que leur état actuel. Ils ne peuvent pas "se souvenir" des états précédents. Ils n'ont pas de mémoire.

Les langues qu'ils peuvent produire sont des «langues régulières». Dans la hiérarchie de Chomsky, la grammaire pour produire une telle langue régulière est de Type-3. Et des "expressions régulières" peuvent être utilisées pour produire de tels langages.

Cependant, il existe des extensions d'expressions régulières qui peuvent également être utilisées pour faire correspondre des accolades équilibrées. Voir ici: Expression régulière pour correspondre aux parenthèses équilibrées

Mais ce ne sont pas des expressions régulières selon la définition originale.

Ce dont nous avons vraiment besoin, c'est d'une grammaire Chomsky-Type-2. Une soi-disant grammaire sans contexte. Et cela sera généralement implémenté avec un automate de refoulement. Une pile est utilisée pour stocker un état supplémentaire. C'est la "mémoire" que les expressions régulières n'ont pas.

Donc, si nous voulons vérifier la syntaxe d'une expression donnée, comme dans votre cas l'entrée pour un std :: map, nous pouvons définir une grammaire ultra-simple et analyser la chaîne d'entrée en utilisant l'approche classique classique: A Shift / Reduce Analyseur.

Plusieurs étapes sont nécessaires: Premièrement, le flux d'entrée sera divisé en Lexems od Tokens. Ceci est généralement effectué par un soi-disant Lexer ou Scanner. Vous trouverez toujours une fonction comme getNextToken ou similaire. Ensuite, les jetons seront déplacés sur la pile. Le Stack Top sera comparé aux productions de la grammaire. S'il y a correspondance avec le côté droit de la production, les éléments de la pile seront remplacés par le no-terminal sur le côté gauche des productions. Cette procédure sera répétée jusqu'à ce que le symbole de début de la grammaire soit atteint (ce qui signifie que tout était OK) ou qu'une erreur de syntaxe soit trouvée.

Concernant votre question:

Comment analyser une chaîne dans std :: map et valider son format?

Je le diviserais en 2 tâches.

  1. Analyser la chaîne pour valider le format
  2. Si la chaîne est valide, placez les données dans une carte

La tâche 2 est simple et typiquement une ligne en utilisant un std :: istream_iterator.

La tâche 1 nécessite malheureusement un analyseur de réduction de décalage. C'est un peu complexe.

Dans le code ci-dessous, je montre une solution possible. Remarque: cela peut être optimisé en utilisant Token avec des attributs. Les attributs seraient un nombre entier et le type de l'accolade. Le jeton avec des attributs serait stocké sur la pile d'analyse. Avec cela, nous pourrions éliminer le besoin d'avoir des productions pour tous les types d'accolades et nous pourrions remplir la carte dans l'analyseur (dans l'opération de réduction de l'un des "{Token :: Pair, {Token :: B1open, Token :: Integer, Token :: Virgule, Token :: Integer, Token :: B1close}} "

Veuillez consulter le code ci-dessous:

#include <iostream>
#include <iterator>
#include <sstream>
#include <map>
#include <vector>
#include <algorithm>

// Tokens:  Terminals and None-Terminals
enum class Token { Pair, PairList, End, OK, Integer, Comma, B1open, B1close, B2open, B2close, B3open, B3close };

// Production type for Grammar
struct Production { Token nonTerminal; std::vector<Token> rightSide; };

// The Context Free Grammar CFG
std::vector<Production>    grammar
{
       {Token::OK, { Token::B1open, Token::PairList, Token::B1close } },
       {Token::OK, { Token::B2open, Token::PairList, Token::B2close } },
       {Token::OK, { Token::B3open, Token::PairList, Token::B3close } },
       {Token::PairList, { Token::PairList, Token::Comma, Token::Pair}    },
       {Token::PairList, { Token::Pair } },
       {Token::Pair, { Token::B1open, Token::Integer, Token::Comma, Token::Integer, Token::B1close} },
       {Token::Pair, { Token::B2open, Token::Integer, Token::Comma, Token::Integer, Token::B2close} },
       {Token::Pair, { Token::B3open, Token::Integer, Token::Comma, Token::Integer, Token::B3close} }
};
// Helper for translating brace characters to Tokens
std::map<const char, Token> braceToToken{
 {'(',Token::B1open},{'[',Token::B2open},{'{',Token::B3open},{')',Token::B1close},{']',Token::B2close},{'}',Token::B3close},
};

// A classical    SHIFT - REDUCE  Parser
class Parser
{
public:
    Parser() : parseString(), parseStringPos(parseString.begin()) {}
    bool parse(const std::string& inputString);
protected:
    // String to be parsed
    std::string parseString{}; std::string::iterator parseStringPos{}; // Iterator for input string

    // The parse stack for the Shift Reduce Parser
    std::vector<Token> parseStack{};

    // Parser Step 1:   LEXER    (lexical analysis / scanner)
    Token getNextToken();
    // Parser Step 2:   SHIFT
    void shift(Token token) { parseStack.push_back(token); }
    // Parser Step 3:   MATCH / REDUCE
    bool matchAndReduce();
};

bool Parser::parse(const std::string& inputString)
{
    parseString = inputString; parseStringPos = parseString.begin(); parseStack.clear();
    Token token{ Token::End };
    do   // Read tokens untils end of string
    {
        token = getNextToken();     // Parser Step 1:   LEXER    (lexical analysis / scanner)                    
        shift(token);               // Parser Step 2:   SHIFT
        while (matchAndReduce())    // Parser Step 3:   MATCH / REDUCE
            ; // Empty body
    } while (token != Token::End);  // Do until end of string reached
    return (!parseStack.empty() && parseStack[0] == Token::OK);
}

Token Parser::getNextToken()
{
    Token token{ Token::End };
    // Eat all white spaces
    while ((parseStringPos != parseString.end()) && std::isspace(static_cast<int>(*parseStringPos))) {
        ++parseStringPos;
    }
    // Check for end of string
    if (parseStringPos == parseString.end()) {
        token = Token::End;
    }
    // Handle digits
    else if (std::isdigit(static_cast<int>(*parseStringPos))) {
        while ((((parseStringPos + 1) != parseString.end()) && std::isdigit(static_cast<int>(*(parseStringPos + 1)))))        ++parseStringPos;
        token = Token::Integer;
    }
    // Detect a comma
    else if (*parseStringPos == ',') {
        token = Token::Comma;
        // Else search for all kind of braces
    }
    else {
        std::map<const char, Token>::iterator foundBrace = braceToToken.find(*parseStringPos);
        if (foundBrace != braceToToken.end()) token = foundBrace->second;
    }
    // In next function invocation the next string element will be checked
    if (parseStringPos != parseString.end())
        ++parseStringPos;

    return token;
}


bool Parser::matchAndReduce()
{
    bool result{ false };
    // Iterate over all productions in the grammar
    for (const Production& production : grammar) {
        if (production.rightSide.size() <= parseStack.size()) {
            // If enough elements on the stack, match the top of the stack with a production
            if (std::equal(production.rightSide.begin(), production.rightSide.end(), parseStack.end() - production.rightSide.size())) {
                // Found production: Reduce
                parseStack.resize(parseStack.size() - production.rightSide.size());
                // Replace right side of production with left side
                parseStack.push_back(production.nonTerminal);
                result = true;
                break;
            }
        }
    }
    return result;
}

using IntMap = std::map<int, int>;
using IntPair = std::pair<int, int>;

namespace std {
    istream& operator >> (istream& is, IntPair& intPair)    {
        return is >> intPair.first >> intPair.second;
    }
    ostream& operator << (ostream& os, const pair<const int, int>& intPair) {
        return os << intPair.first << " --> " << intPair.second;
    }
}

int main()
{   // Test Data. Test Vector with different strings to test
    std::vector <std::string> testVector{
        "({10, 1 1},   (2,  3) , [5 ,6])",
        "({10, 1},   (2,  3) , [5 ,6])",
        "({10, 1})",
        "{10,1}"
    };
    // Define the Parser
    Parser parser{};
    for (std::string& test : testVector)
    {   // Give some nice info to the user
        std::cout << "\nChecking '" << test << "'\n";
        // Parse the test string and test, if it is valid
        bool inputStringIsValid = parser.parse(test);
        if (inputStringIsValid) {               // String is valid. Delete everything but digits
            std::replace_if(test.begin(), test.end(), [](const char c) {return !std::isdigit(static_cast<int>(c)); }, ' ');
            std::istringstream iss(test);       // Copy string with digits int a istringstream, so that we can read with istream_iterator
            IntMap intMap{ std::istream_iterator<IntPair>(iss),std::istream_iterator<IntPair>() };
            // Present the resulting data in the map to the user
            std::copy(intMap.begin(), intMap.end(), std::ostream_iterator<IntPair>(std::cout, "\n"));
        } else {
            std::cerr << "***** Invalid input data\n";
        }
    }
    return 0;
}

J'espère que ce n'est pas trop complexe. Mais c'est la solution correcte «mathématique». S'amuser . . .

3
Armin Montigny 21 juin 2019 à 18:27