using System;
using System.Text;
namespace ConsoleApplication51
{
class Program
{
static class RangeChecker
{
public static string BuildRegex(string matches)
{
string[] splits = matches.Split(',');
if (splits.Length == 0)
{
return "^()$";
}
StringBuilder res = new StringBuilder();
res.Append("^(");
foreach (string split in splits)
{
if (split == "*")
{
return "^([0-9]+)$";
}
string[] subSplit = split.Split('-');
string min = subSplit[0].TrimStart('0');
if (min == string.Empty)
{
return null;
}
if (subSplit.Length == 1)
{
res.Append(min);
res.Append('|');
continue;
}
else if (subSplit.Length > 2)
{
return null;
}
string max = subSplit[1].TrimStart('0');
if (max == string.Empty)
{
return null;
}
if (min.Length > max.Length)
{
return null;
}
// For 2-998 we first produce 2-9, then 10-99
string tempMin = BuildRegexDifferentLength(res, min, max);
if (tempMin == null)
{
return null;
}
// Then here 100-998
BuildRegexSameLength(res, tempMin, max);
}
res.Length--;
res.Append(")$");
return res.ToString();
}
private static bool IsOnlyDigit(string str, int start, char digit)
{
for (int i = start; i < str.Length; i++)
{
if (str[i] != digit)
{
return false;
}
}
return true;
}
private static string BuildRangeDigit(char min, char max)
{
if (min == max)
{
return min.ToString();
}
return "[" + min + "-" + max + "]";
}
private static string BuildRegexDifferentLength(StringBuilder res, string min, string max)
{
string tempMin = min;
for (int i = min.Length; i < max.Length; i++)
{
string tempMax = new string('9', i);
BuildRegexSameLength(res, tempMin, tempMax);
tempMin = "1" + new string('0', i);
}
if (tempMin.CompareTo(max) > 0)
{
return null;
}
return tempMin;
}
private static void BuildRegexSameLength(StringBuilder res, string min, string max)
{
// 100-100
if (min == max)
{
res.Append(min);
res.Append('|');
return;
}
int commonPart = 0;
for (; commonPart < min.Length; commonPart++)
{
if (min[commonPart] != max[commonPart])
{
break;
}
}
RecursivelyAddRegexRange(res, min.Substring(0, commonPart), min.Substring(commonPart), max.Substring(commonPart));
}
private static void RecursivelyAddRegexRange(StringBuilder res, string prefix, string min, string max)
{
if (min.Length == 1)
{
res.Append(prefix);
res.Append(BuildRangeDigit(min[0], max[0]));
res.Append('|');
return;
}
// Check if
bool only0Min = IsOnlyDigit(min, 1, '0');
bool only9Max = IsOnlyDigit(max, 1, '9');
if (only0Min && only9Max)
{
res.Append(prefix);
res.Append(BuildRangeDigit(min[0], max[0]));
for (int i = 1; i < min.Length; i++)
{
res.Append("[0-9]");
}
res.Append('|');
return;
}
string middleMin = min;
if (!only0Min)
{
RecursivelyAddRegexRange(res, prefix + min[0], min.Substring(1), new string('9', min.Length - 1));
if (min[0] != '9')
{
middleMin = (char)(min[0] + 1) + new string('0', min.Length - 1);
}
else
{
middleMin = null;
}
}
string middleMax = max;
if (!only9Max)
{
if (max[0] != '0')
{
middleMax = (char)(max[0] - 1) + new string('9', max.Length - 1);
}
else
{
middleMax = null;
}
}
if (middleMin != null && middleMax != null && middleMin[0] <= middleMax[0])
{
RecursivelyAddRegexRange(res, prefix + BuildRangeDigit(middleMin[0], middleMax[0]), middleMin.Substring(1), middleMax.Substring(1));
}
if (!only9Max)
{
RecursivelyAddRegexRange(res, prefix + max[0], new string('0', max.Length - 1), max.Substring(1));
}
}
}
static void Main(string[] args)
{
Action<string> printRegex = p => Console.WriteLine("{0}: {1}", p, RangeChecker.BuildRegex(p));
printRegex("*");
printRegex("1");
printRegex("1,*");
printRegex("1,2,3,4");
printRegex("1,11-88");
printRegex("1,11-88,90-101");
printRegex("1-11111");
printRegex("75-11119");
}
}
}
dXNpbmcgU3lzdGVtOwp1c2luZyBTeXN0ZW0uVGV4dDsKCm5hbWVzcGFjZSBDb25zb2xlQXBwbGljYXRpb241MQp7CiAgICBjbGFzcyBQcm9ncmFtCiAgICB7CiAgICAgICAgc3RhdGljIGNsYXNzIFJhbmdlQ2hlY2tlcgogICAgICAgIHsKICAgICAgICAgICAgcHVibGljIHN0YXRpYyBzdHJpbmcgQnVpbGRSZWdleChzdHJpbmcgbWF0Y2hlcykKICAgICAgICAgICAgewogICAgICAgICAgICAgICAgc3RyaW5nW10gc3BsaXRzID0gbWF0Y2hlcy5TcGxpdCgnLCcpOwoKICAgICAgICAgICAgICAgIGlmIChzcGxpdHMuTGVuZ3RoID09IDApCiAgICAgICAgICAgICAgICB7CiAgICAgICAgICAgICAgICAgICAgcmV0dXJuICJeKCkkIjsKICAgICAgICAgICAgICAgIH0KCiAgICAgICAgICAgICAgICBTdHJpbmdCdWlsZGVyIHJlcyA9IG5ldyBTdHJpbmdCdWlsZGVyKCk7CiAgICAgICAgICAgICAgICByZXMuQXBwZW5kKCJeKCIpOwoKICAgICAgICAgICAgICAgIGZvcmVhY2ggKHN0cmluZyBzcGxpdCBpbiBzcGxpdHMpCiAgICAgICAgICAgICAgICB7CiAgICAgICAgICAgICAgICAgICAgaWYgKHNwbGl0ID09ICIqIikKICAgICAgICAgICAgICAgICAgICB7CiAgICAgICAgICAgICAgICAgICAgICAgIHJldHVybiAiXihbMC05XSspJCI7CiAgICAgICAgICAgICAgICAgICAgfQoKICAgICAgICAgICAgICAgICAgICBzdHJpbmdbXSBzdWJTcGxpdCA9IHNwbGl0LlNwbGl0KCctJyk7CgogICAgICAgICAgICAgICAgICAgIHN0cmluZyBtaW4gPSBzdWJTcGxpdFswXS5UcmltU3RhcnQoJzAnKTsKCiAgICAgICAgICAgICAgICAgICAgaWYgKG1pbiA9PSBzdHJpbmcuRW1wdHkpCiAgICAgICAgICAgICAgICAgICAgewogICAgICAgICAgICAgICAgICAgICAgICByZXR1cm4gbnVsbDsKICAgICAgICAgICAgICAgICAgICB9CgogICAgICAgICAgICAgICAgICAgIGlmIChzdWJTcGxpdC5MZW5ndGggPT0gMSkKICAgICAgICAgICAgICAgICAgICB7CiAgICAgICAgICAgICAgICAgICAgICAgIHJlcy5BcHBlbmQobWluKTsKICAgICAgICAgICAgICAgICAgICAgICAgcmVzLkFwcGVuZCgnfCcpOwoKICAgICAgICAgICAgICAgICAgICAgICAgY29udGludWU7CiAgICAgICAgICAgICAgICAgICAgfQogICAgICAgICAgICAgICAgICAgIGVsc2UgaWYgKHN1YlNwbGl0Lkxlbmd0aCA+IDIpCiAgICAgICAgICAgICAgICAgICAgewogICAgICAgICAgICAgICAgICAgICAgICByZXR1cm4gbnVsbDsKICAgICAgICAgICAgICAgICAgICB9CgogICAgICAgICAgICAgICAgICAgIHN0cmluZyBtYXggPSBzdWJTcGxpdFsxXS5UcmltU3RhcnQoJzAnKTsKCiAgICAgICAgICAgICAgICAgICAgaWYgKG1heCA9PSBzdHJpbmcuRW1wdHkpCiAgICAgICAgICAgICAgICAgICAgewogICAgICAgICAgICAgICAgICAgICAgICByZXR1cm4gbnVsbDsKICAgICAgICAgICAgICAgICAgICB9CgogICAgICAgICAgICAgICAgICAgIGlmIChtaW4uTGVuZ3RoID4gbWF4Lkxlbmd0aCkKICAgICAgICAgICAgICAgICAgICB7CiAgICAgICAgICAgICAgICAgICAgICAgIHJldHVybiBudWxsOwogICAgICAgICAgICAgICAgICAgIH0KCiAgICAgICAgICAgICAgICAgICAgLy8gRm9yIDItOTk4IHdlIGZpcnN0IHByb2R1Y2UgMi05LCB0aGVuIDEwLTk5CiAgICAgICAgICAgICAgICAgICAgc3RyaW5nIHRlbXBNaW4gPSBCdWlsZFJlZ2V4RGlmZmVyZW50TGVuZ3RoKHJlcywgbWluLCBtYXgpOwoKICAgICAgICAgICAgICAgICAgICBpZiAodGVtcE1pbiA9PSBudWxsKQogICAgICAgICAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgICAgICAgICAgcmV0dXJuIG51bGw7CiAgICAgICAgICAgICAgICAgICAgfQoKICAgICAgICAgICAgICAgICAgICAvLyBUaGVuIGhlcmUgMTAwLTk5OAogICAgICAgICAgICAgICAgICAgIEJ1aWxkUmVnZXhTYW1lTGVuZ3RoKHJlcywgdGVtcE1pbiwgbWF4KTsKICAgICAgICAgICAgICAgIH0KCiAgICAgICAgICAgICAgICByZXMuTGVuZ3RoLS07CiAgICAgICAgICAgICAgICByZXMuQXBwZW5kKCIpJCIpOwoKICAgICAgICAgICAgICAgIHJldHVybiByZXMuVG9TdHJpbmcoKTsKICAgICAgICAgICAgfQoKICAgICAgICAgICAgcHJpdmF0ZSBzdGF0aWMgYm9vbCBJc09ubHlEaWdpdChzdHJpbmcgc3RyLCBpbnQgc3RhcnQsIGNoYXIgZGlnaXQpCiAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgIGZvciAoaW50IGkgPSBzdGFydDsgaSA8IHN0ci5MZW5ndGg7IGkrKykKICAgICAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgICAgICBpZiAoc3RyW2ldICE9IGRpZ2l0KQogICAgICAgICAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgICAgICAgICAgcmV0dXJuIGZhbHNlOwogICAgICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgICAgIH0KCiAgICAgICAgICAgICAgICByZXR1cm4gdHJ1ZTsKICAgICAgICAgICAgfQoKICAgICAgICAgICAgcHJpdmF0ZSBzdGF0aWMgc3RyaW5nIEJ1aWxkUmFuZ2VEaWdpdChjaGFyIG1pbiwgY2hhciBtYXgpCiAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgIGlmIChtaW4gPT0gbWF4KQogICAgICAgICAgICAgICAgewogICAgICAgICAgICAgICAgICAgIHJldHVybiBtaW4uVG9TdHJpbmcoKTsKICAgICAgICAgICAgICAgIH0KCiAgICAgICAgICAgICAgICByZXR1cm4gIlsiICsgbWluICsgIi0iICsgbWF4ICsgIl0iOwogICAgICAgICAgICB9CgogICAgICAgICAgICBwcml2YXRlIHN0YXRpYyBzdHJpbmcgQnVpbGRSZWdleERpZmZlcmVudExlbmd0aChTdHJpbmdCdWlsZGVyIHJlcywgc3RyaW5nIG1pbiwgc3RyaW5nIG1heCkKICAgICAgICAgICAgewogICAgICAgICAgICAgICAgc3RyaW5nIHRlbXBNaW4gPSBtaW47CgogICAgICAgICAgICAgICAgZm9yIChpbnQgaSA9IG1pbi5MZW5ndGg7IGkgPCBtYXguTGVuZ3RoOyBpKyspCiAgICAgICAgICAgICAgICB7CiAgICAgICAgICAgICAgICAgICAgc3RyaW5nIHRlbXBNYXggPSBuZXcgc3RyaW5nKCc5JywgaSk7CgogICAgICAgICAgICAgICAgICAgIEJ1aWxkUmVnZXhTYW1lTGVuZ3RoKHJlcywgdGVtcE1pbiwgdGVtcE1heCk7CgogICAgICAgICAgICAgICAgICAgIHRlbXBNaW4gPSAiMSIgKyBuZXcgc3RyaW5nKCcwJywgaSk7CiAgICAgICAgICAgICAgICB9CgogICAgICAgICAgICAgICAgaWYgKHRlbXBNaW4uQ29tcGFyZVRvKG1heCkgPiAwKQogICAgICAgICAgICAgICAgewogICAgICAgICAgICAgICAgICAgIHJldHVybiBudWxsOwogICAgICAgICAgICAgICAgfQoKICAgICAgICAgICAgICAgIHJldHVybiB0ZW1wTWluOwogICAgICAgICAgICB9CgogICAgICAgICAgICBwcml2YXRlIHN0YXRpYyB2b2lkIEJ1aWxkUmVnZXhTYW1lTGVuZ3RoKFN0cmluZ0J1aWxkZXIgcmVzLCBzdHJpbmcgbWluLCBzdHJpbmcgbWF4KQogICAgICAgICAgICB7CiAgICAgICAgICAgICAgICAvLyAxMDAtMTAwCiAgICAgICAgICAgICAgICBpZiAobWluID09IG1heCkKICAgICAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgICAgICByZXMuQXBwZW5kKG1pbik7CiAgICAgICAgICAgICAgICAgICAgcmVzLkFwcGVuZCgnfCcpOwoKICAgICAgICAgICAgICAgICAgICByZXR1cm47CiAgICAgICAgICAgICAgICB9CgogICAgICAgICAgICAgICAgaW50IGNvbW1vblBhcnQgPSAwOwoKICAgICAgICAgICAgICAgIGZvciAoOyBjb21tb25QYXJ0IDwgbWluLkxlbmd0aDsgY29tbW9uUGFydCsrKQogICAgICAgICAgICAgICAgewogICAgICAgICAgICAgICAgICAgIGlmIChtaW5bY29tbW9uUGFydF0gIT0gbWF4W2NvbW1vblBhcnRdKQogICAgICAgICAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgICAgICAgICAgYnJlYWs7CiAgICAgICAgICAgICAgICAgICAgfQogICAgICAgICAgICAgICAgfQoKICAgICAgICAgICAgICAgIFJlY3Vyc2l2ZWx5QWRkUmVnZXhSYW5nZShyZXMsIG1pbi5TdWJzdHJpbmcoMCwgY29tbW9uUGFydCksIG1pbi5TdWJzdHJpbmcoY29tbW9uUGFydCksIG1heC5TdWJzdHJpbmcoY29tbW9uUGFydCkpOwogICAgICAgICAgICB9CgogICAgICAgICAgICBwcml2YXRlIHN0YXRpYyB2b2lkIFJlY3Vyc2l2ZWx5QWRkUmVnZXhSYW5nZShTdHJpbmdCdWlsZGVyIHJlcywgc3RyaW5nIHByZWZpeCwgc3RyaW5nIG1pbiwgc3RyaW5nIG1heCkKICAgICAgICAgICAgewogICAgICAgICAgICAgICAgaWYgKG1pbi5MZW5ndGggPT0gMSkKICAgICAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgICAgICByZXMuQXBwZW5kKHByZWZpeCk7CiAgICAgICAgICAgICAgICAgICAgcmVzLkFwcGVuZChCdWlsZFJhbmdlRGlnaXQobWluWzBdLCBtYXhbMF0pKTsKICAgICAgICAgICAgICAgICAgICByZXMuQXBwZW5kKCd8Jyk7CgogICAgICAgICAgICAgICAgICAgIHJldHVybjsKICAgICAgICAgICAgICAgIH0KCiAgICAgICAgICAgICAgICAvLyBDaGVjayBpZiAKICAgICAgICAgICAgICAgIGJvb2wgb25seTBNaW4gPSBJc09ubHlEaWdpdChtaW4sIDEsICcwJyk7CiAgICAgICAgICAgICAgICBib29sIG9ubHk5TWF4ID0gSXNPbmx5RGlnaXQobWF4LCAxLCAnOScpOwoKICAgICAgICAgICAgICAgIGlmIChvbmx5ME1pbiAmJiBvbmx5OU1heCkKICAgICAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgICAgICByZXMuQXBwZW5kKHByZWZpeCk7CiAgICAgICAgICAgICAgICAgICAgcmVzLkFwcGVuZChCdWlsZFJhbmdlRGlnaXQobWluWzBdLCBtYXhbMF0pKTsKCiAgICAgICAgICAgICAgICAgICAgZm9yIChpbnQgaSA9IDE7IGkgPCBtaW4uTGVuZ3RoOyBpKyspCiAgICAgICAgICAgICAgICAgICAgewogICAgICAgICAgICAgICAgICAgICAgICByZXMuQXBwZW5kKCJbMC05XSIpOwogICAgICAgICAgICAgICAgICAgIH0KCiAgICAgICAgICAgICAgICAgICAgcmVzLkFwcGVuZCgnfCcpOwoKICAgICAgICAgICAgICAgICAgICByZXR1cm47CiAgICAgICAgICAgICAgICB9CgogICAgICAgICAgICAgICAgc3RyaW5nIG1pZGRsZU1pbiA9IG1pbjsKCiAgICAgICAgICAgICAgICBpZiAoIW9ubHkwTWluKQogICAgICAgICAgICAgICAgewogICAgICAgICAgICAgICAgICAgIFJlY3Vyc2l2ZWx5QWRkUmVnZXhSYW5nZShyZXMsIHByZWZpeCArIG1pblswXSwgbWluLlN1YnN0cmluZygxKSwgbmV3IHN0cmluZygnOScsIG1pbi5MZW5ndGggLSAxKSk7CgogICAgICAgICAgICAgICAgICAgIGlmIChtaW5bMF0gIT0gJzknKQogICAgICAgICAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgICAgICAgICAgbWlkZGxlTWluID0gKGNoYXIpKG1pblswXSArIDEpICsgbmV3IHN0cmluZygnMCcsIG1pbi5MZW5ndGggLSAxKTsKICAgICAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgICAgICAgICAgZWxzZQogICAgICAgICAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgICAgICAgICAgbWlkZGxlTWluID0gbnVsbDsKICAgICAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgICAgICB9CgogICAgICAgICAgICAgICAgc3RyaW5nIG1pZGRsZU1heCA9IG1heDsKCiAgICAgICAgICAgICAgICBpZiAoIW9ubHk5TWF4KQogICAgICAgICAgICAgICAgewogICAgICAgICAgICAgICAgICAgIGlmIChtYXhbMF0gIT0gJzAnKQogICAgICAgICAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgICAgICAgICAgbWlkZGxlTWF4ID0gKGNoYXIpKG1heFswXSAtIDEpICsgbmV3IHN0cmluZygnOScsIG1heC5MZW5ndGggLSAxKTsKICAgICAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgICAgICAgICAgZWxzZQogICAgICAgICAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgICAgICAgICAgbWlkZGxlTWF4ID0gbnVsbDsKICAgICAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgICAgICB9CgogICAgICAgICAgICAgICAgaWYgKG1pZGRsZU1pbiAhPSBudWxsICYmIG1pZGRsZU1heCAhPSBudWxsICYmIG1pZGRsZU1pblswXSA8PSBtaWRkbGVNYXhbMF0pCiAgICAgICAgICAgICAgICB7CiAgICAgICAgICAgICAgICAgICAgUmVjdXJzaXZlbHlBZGRSZWdleFJhbmdlKHJlcywgcHJlZml4ICsgQnVpbGRSYW5nZURpZ2l0KG1pZGRsZU1pblswXSwgbWlkZGxlTWF4WzBdKSwgbWlkZGxlTWluLlN1YnN0cmluZygxKSwgbWlkZGxlTWF4LlN1YnN0cmluZygxKSk7CiAgICAgICAgICAgICAgICB9CgogICAgICAgICAgICAgICAgaWYgKCFvbmx5OU1heCkKICAgICAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgICAgICBSZWN1cnNpdmVseUFkZFJlZ2V4UmFuZ2UocmVzLCBwcmVmaXggKyBtYXhbMF0sIG5ldyBzdHJpbmcoJzAnLCBtYXguTGVuZ3RoIC0gMSksIG1heC5TdWJzdHJpbmcoMSkpOwogICAgICAgICAgICAgICAgfQogICAgICAgICAgICB9CiAgICAgICAgfQoKICAgICAgICBzdGF0aWMgdm9pZCBNYWluKHN0cmluZ1tdIGFyZ3MpCiAgICAgICAgewogICAgICAgICAgICBBY3Rpb248c3RyaW5nPiBwcmludFJlZ2V4ID0gcCA9PiBDb25zb2xlLldyaXRlTGluZSgiezB9OiB7MX0iLCBwLCBSYW5nZUNoZWNrZXIuQnVpbGRSZWdleChwKSk7CgogICAgICAgICAgICBwcmludFJlZ2V4KCIqIik7CiAgICAgICAgICAgIHByaW50UmVnZXgoIjEiKTsKICAgICAgICAgICAgcHJpbnRSZWdleCgiMSwqIik7CiAgICAgICAgICAgIHByaW50UmVnZXgoIjEsMiwzLDQiKTsKICAgICAgICAgICAgcHJpbnRSZWdleCgiMSwxMS04OCIpOwogICAgICAgICAgICBwcmludFJlZ2V4KCIxLDExLTg4LDkwLTEwMSIpOwogICAgICAgICAgICBwcmludFJlZ2V4KCIxLTExMTExIik7CiAgICAgICAgICAgIHByaW50UmVnZXgoIjc1LTExMTE5Iik7CiAgICAgICAgfQogICAgfQp9Cg==