Так как Хан упомянул в своих комментариях, что он хотел бы дождаться дальнейших идей, я покажу дополнительное решение.
И, как и все ранее, я думаю, что это наиболее подходящее решение: -)
Кроме того, я распакую "большой молоток" и поговорю о "языках" и "грамматике" иО, Хомский Иерачи.
Сначала очень простой ответ: чистые регулярные выражения не могут рассчитывать.Таким образом, они не могут проверять совпадающие фигурные скобки, например, 3 открытых и 3 закрытых.
Они в основном реализованы как DFA (детерминированный конечный автомат), также известный как FSA (конечный автомат).Одним из важных свойств здесь является то, что они знают только о своем текущем состоянии.Они не могут «помнить» предыдущие состояния.У них нет памяти.
Языки, которые они могут создавать, являются так называемыми "обычными языками".В иерархии Хомского грамматика для создания такого регулярного языка относится к типу 3.И «регулярные выражения» могут быть использованы для создания таких языков.
Однако существуют расширения для регулярных выражений, которые также можно использовать для сопоставления сбалансированных фигурных скобок.См. Здесь: Регулярное выражение для соответствия сбалансированным скобкам
Но это не регулярное выражение в соответствии с исходным определением.
Что нам действительно нужно, так это Chomsky-Type-2 грамматики.Так называемая контекстно-свободная грамматика.И это обычно будет реализовано с помощью pushdown-автомата.Стек используется для хранения дополнительного состояния.Это та «память», которой нет в регулярных выражениях.
Итак, если мы хотим проверить синтаксис данного выражения, как в вашем случае вход для std :: map, мы можем определитьочень простая грамматика и синтаксический анализ входной строки с использованием стандартного классического подхода: синтаксический анализатор сдвига / уменьшения.
Необходимо выполнить несколько шагов: сначала входной поток будет разбит на лексемы и токены.Обычно это делается так называемым Lexer или сканером.Вы всегда найдете функцию вроде getNextToken или аналогичную.Тогда жетоны будут перемещены в стек.Stack Top будет сопоставлен с продукцией в грамматике.Если есть совпадение с правой стороной производства, элементы в стеке будут заменены нетерминалом на левой стороне производства.Эта процедура будет повторяться до тех пор, пока не будет нажата начальная буква грамматики (что означает, что все в порядке) или не будет найдена синтаксическая ошибка.
Относительно вашего вопроса:
Какразобрать строку в std :: map и проверить ее формат?
Я бы разделил ее на 2 задачи.
- Разобрать строку для проверки формата
- Если строка верна, поместите данные в карту
Задача 2 простая и обычно однострочная с использованием std :: istream_iterator.
Задача 1, к сожалениюнужен сдвиг-уменьшение-парсер.Это немного сложно.
В прилагаемом коде ниже я покажу одно возможное решение.Обратите внимание: это можно оптимизировать с помощью токена с атрибутами.Атрибутами будут целое число и тип фигурной скобки.Токен с атрибутами будет храниться в стеке разбора.С этим мы могли бы устранить необходимость иметь продукцию для всех видов фигурных скобок, и мы могли бы заполнить карту в синтаксическом анализаторе (в операции сокращения одного из «{Token :: Pair, {Token :: B1open, Token :: Integer,Token :: Comma, Token :: Integer, Token :: B1close}} ”
Пожалуйста, смотрите код ниже:
#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;
}
Я надеюсь, что это не слишком сложно. Но это«математическое» правильное решение. Веселитесь.