Implementare algoritm de conversie a unui număr din format roman în format arabic

Față de formatul arab, în care pentru reprezentarea numerelor folosim cifrele arhicunoscute de la 0 la 9, în formatul roman vorbim de următoarele caractere: I, V, X, L, C, D și M. Vă aduceți cu siguranță aminte de ele din clasele primare. Să ridice mâna cine nu a auzit de reprezentarea romană a unui număr!

Tot în clasele primare am învățat și cum putem converti un număr din format roman în format arabic, folosind o arhicunoscută mapare:

Astăzi vom vorbi doar de conversia din format roman în format arabic. Să luăm și câteva exemplu pentru a face lucrurile și mai clare:

Să ne amintăm așadar că numerele în format roman sunt scrise de la stânga la dreapta, de la cea mai mare valoare, la cea mai mică. Totuși, partea tricky este că VIIII nu este valid, ci IX. IX = 9 = 10 – 1. În loc de o adunare, aici vorbim de o scădere. Această soluție a fost propusă pentru a reduce numărul de caractere necesare pentru a reprezenta un număr. În cazul nostru, pentru 9 sunt 2 caractere folosite, față de 5 în reprezentarea cea mai intuitivă – VIIII. Dar până la urmă noi suntem obișnuiți cu ceva asemănător atunci când spunem ora curentă. Iată și un exemplu! Să zicem că ora curentă este 12:58 și cineva ne întreabă cât este ceasul. Cea mai la îndemână variantă este ora treispreceze fără două minute. A doua ar fi: ora doisprezece și cincizeci și opt de minute. În acest caz, prima variantă este mai convenabilă pentru că necesită mai puține cuvinte de rostit (deci este mai rapidă) și cumva te duce și la ideea că mai e foarte puțin până la ora 13. Vorbim de câteva minute înainte de ora 13, dar care de multe ori sunt nesemnificative.

Cele 6 cazuri în care scăderea este utilizată sunt:

• I poate apărea înaintea lui V și X pentru a forma 4 sau 9.
• X poate apărea înaintea lui L sau C pentru a forma 40 sau 90.
• C poate apărea înaintea lui D sau M pentru a forma 400 sau 900.

Cerință

Dându-se un număr în format roman, se cere să se găsească reprezentarea lui în format arabic. În plus, se garantează faptul că numărul primit ca și input este valid. Ca și temă de casă, puteți scrie un algoritm care validează șirul de caractere primit ca și input că este reprezentat corect în format roman.

Soluție

Cea mai bună soluție este că nu vedem doar cele 7 caractere ca și simboluri posibile pentru reprezentarea romană, ci să luăm în calcul și cazurile particulare, unde avem scăderi, în loc de adunări. Și anume: IV = 4, IX = 9, XL = 40, XC = 90, CD = 400, CM = 900. Cu alte cuvinte, vom aveam 13 simboluri în loc de 7. În acest fel, dintr-o singură traversare, vom putea interpreta și converti numărul dorit.

Să luăm și un exemplu pentru a clarifica lucrurile: MMCMXCIX. Iată din ce simboluri e compus acest număr: M M CM XC IX = 1000 + 1000 + 900 + 90 + 9 = 2999.

Implementarea în Java este:

import org.assertj.core.api.Assertions;
import org.junit.Test;

import java.util.Map;

import static java.util.Map.entry;

public final class NumberFormat {

    private static Map<String, Integer> CONVERT_VALUES = Map.ofEntries(
            entry("I", 1),
            entry("V", 5),
            entry("X", 10),
            entry("L", 50),
            entry("C", 100),
            entry("D", 500),
            entry("M", 1000),
            entry("IV", 4),
            entry("IX", 9),
            entry("XL", 40),
            entry("XC", 90),
            entry("CD", 400),
            entry("CM", 900)
    );

    public int romanToArabic(String number) {
        int numberLength = number.length();
        int sum = 0;

        int i = 0;
        while (i++ < numberLength) {
            if (i < numberLength) {
                String doubleSymbol = number.substring(i - 1, i + 1);
                if (CONVERT_VALUES.containsKey(doubleSymbol)) {
                    sum += CONVERT_VALUES.get(doubleSymbol);
                    i++;
                    continue;
                }
            }
            sum += CONVERT_VALUES.get(String.valueOf(number.charAt(i - 1)));
        }

        return sum;
    }

}

Iată și două teste pentru soluția propusă:

import org.assertj.core.api.Assertions;
import org.junit.Test;

public class NumberFormatTest {

    @Test
    public void simple_test() {
        Assertions.assertThat(new NumberFormat().romanToArabic("MMCMXCIX")).isEqualTo(2999);
    }

    @Test
    public void advanced_test() {
        Assertions.assertThat(new NumberFormat().romanToArabic("MMMDCCLXXXIV")).isEqualTo(3784);
    }

}

Happy coding! 🙂