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");
        }
    }
}