online compiler and debugger for c/c++

//C++17 #include <iostream> #include <string> #include <algorithm> #include <optional> #include <cassert> #include <iomanip> struct WildCardParser { //? Любой отдельный символ //* Ноль или более символов //# Любая однозначная цифра (0-9) //[charlist] Любой отдельный символ в charlist //[!charlist] Любой отдельный символ, отсутствующий в charlist //To match the special characters left bracket ([), question mark (?), number sign (#) //and asterisk (*), enclose them in brackets. The right bracket (]) //can't be used within a group to match itself, but it can be used outside a group as an individual character. constexpr static bool ShowDebugOutput=!true; constexpr static std::wstring_view DebugPrefix=L" dbg: "; constexpr static wchar_t WCHAR_exclamation{L'!'}; constexpr static wchar_t WCHAR_openbrace{L'['}; constexpr static wchar_t WCHAR_closebrace{L']'}; constexpr static wchar_t WCHAR_hyphen{L'-'}; constexpr static wchar_t WCHAR_numbersign{L'#'}; constexpr static wchar_t WCHAR_asterisk{L'*'}; constexpr static wchar_t WCHAR_question{L'?'}; constexpr static wchar_t WCHAR_zero{L'0'}; constexpr static wchar_t WCHAR_nine{L'9'}; //информация о пропарсенных квадратных скобках struct s_SquareBracketsInfo { private: //#todo - для оптимизации можно попробовать заменить строку массивом, тогда уберётся работа с кучей std::wstring m_CharsList;//список символов, раскрытый из квадратных скобок size_t m_ClosingBracketPos{};//позиция закрывающей скобки bool m_Inverted{};//флаг инверсии из начала скобок private: //для оптимизации: предыдущий распарсенный текст. //Если он такой же, то заново парсить не нужно, всё уже готово std::optional<std::wstring_view> m_lastParsedText; public: bool IsSetEmpty()const noexcept { return m_CharsList.empty(); } bool TestChar(const wchar_t c)const noexcept { const bool contains=(m_CharsList.find(c)!=m_CharsList.npos); if(m_Inverted) { return !contains; } else { return contains; } } bool Parse(const std::wstring_view text) { if(m_lastParsedText) { if(m_lastParsedText->size()==text.size()) { if(m_lastParsedText->data()==text.data()) { if constexpr(ShowDebugOutput)std::wcout<<DebugPrefix<<L"m_lastParsedText reused\n"; return true; } } } const auto res=Parse__(text); if(res) { //запоминаем последний парсённый текст m_lastParsedText=text; //if constexpr(ShowDebugOutput)std::wcout<<DebugPrefix<<L"m_lastParsedText saved\n"; assert(m_lastParsedText); assert(!m_lastParsedText->empty()); assert(m_lastParsedText->size()>m_ClosingBracketPos); assert((*m_lastParsedText)[m_ClosingBracketPos]==WCHAR_closebrace); } else { //поскольку состояние могло меняться, забываем последний текст m_lastParsedText.reset(); if constexpr(ShowDebugOutput)std::wcout<<DebugPrefix<<L"m_lastParsedText reset\n"; } return res; } size_t PosOfClosingBracket()const noexcept { return m_ClosingBracketPos; } private: //заполнение списка символов из квадратных скобок //text - начинается с первого символа после открывающей скобки bool Parse__(std::wstring_view text) { //тут не производится оптимизация по удалению повторов [ababa]. //Предполагается, что юзер сам себе не враг, а если добавлять алгоритм //удаления повторов - это будет постоянная дополнительная нагрузка if(text.empty())return false; m_CharsList.clear(); m_ClosingBracketPos={}; m_Inverted={}; //справа ограничиваемся по закрывающей скобке { const auto pos=text.find_first_of(WCHAR_closebrace); if(pos==text.npos)return false; text=text.substr(0, pos); m_ClosingBracketPos=pos; } //флаг инверсии if(!text.empty() && text.front()==WCHAR_exclamation) { //проверка на одинокий восклицательный знак if(text.size()==1) { m_CharsList.push_back(WCHAR_exclamation); return true; } m_Inverted=true; text.remove_prefix(1); } //сейчас text такой: //begin,front - первый символ после открывающей скобки или инвертирующего знака //back - символ перед закрывающей скобкой //end - закрывающая скобка auto text_cur=text.cbegin(); auto const text_end=text.cend(); while(text_cur!=text_end) { //text_cur - текущий символ //если следующий символ это минус, if(const auto hyphen=text_cur+1; hyphen!=text_end && *hyphen==WCHAR_hyphen) { //то после минуса тоже должен быть какой-то символ if(const auto second=hyphen+1; second!=text_end) { //обработка X-Z, сейчас находимся на X auto c1=*text_cur; auto c2=*second; if(c1>c2)std::swap(c1, c2); for(auto c=c1; c<=c2; ++c)m_CharsList.push_back(c); //идём дальше //обрабатываем ситуацию с трамваем a-b-c //если после second лежит минус const auto next_after_second=second+1; if(next_after_second!=text_end && *next_after_second==WCHAR_hyphen) { text_cur=second; } else { text_cur=second+1; } continue; } } //один символ кладём в список m_CharsList.push_back(*text_cur); text_cur++; } return true; } }; static bool Match(const std::wstring_view text, const std::wstring_view wc) { //информация о пропарсенных квадратных скобках s_SquareBracketsInfo SBInfo; return Match_recursed(text, wc, SBInfo); } private: static bool Match_recursed(const std::wstring_view text, const std::wstring_view wc, s_SquareBracketsInfo& SBInfo) { auto wc_cur=wc.cbegin(); auto const wc_end=wc.cend(); auto text_cur=text.cbegin(); auto const text_end=text.cend(); while(wc_cur!=wc_end) { if(text_cur==text_end) { //завершающие звёздочки игнорируем if(*wc_cur==WCHAR_asterisk) { ++wc_cur; continue; } //завершающие пустые квадратные скобки игнорируем if(*wc_cur==WCHAR_openbrace && (wc_cur+1)!=wc_end && *(wc_cur+1)==WCHAR_closebrace) { wc_cur+=2; continue; } return false; } switch(*wc_cur) { default: { //любой другой символ - должен совпасть с текстовым if(*wc_cur == *text_cur) { ++wc_cur; ++text_cur; } else { return false; } }break; case WCHAR_question: { ++wc_cur; ++text_cur; }break; case WCHAR_numbersign: { if(WCHAR_zero <= *text_cur && *text_cur<=WCHAR_nine) { ++wc_cur; ++text_cur; } else { return false; } }break; case WCHAR_openbrace: { const auto wc_next=wc_cur+1; if(!SBInfo.Parse({&*wc_next, size_t(wc_end-wc_next)})) { //ошибка парсинга квадратных скобок return false; } if(SBInfo.IsSetEmpty()) { //[] wc_cur=wc_next+SBInfo.PosOfClosingBracket()+1; } else if(SBInfo.TestChar(*text_cur)) { //символ строки есть в списке wc_cur=wc_next+SBInfo.PosOfClosingBracket()+1; ++text_cur; } else { return false; } }break; case WCHAR_asterisk: { const auto wc_next=wc_cur+1; if(wc_next==wc_end) { //следующего символа в маске нет, поэтому всё остальное - матчится return true; } //нужно выяснить, сколько символов возьмёт звёздочка из последующей строки. //Используем для этого рекурсию auto text_lef=text_end; while(1) { //предполагаем, что звёздочка забирает [text_lef...text_end). //Тогда эта часть строки должна сматчится с оставшейся частью маски if(Match_recursed({&*text_lef, size_t(text_end-text_lef)}, {&*wc_next, size_t(wc_end-wc_next)}, SBInfo)) { return true; } if(text_lef==text_cur) { return false; } text_lef--; } }break; } } //строка и маска должны быть дочитаны полностью return wc_cur==wc_end && text_cur==text_end; } }; int main() { struct s_test { const std::wstring_view string; const std::wstring_view mask; bool result{}; s_test()noexcept=default; s_test(const s_test&)noexcept=default; s_test(s_test&&)noexcept=default; s_test& operator=(const s_test&)noexcept=default; s_test& operator=(s_test&&)noexcept=default; s_test(const std::wstring_view string, const std::wstring_view mask, const std::wstring result) :string{string}, mask{mask} { this->result=(result==L"True"); } s_test(const std::wstring_view string, const std::wstring_view mask, void* result) :string{string}, mask{mask} { this->result=false; } std::wstring quoted_string()const { return L'"'+std::wstring(string)+L'"'; } std::wstring quoted_mask()const { return L'"'+std::wstring(mask)+L'"'; } }; const std::vector<s_test> tests { {L"XYXZZXYXYXZZXY", L"*X*X?*X*X?",L"True"}, {L"aBBBa", L"a*a",L"True"}, {L"F" , L"[A-Z]" ,L"True"}, {L"F" , L"[!A-Z]",NULL}, {L"a2a" , L"a#a", L"True"}, {L"aM5b" , L"a[L-P]#[!c-e]", L"True"}, {L"BAT123khg" , L"B?T*", L"True"}, {L"CAT123khg" , L"B?T*",NULL}, {L"ab" , L"a*b",L"True"}, {L"a*b" , L"a [*]b", NULL}, {L"axxxxxb" , L"a [*]b",NULL}, {L"a [xyz" , L"a [[]*", L"True"}, {L"aM5b" , L"a*?b", L"True"}, {L"aM5b" , L"a*[1-4-9][!c-e]", L"True"}, {L"aM55b" , L"a*[1-4-9][!c-e]", L"True"}, {L"aM55b" , L"a*[1-45-9][!c-e]", L"True"}, {L"aM5b" , L"*#[!c-e]", L"True"}, {L"5*", L"5[*]", L"True"}, {L"?n", L"[?]n", L"True"}, {L"a", L"[a-cdf]", L"True"}, {L"b", L"[a-cdf]", L"True"}, {L"c", L"[a-cdf]", L"True"}, {L"d", L"[a-cdf]", L"True"}, {L"f", L"[a-cdf]", L"True"}, {L"-", L"[-acdf]", L"True"}, {L"a", L"[-acdf]", L"True"}, {L"c", L"[-acdf]", L"True"}, {L"d", L"[-acdf]", L"True"}, {L"f", L"[-acdf]", L"True"}, {L"[", L"[ [ ]", L"True"}, {L"]", L"]", L"True"}, {L"abc_d", L"abc[_]d*", L"True"}, {L"abc_de", L"abc[_]d*", L"True"}, {L"abcd", L"abc[def]", L"True"}, {L"abce", L"abc[def]", L"True"}, {L"abcf", L"abc[def]", L"True"}, {L"abcdef", L"abc*[de]ef", L"True"}, {L"abcyef", L"abc[xz]ef", NULL}, {L"abcxef", L"abc[xz]ef", L"True"}, {L"abcyef", L"abc[!xz]ef", L"True"}, {L"abcxef", L"abc[!xz]ef", NULL}, {L"ac5c5b", L"a*[1-56-9][!c-e]", L"True"}, {L"", L"", L"True"}, {L"", L"*", L"True"}, {L"", L"[]", L"True"}, {L"", L"[!]", NULL}, {L"", L"[]*", L"True"}, {L"", L"[!]*", NULL}, {L"1", L"[!]*", NULL}, {L"1", L"[]*", L"True"}, {L"1", L"[!]*", NULL}, {L"1", L"[!]", NULL}, {L"1", L"*[!]", NULL}, {L"1", L"*[]", L"True"}, {L"1", L"#[]", L"True"}, {L"1", L"#[!]", NULL}, {L"12", L"#[!]", NULL}, {L"12", L"#[!]*", NULL}, {L"123", L"*[!]*", NULL}, {L"1!3", L"*[!]*", L"True"}, {L"!", L"*[!]*", L"True"}, {L"!", L"[!]", L"True"}, {L"!a", L"*[!a]*", L"True"}, {L"!a", L"[!a]*", L"True"}, {L"!a", L"*[!a]", NULL}, {L"!a", L"[!a]", NULL}, {L"a", L"[!a]", NULL}, {L"b", L"[!a]", L"True"}, {L"2", L"#[]", L"True"}, {L"*", L"[*]", L"True"}, {L"1", L"[*]", NULL}, {L"!", L"[!-!]", NULL}, {L"1", L"[!-!]", L"True"}, {L"!", L"[-!]", L"True"}, {L"!", L"[!-]", L"True"}, {L"-", L"[!-]", NULL}, {L"-", L"[-]", L"True"}, {L"***", L"*[*]*", L"True"}, {L"???", L"?[?]?", L"True"}, {L"###", L"#[#]#", NULL}, {L"[[[[[", L"[[]?*[[]", L"True"}, {L"a [xyz" , L"a [*", NULL}, }; size_t wid_of_string{}; size_t wid_of_mask{}; for(const auto& test:tests) { wid_of_string=(std::max)(wid_of_string, test.string.size()); wid_of_mask =(std::max)(wid_of_mask , test.mask .size()); } size_t errors_count{}; for(const auto& test:tests) { if(test.result==WildCardParser::Match(test.string, test.mask)) { std::wcout<<L"ok : "; } else { std::wcout<<L"error: "; errors_count++; } using std::left, std::setw; std::wcout<<L" string "<<left<<setw(wid_of_string+size_t(2))<<test.quoted_string(); std::wcout<<L" LIKE " <<left<<setw(wid_of_mask +size_t(2))<<test.quoted_mask() ; std::wcout<<" must be "<<(test.result?L"true":L"false"); std::wcout<<'\n'; if constexpr(WildCardParser::ShowDebugOutput)std::wcout<<L"\n"; } std::wcout<<L"\nerrors_count="<<errors_count<<L"\n"; return 0; }