/* package whatever; // don't place package name! */
import java.util.HashMap;
import java.util.Map;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

/**
 * Optimizations:
 * - Creates a map to get each roman numeral decimal value with O(1) complexity
 * - All Regex compiled only once
 * - Minimum code run each time after initialization
 */

/* Name of the class has to be "Main" only if the class is public. */
class RomanToDecimalConverter {
	public static void main (String[] args) {
		printRomanToDecimal("XCIX");
        printRomanToDecimal("MMMCMXCIX");

        //error cases
        printRomanToDecimal("IIX");
        printRomanToDecimal("IIXX");
        printRomanToDecimal("ABC");
        printRomanToDecimal("IVX");
	}
	
	private static void printRomanToDecimal(String s) {
		int decimal = convert(s);
		String output = decimal != -1 ? ""+decimal : "Invalid roman numerals";
		System.out.println(s + ": " + output);
	}
	
    private static final Map<String, Integer> ROMAN_NUMERALS_TO_DECIMAL_MAP;

    static {
        //init the correspondence map <RomanNumeral, DecimalValue> when the class is loaded
        ROMAN_NUMERALS_TO_DECIMAL_MAP = new HashMap<>();

        String[] romanNumerals = {"M","CM","D","CD","C","XC","L","XL","X","IX","V","IV","I"};
        int[] decimalValues = {1000,900,500,400,100,90,50,40,10,9,5,4,1};

        //let's map each roman numeral to its decimal value
        for (int i = 0; i < decimalValues.length; i++) {
            ROMAN_NUMERALS_TO_DECIMAL_MAP.put(romanNumerals[i], decimalValues[i]);
        }
    }

    //checks roman numerals format (max number is 3999 = MMMCMXCIX)
    //@see http://w...content-available-to-author-only...e.ro/reguli_scriere_cifre_numere_romane.php?lang=en
    private static final Pattern CHECK_ROMAN_NUMERALS_FORMAT_REGEX =
            Pattern.compile("^(M{0,3})(CM|CD|D?C{0,3})(XC|XL|L?X{0,3})(IX|IV|V?I{0,3})$");

    //we need this compiled regex to match each roman numeral one by one
    //from left to right from the highest to the lowest decimal value
    private static final Pattern FIND_ROMAN_NUMERALS_ONE_BY_ONE_REGEX =
            Pattern.compile("M|CM|D|CD|C|XC|L|XL|X|IX|V|IV|I");

    private static boolean containsValidRomanNumerals(String s) {
        return !(s == null || s.isEmpty() || !CHECK_ROMAN_NUMERALS_FORMAT_REGEX.matcher(s).matches());
    }

    /**
     * Converts roman numerals to their decimal value
     * @param s String containing roman numerals
     * @return decimal value corresponding to the roman numerals input
     */
    public static int convert(String s) {
        if (!containsValidRomanNumerals(s)) return -1;

        final Matcher matcher = FIND_ROMAN_NUMERALS_ONE_BY_ONE_REGEX.matcher(s);

        int sum = 0;
        //every time we find a roman numeral...
        while (matcher.find()) {
            //...let's add its decimal value to the sum
            sum += ROMAN_NUMERALS_TO_DECIMAL_MAP.get(matcher.group(0));
        }

        return sum;
    }
}