//C++17
#include <iostream>
#include <string>
#include <algorithm>
#include <optional>
#include <cassert>
#include <iomanip>
//? Любой отдельный символ
//* Ноль или более символов
//# Любая однозначная цифра (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)}))
{
//дальше лежат корректные квадратные скобки
//символ строки лежит в списке?
if(SBInfo.TestChar(*text_cur))
{
//надо будет перейти к обработке скобок
++wc_cur;
done=true;
}
else
{
//то звёздочка забирает один символ из текста
++text_cur;
}
}
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;
}
int main()
{
struct s_test
{
const std::wstring_view string;
const std::wstring_view mask;
bool result{};
};
const std::vector<s_test> tests
{
{L"" , L"*" , 1},
{L"5*" , L"5[*]" , 1},
{L"?n" , L"[?]n" , 1},
{L"a" , L"[a-cdf]" , 1},
{L"b" , L"[a-cdf]" , 1},
{L"c" , L"[a-cdf]" , 1},
{L"d" , L"[a-cdf]" , 1},
{L"f" , L"[a-cdf]" , 1},
{L"-" , L"[-acdf]" , 1},
{L"a" , L"[-acdf]" , 1},
{L"c" , L"[-acdf]" , 1},
{L"d" , L"[-acdf]" , 1},
{L"f" , L"[-acdf]" , 1},
{L"[" , L"[ [ ]" , 1},
{L"]" , L"]" , 1},
{L"abc_d" , L"abc[_]d*" , 1},
{L"abc_de", L"abc[_]d*" , 1},
{L"abcd" , L"abc[def]" , 1},
{L"abce" , L"abc[def]" , 1},
{L"abcf" , L"abc[def]" , 1},
{L"abcdef", L"abc*[de]ef", 1},
{L"abcyef", L"abc[xz]ef" , 0},
{L"abcxef", L"abc[xz]ef" , 1},
{L"abcyef", L"abc[!xz]ef", 1},
{L"abcxef", L"abc[!xz]ef", 0},
{L"aBBBa" , L"a*a" , 1},
{L"ac5c5b", L"a*[1-56-9][!c-e]", 0}
};
for(auto& test:tests)
{
if(test.result==MatchWildcardAndText(test.string, test.mask))
{
std::wcout<<L"ok :";
}
else
{
std::wcout<<L"error:";
}
std::wcout<<L"must be";
if(test.result)
{
std::wcout<<L" true >>";
}
else
{
std::wcout<<L" false >>";
}
std::wcout<<L" string "<<std::left<<std::setw(10)<<(L"'"+std::wstring(test.string)+L"'");
std::wcout<<L" mask " <<std::left <<std::setw(16)<<(L"'"+std::wstring(test.mask )+L"'");
std::wcout<<'\n';
if constexpr(MatchWildcardAndText_showDebugOutput)std::wcout<<L"\n";
}
return 0;
}
