/*
 * Program wykorzystujacy wzorzec interpretera
 * do konwersji liczb rzymskich w stringu na int.
 */

#include <iostream>
#include <string>
#include <boost/algorithm/string/predicate.hpp>
#include <boost/foreach.hpp>
#include <boost/ptr_container/ptr_list.hpp>


/** Reprezentuje (pod)wyrazenie, bedace czescia ciagu cyfr liczby rzymskiej.
 * Kazde wyrazenie rozni sie aktualnym kontekstem, ktory jest
 * analogia "miejsca dziesietnego" w danej liczbie rzymskiej.
 * Od miejsca zaleza symbole dla poszczegolnych "cyfr" oraz mnoznik, czyli
 * np. w kontekscie "setek" symbol "D" reprezentuje "piec" z mnoznikiem 100,
 * czyli 500.
 * W ogolnosci liczba rzymska sklada sie z cyfr, ktore
 * sumuja sie do wartosci calej liczby, a takze z cyfr, ktore
 * modyfikuja nastepujace po nich cyfry tworzac "podwojne" cyfry.
 * (np. "IX" jest "podwojna" cyfra, a "V" pojedyncza).
 */
class Wyrazenie : boost::noncopyable
{
    public:

        /** Zwraca wartosc kolejnego, znajdujacego sie na poczatku ciagu s,
         * wyrazenia, w zaleznosci od aktualnego kontekstu.
         * Usuwa wykorzystane w aktualnym kroku cyfry z ciagu.
         */
        int interpretuj( std::string & s );

        /** Zwracaja symbole cyfr dla konkretnego - zaleznego od konkretnej
         * klasy pochodnej - kontekstu (miejsca w liczbie).
         * Mamy cztery rodzaje cyfr w systemie rzymskim: jeden, cztery,
         * piec i dziewiec. Odpowiedniki pozostalych cyfr arabskich sa
         * tworzone przez sumowanie w/w cyfr.
         * W systemie dziesietnym znaki odpowiadajace cyfrom sa zawsze takie
         * same, "1" jest taka sama dla jednosci, dziesiatek, setek itd.
         * Natomiast w systemie rzymskim "1" rozni sie w zaleznosci
         * od kontekstu: "I" dla jednosci, "X" dla dziesiatek itd.
         */
        virtual std::string jeden() = 0;
        virtual std::string cztery() = 0;
        virtual std::string piec() = 0;
        virtual std::string dziewiec() = 0;

        /** Mnoznik, przez ktory nalezy pomnozyc wynikowa cyfre w danym
         * kontekscie. Analogia do mnozenia kolejnych cyfr liczby dziesietnej
         * przez kolejne potegi 10.
         */
        virtual int mnoznik() = 0;
};

/** Oblicza wartosc wszystkich cyfr w danym kontekscie (miejscu w liczbie),
 * czyli np. dla wszystkich cyfr skladajacych sie na setki
 * i usuwa wykorzystane cyfry z ciagu.
 */
int Wyrazenie::interpretuj( std::string & s )
{
    /** Sprawdza, czy ciag wejsciowy zaczyna sie od podanego podciagu.
     */
    using boost::algorithm::istarts_with;

    if ( s.length() == 0 )
        return 0;

    /** Suma cyfr dla danego kontekstu */
    int suma = 0;

    /* Mamy dwa rodzaje cyfr podwojnych - dziewiec i cztery.
     * W jednym kontekscie zadne inne cyfry nie moga wystapic z 
     * nimi rownoczesnie.
     */
    if ( istarts_with( s, dziewiec() ) )
    {
        /* Usun dwa pierwsze znaki cyfry podwojnej z ciagu */
        s.erase( 0, 2 );
        suma += 9 * mnoznik();
        /* Po dziewiatce (i podobnie po czworce) nie moga wystapic
         * inne cyfry w jednym kontekscie, wiec mozemy wyjsc od razu
         */
        return suma;
    }
    else if ( istarts_with( s, cztery() ) )
    {
        s.erase( 0, 2 );
        suma += 4 * mnoznik();
        return suma;
    }
    else if ( istarts_with( s, piec() ) )
    {
        s.erase( 0, 1 );
        suma += 5 * mnoznik();
        /* Po piatce natomiast moga wystapic jedynki, wiec
         * nie mozemy wyjsc przedwczesnie */
    }

    /* Jedynki jako jedyne moga wystapic wielokrotnie po sobie
     * w jednym kontekscie, np. dla "III" zostanie 
     * trzykrotnie usuniety symbol jedynki i trykrotnie do sumy dodane
     * zostanie 1 * mnoznik, czyli po prostu mnoznik.
     */
    while ( istarts_with( s, jeden() ) )
    {
        s.erase( 0, 1 );
        suma += mnoznik();
    }

    return suma;
}

/** Konkretne klasy dla danego kontekstu.
 * Zwracaja symbole cyfr o konkretnym znaczeniu w danym kontekscie,
 * na przyklad "czworka" dla jednosci jest "IV", a dla setek "CD".
 */
class Tysiace : public Wyrazenie
{
    public:

        std::string jeden() { return "M"; }
        std::string cztery() { return " "; }
        std::string piec() { return " "; }
        std::string dziewiec() { return " "; }

        int mnoznik() { return 1000; }
};

class Setki : public Wyrazenie
{
    public:

        std::string jeden() { return "C"; }
        std::string cztery() { return "CD"; }
        std::string piec() { return "D"; }
        std::string dziewiec() { return "CM"; }
        
        int mnoznik() { return 100; }
};

class Dziesiatki : public Wyrazenie
{
    public:

        std::string jeden() { return "X"; }
        std::string cztery() { return "XL"; }
        std::string piec() { return "L"; }
        std::string dziewiec() { return "XC"; }
        
        int mnoznik() { return 10; }
};

class Jednosci : public Wyrazenie
{
    public:

        std::string jeden() { return "I"; }
        std::string cztery() { return "IV"; }
        std::string piec() { return "V"; }
        std::string dziewiec() { return "IX"; }
        
        int mnoznik() { return 1; }
};

int main()
{
    /* 2938 */
    std::string rzymska( "MMCMXXXVIII" );

    /* Stworzenie gramatyki liczb rzymskich, w ktorej wystepuja,
     * w kolejnosci, cyfry skladajace sie na: tysiace, setki, dziesiatki
     * i jednosci. W ten sposob kazda sekwencja znakow jest inaczej
     * interpretowana, w zaleznosci do tego, na jakim miejscu znajduje
     * sie w ciagu.
     * Tworzenie listy ma tylko na celu ulatwienie dalszego korzystania.
     * Ponadto jest to tylko jedna z mozliwosci, czesto korzysta sie z gramatyk
     * opartych o struktury drzewiaste.
     */
    boost::ptr_list< Wyrazenie > wyrazenia;
    wyrazenia.push_back( new Tysiace() );
    wyrazenia.push_back( new Setki() );
    wyrazenia.push_back( new Dziesiatki() );
    wyrazenia.push_back( new Jednosci() );

    int suma = 0;

    /* Przeanalizuj cale wyrazenie dla kolejnych kontekstow zgodnie z gramatyka.
     * Kolejno dla kazdego kontekstu przeanalizuj poczatek ciagu i usun
     * wykorzystane cyfry, dodajac do sumy aktualnie obliczane wyrazenia. Ciag
     * jest przetwarzany zgodnie z wczesniej ustalonym porzadkiem przy tworzeniu
     * listy (gramatyki) wyrazen, poczawszy od tysiecy po jednosci.
     */
    BOOST_FOREACH( boost::ptr_list< Wyrazenie >::reference w, wyrazenia )
    {
        /* Wywoluje interpretuj() dla konkretnego potomka klasy Wyrazenie
         * (dziala mechanizm funkcji wirtualnych)
         */
        suma += w.interpretuj( rzymska );
    }

    assert( suma == 2938 );
    std::cout << suma << std::endl;

    return 0;
}