In this article, we have explained two efficient approaches / algorithms to convert Roman number to Integer. We have presented the implementation as well.

Table of contents:

1. Introduction to Roman System
2. Approach 1: Using switch statements
3. Approach 2: Using Hash Map

Prerequisite:

• Switch Statements
• Hash Map / Hash Table

Let us get started with Roman to Integer. This is similar to Leetcode Problem 13. Roman to Integer.

Introduction to Roman System

The roman number system consists of 7 main symbols which are I, V, X, L, C, D, M which represent 1, 5, 10, 50, 100, 500, 1000 integer numbers respectively.

Based on these roman symbols we can construct any integer number eg, roman number for 1932 is MCMXXXII which when broken down is 1000(M), 900(CM), 10(X) 10(X) 10(X), 1(I) 1(I) which sums up to 1932.

Some key things to note before trying to convert a roman numeral into its integer equivalent.

Roman numerals are written in descending order from left to right with exceptions where the left character is less than the right character.
Such cases include the following characters; I, X and C.

Case 1: I -> IV = (5 - 1) and IX = (10 - 1) - subtract 1

Case 2: X -> XL = (50 - 10) and XC = (100 - 10) - subtract 10

Case 3: C -> CD = (500 - 100) and CM = (1000 - 100) - subtract 100

In such cases we subtract the left value from the right to get our integer representation like show above.
Knowing that makes our problem easier to solve.

Lets define the problem programmatically for better understanding. What are the inputs and outputs. Given a roman number as input, the expected output is its integer equivalent.

Following the above our program should take as input the string MCMXXXII and return an integer output 1932.

How to solve this problem with code? I will discuss 2 approaches here.

Approach 1: Using switch statements.
Approach 2: Using a hashmap.

Approach 1: Using switch statements

A switch statement evaluates an expression and matches the value of the expression to a case and executes a statement associated with that case.
You can read up on c++ switch statements on the link at the end of this post.
In our example, our expression is the character of the input string and the case is the roman representation of that character and based on this we will assign a value to a variable.

Algorithm

1. Initialize two variables, result and temporary variable n with 0.
2. Loop through the string from right to left, backwards.
3. Compare each character with a switch case, if there is a match assign the case value to variable n.
4. Multiply 4 by n, if the answer is less than result then subract from result otherwise add to result and proceed with the loop.
5. Return the result.

Code

#include<bits/stdc++.h>

int romanToInt(std::string str){

    int result = 0, n = 0;
    
    for(int i = str.length() - 1; i >= 0; i--){
        switch(str[i]){
            case 'I': n = 1; break;
            case 'V': n = 5; break;
            case 'X': n = 10; break;
            case 'L': n = 50; break;
            case 'C': n = 100; break;
            case 'D': n = 500; break;
            case 'M': n = 1000; break;
        }
        (4 * n < result) ? result -= n : result += n;
    }
    return result;
}

int main(){
    std::string str = "MCMXXXII";
    std::cout << romanToInt(str) << std::endl;
    return 0;
}

Code Explanation

The romanToInt() function takes a string as input and returns an integer representation of the string which is equivalent to a roman number.
Line 1: We include every standard library and STL include file using the #include<bits/stdc++.h> header.
Line 2: We declare the romanToInt() function.
Line 3: We declare two variables, the result variable that will hold the result of our computation and n which is a temporary variable we will use during computations, both are initialized as 0 at the begining of the program.
Line 4: We go through the roman string backwards using a for loop, from size of the string down to 0. We need to evaluate the roman values in ascending order for this approach to work.
Line 5 - 13: For each character in the roman string we use a switch case statement for evaluation which returns the corresponding value of that character.
That is if the character matches the one in the switch case, we assign the corresponding value to n, after which n gets evaluated at the next if-else statement.
Line 14: Here we use a short hand if else statement, that is if 4 * n is less than result variable, we subtract n from result, otherwise we add n to the result.

The breakdown is as follows, for the roman MCMXXXII our loop will do the following 8 iterations.

1st Iteration n = 0, result + 1 result = 1;
2st Iteration n = 1, result + 1 result = 2;
3st Iteration n = 2, result + 10 result = 12;
4st Iteration n = 12, result + 10 result = 22;
5st Iteration n = 22, result + 10 result = 32;
6st Iteration n = 32, result + 1000 result = 1032;
7st Iteration n = 1032, result - 100 result = 932;
8st Iteration n = 932, result + 1000 result = 1932;

Line 16: We return result which is an integer equivalent to the roman numeral.

Analysis:

The time complexity is linear O(n), n is the length of the string. we go through all its characters for our computation.
The space is constant, we dont use any additional space.

Approach 2: Using Hash Map

Here we use a hashmap which maps keys to values forming a pair. In this case the roman characters are mapped to their corresponding integer equivalents.
When we lookup a roman character, the hashmap will return the corresponding value based on it mapping.

You can read up on unordered_map and hashtables in general to understand the inner workings of this very useful data structure in the proveded links at the end of this post.

Algorithm

1. Initialize result variable with 0.
2. Create a hashmap and insert values to it, the character as the key and its integer equivalent as its value to form a pair.
3. Loop through the string, take one character and check for its corresponding integer value from hashmap.
4. If current character value is less than next character value, subtract the two and add their answer to result variable, increment the loop variable and continue, otherwise add the current character value to result and proceed with the loop.
5. Return result.

Code

#include<bits/stdc++.h>

int romanToInt(std::string str){
    int result = 0;

    std::unordered_map<char, int> romanInt;

    romanInt['I'] = 1;
    romanInt['V'] = 5;
    romanInt['X'] = 10;
    romanInt['L'] = 50;
    romanInt['C'] = 100;
    romanInt['D'] = 500;
    romanInt['M'] = 1000;
    

    for(int i = 0; i < str.length(); i++){
        if(romanInt[str[i]] < romanInt[str[i+1]]){
            result += romanInt[str[i+1]] - romanInt[str[i]];
            i += 1;
            continue;
        }
        result += romanInt[str[i]];
    }

    return result;
}

int main(){
    std::string str = "MCMXXXII";
    std::cout << romanToInt(str) << std::endl;
    return 0;
}

Code Explanation

I will explain new code that is not explained in the previous approach.
Line 4: We declare a hash map whereby the key will be of character type and the value of integer type.
Line 5 - 11: We initialize values of the hashmap so when we call a key it returns its mapped value.
Line 12: We use a for loop to got through the string characters.
Line 13 - 18: We do an if check, if the present value is less than the next value, we subtract the two and add the result to result variable, increment i and continue with the loop, otherwise we just add the value to result an proceed with the loop.

1st Iteration i = 0, result = 1000
2nd Iteration i = 1, result = 1000 + (1000 - 100) = 1900
3rd Iteration i = 3, result = 1910
4th Iteration i = 4, result = 1920
5th Iteration i = 5, result = 1930
6th Iteration i = 6, result = 1931
7th Iteration i = 7, result = 1932

Line 20: We return the result variable which will now hold the integer equivalent of the roman input.

Analysis:

The procedure takes linear time O(n) n being length of the string.
It uses constant space O(1) as no extra space is used.

Question:

Can you solve the same problem using if-else conditional statements in the place of switch statements?

With this article at OpenGenus, you must have complete idea of how to convert Roman number to Integer.