online compiler and debugger for c/c++

#include <iostream> #include <string> #include <unordered_map> #include <vector> #include <algorithm> #include <optional> #include <cassert> #include <future> //? Любой отдельный символ //* Ноль или более символов //# Любая однозначная цифра (0-9) //[charlist] Любой отдельный символ в charlist //[!charlist] Любой отдельный символ, отсутствующий в charlist //Symbol Meaning //LIKE '5[*]' 5* //LIKE '[?]n' ?n //LIKE '[a-cdf]' a, b, c, d, or f //LIKE '[-acdf]' -, a, c, d, or f //LIKE '[ [ ]' [ //LIKE ']' ] //LIKE 'abc[_]d*' abc_d and abc_de //LIKE 'abc[def]' abcd, abce, and abcf constexpr bool MatchWildcardAndText_showDebugOutput = !true; constexpr std::wstring_view MatchWildcardAndText_DebugPrefix = L" dbg: "; bool MatchWildcardAndText(const std::wstring_view text, const std::wstring_view wc) { auto wc_cur = wc.cbegin(); auto wc_end = wc.cend(); auto text_cur = text.cbegin(); auto text_end = text.cend(); //информация о пропарсенных квадратных скобках 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 TestChar(const char 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 (MatchWildcardAndText_showDebugOutput)std::wcout << MatchWildcardAndText_DebugPrefix << L"m_lastParsedText reused\n"; return true; } } } auto res = Parse__(text); if (res) { //запоминаем последний парсённый текст m_lastParsedText = text; //if constexpr(MatchWildcardAndText_showDebugOutput)std::wcout<<MatchWildcardAndText_DebugPrefix<<L"m_lastParsedText saved\n"; assert(m_lastParsedText); assert(!m_lastParsedText->empty()); assert(m_lastParsedText->size() > m_ClosingBracketPos); assert((*m_lastParsedText)[m_ClosingBracketPos] == L']'); } else { //поскольку состояние могло меняться, забываем последний текст m_lastParsedText.reset(); if constexpr (MatchWildcardAndText_showDebugOutput)std::wcout << MatchWildcardAndText_DebugPrefix << L"m_lastParsedText reset\n"; } return res; } size_t PosOfClosingBracket()const noexcept { return m_ClosingBracketPos; } private: //заполнение списка символов из квадратных скобок //text - начинается с первого символа после открывающей L'[' bool Parse__(std::wstring_view text) { //тут не производится оптимизация по удалению повторов [ababa]. //Предполагается, что юзер сам себе не враг, а если добавлять алгоритм //удаления повторов - это будет постоянная дополнительная нагрузка m_CharsList.clear(); m_ClosingBracketPos = {}; m_Inverted = {}; m_CharsList.reserve(256); if (text.empty())return false; //справа ограничиваемся по закрывающей скобке { const auto pos = text.find_first_of(L']'); if (pos == text.npos)return false; text = text.substr(0, pos); m_ClosingBracketPos = pos; } //флаг инверсии if (!text.empty() && text.front() == L'!') { m_Inverted = true; text.remove_prefix(1); } //сейчас text такой: //begin,front - первый символ после L'[' или L"[!" //back - символ перед L']' //end - L']' auto text_cur = text.cbegin(); auto text_end = text.cend(); while (text_cur != text_end) { //text_cur - текущий символ //если следующий символ это минус, if (auto hyphen = text_cur + 1; hyphen != text_end && *hyphen == L'-') { //то после минуса тоже должен быть какой-то символ if (auto second = hyphen + 1; second != text_end) { //обработка X-Z, сейчас находимся на X char c1 = *text_cur; char c2 = *second; if (c1 > c2)std::swap(c1, c2); for (char c = c1; c <= c2; ++c)m_CharsList.push_back(c); //идём дальше text_cur = second + 1; continue; } } //один символ кладём в список m_CharsList.push_back(*text_cur); text_cur++; } return true; } }; s_SquareBracketsInfo SBInfo; while (wc_cur != wc_end) { if (text_cur == text_end) { //завершающие звёздочки игнорируем if (*wc_cur == L'*') { ++wc_cur; continue; } return false; } switch (*wc_cur) { default: { //любой другой символ - должен совпасть с текстовым if (*wc_cur == *text_cur) { ++wc_cur; ++text_cur; } else { return false; } }break; case L'?': { ++wc_cur; ++text_cur; }break; case L'#': { if (L'0' <= *text_cur && *text_cur <= L'9') { ++wc_cur; ++text_cur; } else { return false; } }break; case L'*': { auto wc_next = wc_cur + 1; bool done{}; do { if (wc_next != wc_end) { switch (*wc_next) { default: { //любой другой символ - должен совпасть с текстовым if (*wc_next == *text_cur) { //совпал, поэтому звёздочку считаем завершённой ++wc_cur; done = true; } else { //звёздочка забирает один символ из текста ++text_cur; } }break; case L'?': { //звезда сматчилась с пустотой ++wc_cur; done = true; }break; case L'#': { if (L'0' <= *text_cur && *text_cur <= L'9') { //звезда сматчилась с пустотой ++wc_cur; done = true; } }break; case L'*': { //звезда сматчилась с пустотой ++wc_cur; //завершение не делаем, так как идём обрабатывать звезду //done=true; }break; case L'[': { auto wc_past_next = wc_next + 1; if (wc_past_next != wc_end && SBInfo.Parse({ &*wc_past_next, size_t(wc_end - wc_past_next) })) { //дальше лежат корректные квадратные скобки ++wc_cur; done = true; } else { //считаем обычным символом //любой другой символ - должен совпасть с текстовым if (*wc_next == *text_cur) { ++wc_cur; done = true; } } }break; } } else { //следующего символа в маске нет, поэтому всё остальное - матчится return true; } } while (!done && wc_cur != wc_end && text_cur != text_end); }break; case L'[': { auto wc_next = wc_cur + 1; if (wc_next != wc_end && SBInfo.Parse({ &*wc_next, size_t(wc_end - wc_next) })) { //символ строки должен лежать в списке if (SBInfo.TestChar(*text_cur)) { wc_cur = wc_next + SBInfo.PosOfClosingBracket() + 1; ++text_cur; } else { return false; } } else { //считаем обычным символом //любой другой символ - должен совпасть с текстовым if (*wc_cur == *text_cur) { ++wc_cur; ++text_cur; } else { return false; } } }break; } } //#todo - эти три строки можно записать с одним return if (wc_cur != wc_end) return false; if (text_cur != text_end) return false; return true; } bool check(wchar_t* s, wchar_t* p) { wchar_t* rs = 0, * rp=0; while (1) if (*p == L'*') rs = s, rp = ++p; else if (!*s) return !*p; else if (*s == *p || *p == L'?') ++s, ++p; else if (rs) s = ++rs, p = rp; else return false; } bool LikeVB(const wchar_t* s, const wchar_t* p) { const wchar_t* rs = 0, * rp = 0; while (1) { if (*p == L'[') { bool b = false, res = false; if (*(++p) == L'!') { b = true; ++p; } while (*p != L']') { if (*p == L'\0') { throw 93; }//если забыли закрывающую скобку//return false; if (*(p + 1) == L'-' && *(p + 2) != L']')//если есть диапазон ... - ... { //if (*(p+2) == L'\0') { return false; }//если забыли закрывающую скобку if (*s >= *p && *s <= *(p + 2)) { if (b) { return false; }//если таких символов не должно быть else { res = true; }//если нашли//break; } p += 2; } else { //если отдельный символ if (*s == *p) { if (b) { return false; }//если таких символов не должно быть else { res = true; }//если нашли// res=true; } ++p; } } if (b == res) return false; ++p;//закрывающая скобка ++s; } else if (*p == L'*') { rs = s, rp = ++p; } else if (!*s) { return !*p; } else if (*p == L'#') { if (*s <= L'9' && *s >= L'0') { ++s, ++p; } else { return false; //++p;//or return false???? } } else if (*s == *p || *p == L'?') { ++s, ++p; } else if (rs) { s = ++rs, p = rp; } else { return false; } } } int main() { try { int iMax = 1600000;// 16000000; std::chrono::steady_clock::time_point timeStart; std::chrono::steady_clock::time_point timeStop; std::vector < std::vector<const wchar_t* >> testArr = { {L"XYXZZXY", L"*X*X?",L"True"}, //' Speed test {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"aM5b" , L"*#[!c-e]", L"True"}, //{L"" , L"[]", L"True"}, //{L"", L"*", L"True"}, //{L"", L"", L"True"}, //{L"*", L"", NULL}, //{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"a [xyz" , L"a [*", NULL} //' Throws Error 93 (invalid pattern string). }; std::wcout << L"Test pattern..."; std::wcout << L"\n\ncheck..."; for (int i = 0; i < testArr.size(); i++) { if (check((wchar_t*)testArr[i][0], (wchar_t*)testArr[i][1]) != (bool)testArr[i][2]) { std::wcout << std::wstring(L"\nERR: string, pattern-> '") + testArr[i][0] + L"', '" + testArr[i][1] + L"'"; } } std::wcout << L"\n\nLikeVB..."; for (int i = 0; i < testArr.size(); i++) { if (LikeVB(testArr[i][0], testArr[i][1]) != (bool)testArr[i][2]) { std::wcout << std::wstring(L"\nERR: string, pattern-> '") + testArr[i][0] + L"', '" + testArr[i][1] + L"'"; } } std::wcout << L"\n\nMatchWildcardAndText..."; for (int i = 0; i < testArr.size(); i++) { if (MatchWildcardAndText(testArr[i][0], testArr[i][1]) != (bool)testArr[i][2]) { std::wcout << std::wstring(L"\nERR: string-> ") + testArr[i][0] + L" pattern-> " + testArr[i][1]; } } std::wcout << L"\n\nSpeed test..."; timeStart = std::chrono::steady_clock::now(); for (int i = 0; i < iMax; i++) { check((wchar_t*)testArr[0][0], (wchar_t*)testArr[0][1]); } timeStop = std::chrono::steady_clock::now(); std::wcout << L"\n\ncheck, ms: " + std::to_wstring(std::chrono::duration_cast<std::chrono::milliseconds> (timeStop - timeStart).count()); timeStart = std::chrono::steady_clock::now(); for (int i = 0; i < iMax; i++) { LikeVB(testArr[0][0], testArr[0][1]); } timeStop = std::chrono::steady_clock::now(); std::wcout << L"\n\nLikeVB, ms: " + std::to_wstring(std::chrono::duration_cast<std::chrono::milliseconds> (timeStop - timeStart).count()); timeStart = std::chrono::steady_clock::now(); for (int i = 0; i < iMax; i++) { MatchWildcardAndText(testArr[0][0], testArr[0][1]); } timeStop = std::chrono::steady_clock::now(); std::wcout << L"\n\nMatchWildcardAndText, ms: " + std::to_wstring(std::chrono::duration_cast<std::chrono::milliseconds> (timeStop - timeStart).count()); std::wcout << L"\n\n"; system("pause"); return 0; } catch (int& e) { system("pause"); return e; } catch (...) { system("pause"); return -1; } }