//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;
}
