Rzymskie na dziesiętne

Jak chyba większość maniaków programowania najlepiej odpoczywam po tej pięknej i fascynującej pracy... programując różne pierdoły ;) Natknąłem się na kilka sposobów przekodowywania liczby dziesiętnej na rzymską, ale jakoś nie wpadł mi w oko algorytm przeciwny. Tymczasem potrzeba takiej konwersji zachodzi częściej - choćby, jak w moim przypadku - do zamiany roku produkcji podanego w czołówce filmu w systemie, a jakże, rzymskim, na jakiś przyswajalny mojej wyobraźni, czyli dziesiętny :) Oto owoc kilku chwil mojego relaksu. Dla tych, którzy zrzynają gotowce mechanicznie podaję najpierw źródło :D

unit Roman2Dec;

{ 'private' }

interface

function RomanToDec( const roman: string ): integer;



implementation

uses
  Sysutils, { funkcja UpperCase }
  Strutils; { funkcje AnsiEndsStr, LeftStr }


const
  numbers_max = 21;

type
  liczby = record
    rom: string;
    dec: integer;
  end;

function RomanToDecRec( const roman: string ): integer;
const
  numbers: array[ 1..numbers_max ] of liczby =
  ( ( rom: 'III'; dec: 3 ),
    ( rom: 'II'; dec: 2 ),
    ( rom: 'IV'; dec: 4 ),
    ( rom: 'IX'; dec: 9 ),
    ( rom: 'I'; dec: 1 ),
    ( rom: 'V'; dec: 5 ),
    ( rom: 'XXX'; dec: 30 ),
    ( rom: 'XX'; dec: 20 ),
    ( rom: 'XL'; dec: 40 ),
    ( rom: 'XC'; dec: 90 ),
    ( rom: 'X'; dec: 10 ),
    ( rom: 'L'; dec: 50 ),
    ( rom: 'CCC'; dec: 300 ),
    ( rom: 'CC'; dec: 200 ),
    ( rom: 'CD'; dec: 400 ),
    ( rom: 'CM'; dec: 900 ),
    ( rom: 'C'; dec: 100 ),
    ( rom: 'D'; dec: 500 ),
    ( rom: 'MMM'; dec: 3000 ),
    ( rom: 'MM'; dec: 2000 ),
    ( rom: 'M'; dec: 1000 ) );

var
  roman_temp: string;
  i: integer;
  decimal_temp: integer;
  success: boolean;

begin
  { Przypisanie wartosci poczatkowych }
  result := 0; { Wazne przypisanie, pozwala uproscic obsluge ew. bledow! }
  decimal_temp := 0; { zmienna sluzaca do przechowywania sumy czastkowej }

  { Przepisanie liczby rzymskiej do zmiennej tymczasowej, zmiana na duze litery }
  roman_temp := UpperCase( roman );

  { Wlasciwa analiza }
  while Length( roman_temp ) > 0 do
  begin
    { Zmienna success bedzie ustawiona na true jesli ktorys z elementow tablicy
      numbers bedzie KONCZYL lancuch roman_temp. Na razie ustawiamy ja na false,
      co pozwala wylapac blad w przypadku liczb zawierajacych znaki inne niz
      cyfry rzymskie, na przyklad 'A'. }
    success := false;

    { przeszukiwanie tablicy numbers }
    for i := 1 to numbers_max do
    begin
      if AnsiEndsStr( numbers[ i ].rom, roman_temp ) then
        { jeden z elementow numbers znajduje sie na koncu lancucha roman_temp }
      begin
        { kontrola poprawnosci - dziesietny odpowiednik nie moze byc mniejszy
          niz uzyskana juz suma tymczasowa. Poniewaz result jest na razie
          ustawiony na 0 - mozemy spokojnie opuscic funkcje bez dodatkowych
          czynnosci }
        if ( numbers[ i ].dec <= decimal_temp ) then
          exit;

        { Zwiekszamy sume tymczasowa }
        decimal_temp := decimal_temp + numbers[ i ].dec;

        { Obcinamy lancuch tymczasowy od konca o dlugosc znalezionego wlasnie
          elementu liczby rzymskiej }
        roman_temp := LeftStr( roman_temp, Length( roman_temp ) - Length( numbers[ i ].rom ) );

        { Ustawiamy zmienna success i konczymy przeszukiwanie }
        success := true;
        break;
      end;
    end;

    if not success then
    begin
      { jesli liczba rzymska konczy sie elementem, ktorego nie znaleziono
        w tablicy numbers - na przyklad zawiera 'A' - opuszczamy funkcje.
        Result dalej jest ustawiony na zero :) }
      exit;
    end;
  end; { lancuch roman_temp pusty, koniec przeszukiwania }

  result := decimal_temp;
end; { function RomanToDec }

end.

Teraz kilka słów o użytym algorytmie:

Konwersja oparta jest na prostym fakcie: zapis cyfr rzymskich jest skomplikowany jedynie dlatego, że najstarsi Rzymianie nie znali... SPACJI :) Oraz nie pofatygowali się wprowadzić jednoznakowych odpowiedników dla wszystkich cyfr z zakresu 0..9, co również nie dziwi zważywszy że zera też nie znali :) Tak więc jakaś liczba rzymska, na przykład

MMCCCLXXXVIII (2388 dziesiętnie)

co wygląda dość koszmarnie - rozbiera się jako:

MM CCC L XXX V III

Czyli 2000 + 300 + 50 + 30 + 5 + 3.

Można było stosować logiczny rozbiór liczby, sprawdzając czy 'I' to jedynka czy część 'II', 'III', 'IV', 'VI' lub 'IX', ale powstałby logiczny potworek :) . Można było zapisać odpowiedniki cyfr rzymskich 1..9, 10..90, 100..900, 1000..3000 - ale wtedy tablica numbers miałaby 30 elementów. Wybrałem metodę IMHO najprostszą, polegającą na wyliczeniu listy możliwych tokenów (patrz tablica numbers) i wyszukiwaniu jej elementów w liczbie rzymskiej. Wyjaśnienia wymaga jedynie jej (tablicy :P) uporządkowanie. Jest tak posortowana, żeby podczas przeszukiwania liczby rzymskiej najpierw wychwytywać 'III' a potem 'II'. Zauważcie, że w przypadku wystąpienia niedozwolonej sekwencji 'XXXX' najpierw zostanie odnaleziony token 'XXX', a następnie 'X', co spowoduje wyjście z funkcji z wynikiem zero :) Wyjaśnia się tu dlaczego nie redukowałem rozmiarów tablicy numbers poprzez usunięcie tokenów 'III', 'II' i pozwolenie programowi by zliczał to jako odpowiednią ilość jedynek. Otóż... musiałbym wtedy znacznie rozbudować kontrolę poprawności wprowadzanych liczb rzymskich! Obecnie opiera się ona na prostym fakcie: wartość żadnego kolejnego tokenu nie może być mniejsza niż już obliczona suma cząstkowa (ret_val). Zapis 'VII' jest poprawny, zapis 'IIV' - już nie. Gdybym zostawił tylko 'I', przy konwersji liczby 'III' funkcja zwróciłaby zero :) Dla szczególnie dociekliwych - podpowiem, że kontrola nie jest zupełnie szczelna i mimo wszystko można przemycić niewłaściwy zapis ;)

Konwersja wyłącznie dla liczb z przedziału 1..3999. Na moje potrzeby (zmiana roku filmu) - to aż nadto.

Na koniec (o ile ktoś do tego miejsca doczytał :P) kilka ogólnych uwag o sposobie napisania funkcji. Miałem do wyboru użycie dwóch tablic, jednej na tokeny rzymskie i drugiej na odpowiedniki dziesiętne - lub tablicy rekordów. Pierwszy wariant mimo iż teoretycznie upraszczał strukturę programu - MÓGŁ spowodować problemy i przy pisaniu (łatwo się pomylić w odpowiednikach rom-dec) i przy EWENTUALNYM późniejszym rozszerzaniu funkcji na przykład poprzez zwiększanie zakresu konwertowanych liczb. Z tych samych względów zamiast kodować rozmiar tablicy numbers "na sztywno" - użyłem stałej numbers_max. A życie szybko uczy każdego programistę, że jedynie małą część kodu pisze się raz-na-zawsze :)

Ale sposoby pisania przejrzystego i łatwego do modyfikacji kodu - to już temat na zupełnie inne opowiadanie... :)