Pull to refresh

LINQ конвертер между римскими и арабскими числами

Reading time 4 min
Views 14K
Сложилось, что разбирал со студентами LINQ, а со школьниками преобразование между римской и арабской системой счисления. В итоге, мысли заплелись и получился интересный код конвертера, который жалко схоронить в локальных архивах. Пример сгодится в качестве упражнения для понимания LINQ.

Итак, нам понадобится словарь, сопоставляющий элементы римских чисел с арабскими.

Dictionary<int, string> ra = new Dictionary<int, string>
        { { 1000, "M" },  { 900, "CM" },  { 500, "D" },  { 400, "CD" },  { 100, "C" },
                          { 90 , "XC" },  { 50 , "L" },  { 40 , "XL" },  { 10 , "X" },
                          { 9  , "IX" },  { 5  , "V" },  { 4  , "IV" },  { 1  , "I" } };

Используя этот словарь можно написать конвертеры из римской в арабскую нотацию и обратно. Для краткости и красоты мы не будем обрабатывать предусловия. Для арабских цифр допустимый диапазон определен как [1,4000). А римские цифры должны быть корректными и преобразованы к верхнему регистру.

Конвертер из арабских в римские


Разбор числа начинаем с больших чисел. Ключи в словаре упорядочены в порядке убывания. Просматривая их в заданном порядке находим первый ключ со значением не более конвертируемого числа (оператор Where). В словаре этому числу сопоставлено буквенное сочетание из римской системы счисления. Склеиваем найденное буквенное сочетание с рекурсивно конвертированным остатком числа (оператор Select). Первый результат и будет искомым представлением числа в римской нотации (оператор FirstOrDefault).

string ToRoman(int number) => ra
            .Where(d => number >= d.Key)
            .Select(d => d.Value + ToRoman(number - d.Key))
            .FirstOrDefault();

Конвертер из римских в арабские


Разбор римского числа происходит слева направо. Просматриваем все буквенные сочетания из словаря на вхождение в начало преобразуемой строки number.StartsWith(d.Value). При совпадении поле ключа будет содержать числовое значение, соответствующее буквенному сочетанию. Полученное значение суммируется с рекурсивно обработанной оставшейся строкой.

int ToArabic(string number) => number.Length == 0 ? 0 : ra
            .Where(d => number.StartsWith(d.Value))
            .Select(d => d.Key + ToArabic(number.Substring(d.Value.Length)))
            .FirstOrDefault();

Готовый класс для копипастинга v1
static class RomanNum
{
    // (c) 2015, Alexey Danov | THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY ...
    static Dictionary<int, string> ra = new Dictionary<int, string>
    { { 1000, "M" },  { 900, "CM" },  { 500, "D" },  { 400, "CD" },  { 100, "C" },
                      { 90 , "XC" },  { 50 , "L" },  { 40 , "XL" },  { 10 , "X" },
                      { 9  , "IX" },  { 5  , "V" },  { 4  , "IV" },  { 1  , "I" } };

    public static string ToRoman(int number) => ra
        .Where(d => number >= d.Key)
        .Select(d => d.Value + ToRoman(number - d.Key))
        .FirstOrDefault();

    public static int ToArabic(string number) => number.Length == 0 ? 0 : ra
        .Where(d => number.StartsWith(d.Value))
        .Select(d => d.Key + ToArabic(number.Substring(d.Value.Length)))
        .First();
}

На этом можно было бы остановиться. Но оказывается, что число 499 можно записать пятью способами: CDXCIX, LDVLIV, XDIX, VDIV или ID. Для краткой записи могут использоваться не заданные в словаре сочетания. Можно расширить словарь, а можно отталкиваться только от исходных букв IVXLCDM, которым соответствуют числа (1,5,10,50,100,500,1000).

В целях прокачки навыков .Net мага VC-уровня (VC == 95), словарь сгенерируем автоматически. А полученный код можно использовать для проверки навыков чтения чужого кода на вступительных испытаниях в школу .Net магов IC-уровня.

Конвертер из римских в арабские с обвязкой


Для генерации словаря пришлось воспользоваться внешней переменной. Далее код без комментариев.

int o = 1;
string w = "IVXLCDM";
Dictionary<char, int> ra = w.ToDictionary(ch => ch, ch => (o = ("" + o)[0] == '1' ? o * 2 : o * 5) / 2);
int ToArabic(string num) => 
    num.Select((c, i) => ++i < num.Length && ra[c] < ra[num[i]] ? -ra[c] : ra[c]).Sum();

Конвертер из арабских в римские с обвязкой


А вот для перевода в римскую систему для краткости потребовалась пара вспомогательных функций. Можно их включить в саму функцию, но получится нагромождение.

string W(int k, int l = 1) => w.Substring(k, l);
string R(char m, int k) => 
    m == '9' ? W(k-2)+W(k) : m == '5' ? W(k-1) : m == '4' ? W(k-2, 2) : W(k-2);

string ToRoman(int num) => num < 1 ? "" : 
       (from z in "000100101".Split('1') from m in "9541" select m + z)
       .Where(z => num >= (o = int.Parse(z)))
       .Select(z => R(z[0], z.Length * 2)).First() + ToRoman(num - o);


Готовый класс для копипастинга v2
static class RomanNumEx
{
    // (c) 2015, Alexey Danov | THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY ...
    static int o = 1;
    static string w = "IVXLCDM";
    static Dictionary<char, int> ra = w.ToDictionary(ch => ch, ch => (o = ("" + o)[0] == '1' ? o * 2 : o * 5) / 2);

    public static int ToArabic(string num) => num
        .Select((c, i) => ++i < num.Length && ra[c] < ra[num[i]] ? -ra[c] : ra[c]).Sum();

    static string W(int k, int l = 1) => w.Substring(k, l);
    static string R(char m, int k) => m == '9' ? W(k-2)+W(k) : m == '5' ? W(k-1) : m == '4' ? W(k-2, 2) : W(k-2);

    public static string ToRoman(int num) => num < 1 ? "" : 
        (from z in "000100101".Split('1') from m in "9541" select m + z)
        .Where(z => num >= (o = int.Parse(z)))
        .Select(z => R(z[0], z.Length * 2)).First() + ToRoman(num - o);
}

Эти примеры далеко не оптимальны по скорости работы, но их можно использовать. И прежде всего, в обучении основам LINQ.
Tags:
Hubs:
+7
Comments 13
Comments Comments 13

Articles