Roman to Integer Conversion in DSA C++ - Build from Scratch

Roman to Integer Conversion

📖 Scenario: You are building a simple tool to convert Roman numerals into regular numbers. Roman numerals are used in clocks, books, and movie titles. Your program will help translate these into numbers we use every day.

🎯 Goal: Build a program that takes a Roman numeral string and converts it into its integer value.

📋 What You'll Learn

Create a dictionary (map) of Roman numeral characters and their integer values.

Create a variable to hold the total integer value.

Use a loop to process the Roman numeral string and apply the subtraction rule.

Print the final integer value.

💡 Why This Matters

🌍 Real World

Roman numerals appear in clocks, book chapters, movie sequels, and historical dates. Converting them to integers helps computers understand and process these values.

💼 Career

Understanding how to map characters to values and apply rules in loops is essential for parsing and interpreting data formats, a common task in software development.

1

Create Roman numeral map

Create a std::map called roman_map with these exact entries: 'I': 1, 'V': 5, 'X': 10, 'L': 50, 'C': 100, 'D': 500, 'M': 1000.

DSA C++

#include 
#include 
#include 

int main() {
    // Create roman_map here

}

Hint

Use std::map and initialize it with the given Roman numeral pairs.

2

Initialize variables

Create a std::string variable called roman and set it to "MCMXCIV". Create an int variable called total and set it to 0.

DSA C++

#include 
#include 
#include 

int main() {
    std::map roman_map = {
        {'I', 1}, {'V', 5}, {'X', 10}, {'L', 50},
        {'C', 100}, {'D', 500}, {'M', 1000}
    };

    // Create roman string and total variable here

}

Hint

Use std::string roman = "MCMXCIV"; and int total = 0;.

3

Convert Roman numeral to integer

Use a for loop with int i = 0 and i < roman.size() to iterate over roman. Inside the loop, if i + 1 < roman.size() and roman_map[roman[i]] < roman_map[roman[i + 1]], subtract roman_map[roman[i]] from total. Otherwise, add roman_map[roman[i]] to total.

DSA C++

#include 
#include 
#include 

int main() {
    std::map roman_map = {
        {'I', 1}, {'V', 5}, {'X', 10}, {'L', 50},
        {'C', 100}, {'D', 500}, {'M', 1000}
    };

    std::string roman = "MCMXCIV";
    int total = 0;

    // Add for loop to convert roman to integer here

}

Hint

Use a for loop to check each character and apply subtraction if the next value is larger.

4

Print the integer result

Write std::cout << total << std::endl; to print the final integer value.

DSA C++

#include 
#include 
#include 

int main() {
    std::map roman_map = {
        {'I', 1}, {'V', 5}, {'X', 10}, {'L', 50},
        {'C', 100}, {'D', 500}, {'M', 1000}
    };

    std::string roman = "MCMXCIV";
    int total = 0;

    for (int i = 0; i < roman.size(); i++) {
        if (i + 1 < roman.size() && roman_map[roman[i]] < roman_map[roman[i + 1]]) {
            total -= roman_map[roman[i]];
        } else {
            total += roman_map[roman[i]];
        }
    }

    // Print total here
}

Hint

Use std::cout << total << std::endl; to show the result.

Practice

1. What is the value of the Roman numeral IX when converted to an integer?

easy

A. 11

B. 6

C. 9

D. 19

Solution

1. Step 1: Understand Roman numeral rules for subtraction

   In Roman numerals, when a smaller numeral appears before a larger one, it is subtracted. Here, I (1) is before X (10), so subtract 1 from 10.

2. Step 2: Calculate the integer value

   10 - 1 = 9.

3. Final Answer:

   9 -> Option C

4. Quick Check:

   IX = 9 [OK]

Hint: Subtract when smaller numeral precedes larger one [OK]

Common Mistakes:

• Adding values instead of subtracting for IX
• Confusing IX with XI
• Ignoring subtraction rule

2. Which of the following C++ code snippets correctly initializes a map for Roman numeral values?

easy

A. std::map roman{{'I', 1}, {'V', 5}, {'X', 10}};

B. std::map roman = {'I':1, 'V':5, 'X':10};

C. std::map roman = {('I', 1), ('V', 5), ('X', 10)};

D. std::map roman = [('I', 1), ('V', 5), ('X', 10)];

Solution

1. Step 1: Check C++ map initialization syntax

   In modern C++, maps can be initialized using initializer lists with curly braces and pairs inside curly braces.

2. Step 2: Identify correct syntax

   std::map roman{{'I', 1}, {'V', 5}, {'X', 10}}; uses double braces with pairs correctly. Options A, B, and C use invalid syntax for map initialization.

3. Final Answer:

   std::map roman{{'I', 1}, {'V', 5}, {'X', 10}}; -> Option A

4. Quick Check:

   Correct map initialization syntax [OK]

Hint: Use double braces with pairs for map initialization [OK]

Common Mistakes:

• Using colon instead of comma in initializer list
• Using parentheses instead of braces for pairs
• Using square brackets for initialization

3. What is the output of the following C++ code snippet?

std::string s = "MCMXCIV";
std::map roman{{'I',1},{'V',5},{'X',10},{'L',50},{'C',100},{'D',500},{'M',1000}};
int result = 0;
for (int i = 0; i < s.size(); ++i) {
  if (i + 1 < s.size() && roman[s[i]] < roman[s[i+1]]) {
    result -= roman[s[i]];
  } else {
    result += roman[s[i]];
  }
}
std::cout << result << std::endl;

medium

A. 1904

B. 1994

C. 1094

D. 1949

Solution

1. Step 1: Trace the loop through the string "MCMXCIV"

   Check each character and compare with next: M(1000), C(100), M(1000), X(10), C(100), I(1), V(5). Subtract when current < next, else add.

2. Step 2: Calculate result step-by-step

   Positions: M(1000, add), C(100, next M=1000 > 100 subtract), M(1000, add), X(10, next C=100 > 10 subtract), C(100, add), I(1, next V=5 > 1 subtract), V(5, add). Calculation: 1000 - 100 + 1000 - 10 + 100 - 1 + 5 = 1994.

3. Final Answer:

   1994 -> Option B

4. Quick Check:

   Roman "MCMXCIV" = 1994 [OK]

Hint: Subtract if current < next, else add [OK]

Common Mistakes:

• Adding all values without subtraction
• Misreading character values
• Off-by-one errors in loop

4. Identify the bug in the following C++ code for Roman to Integer conversion:

int romanToInt(std::string s) {
  std::map roman{{'I',1},{'V',5},{'X',10},{'L',50},{'C',100},{'D',500},{'M',1000}};
  int result = 0;
  for (int i = 0; i < s.size(); ++i) {
    if (roman[s[i]] < roman[s[i+1]]) {
      result -= roman[s[i]];
    } else {
      result += roman[s[i]];
    }
  }
  return result;
}

medium

A. Accessing s[i+1] without checking bounds causes out-of-range error

B. Using map instead of unordered_map causes slow lookup

C. Result variable should be initialized to 1 instead of 0

D. The subtraction logic is reversed

Solution

1. Step 1: Analyze loop and index usage

   The loop runs from i = 0 to s.size() - 1, but inside the loop it accesses s[i+1] without checking if i+1 is within bounds.

2. Step 2: Identify potential runtime error

   When i is the last index, s[i+1] is out of range, causing undefined behavior or crash.

3. Final Answer:

   Accessing s[i+1] without checking bounds causes out-of-range error -> Option A

4. Quick Check:

   Check index bounds before accessing s[i+1] [OK]

Hint: Always check index bounds before accessing next element [OK]

Common Mistakes:

• Ignoring index bounds causing runtime errors
• Incorrect initialization of result
• Misunderstanding subtraction logic

5. Given the Roman numeral string "XLIX", which of the following C++ code snippets correctly converts it to an integer?

hard

A. int romanToInt(std::string s) {
std::map roman{{'I',1},{'V',5},{'X',10},{'L',50},{'C',100},{'D',500},{'M',1000}};
int total = 0;
for (int i = 0; i < s.size(); ++i) {
total += roman[s[i]];
}
return total;
}

B. int romanToInt(std::string s) {
std::map roman{{'I',1},{'V',5},{'X',10},{'L',50},{'C',100},{'D',500},{'M',1000}};
int total = 0;
for (int i = 0; i < s.size(); ++i) {
if (roman[s[i]] > roman[s[i+1]]) {
total += roman[s[i]];
} else {
total -= roman[s[i]];
}
}
return total;
}

C. int romanToInt(std::string s) {
std::map roman{{'I',1},{'V',5},{'X',10},{'L',50},{'C',100},{'D',500},{'M',1000}};
int total = 0;
for (int i = s.size() - 1; i >= 0; --i) {
if (roman[s[i]] < roman[s[i+1]]) {
total -= roman[s[i]];
} else {
total += roman[s[i]];
}
}
return total;
}

D. int romanToInt(std::string s) {
std::map roman{{'I',1},{'V',5},{'X',10},{'L',50},{'C',100},{'D',500},{'M',1000}};
int total = 0;
for (int i = 0; i < s.size(); ++i) {
if (i + 1 < s.size() && roman[s[i]] < roman[s[i+1]]) {
total -= roman[s[i]];
} else {
total += roman[s[i]];
}
}
return total;
}

Solution

1. Step 1: Check correct subtraction logic with bounds check

   int romanToInt(std::string s) { std::map roman{{'I',1},{'V',5},{'X',10},{'L',50},{'C',100},{'D',500},{'M',1000}}; int total = 0; for (int i = 0; i < s.size(); ++i) { if (i + 1 < s.size() && roman[s[i]] < roman[s[i+1]]) { total -= roman[s[i]]; } else { total += roman[s[i]]; } } return total; } correctly checks if next character exists and if current value is less than next, then subtracts; else adds.

2. Step 2: Verify other options for errors

   int romanToInt(std::string s) { std::map roman{{'I',1},{'V',5},{'X',10},{'L',50},{'C',100},{'D',500},{'M',1000}}; int total = 0; for (int i = 0; i < s.size(); ++i) { if (roman[s[i]] > roman[s[i+1]]) { total += roman[s[i]]; } else { total -= roman[s[i]]; } } return total; } reverses logic and lacks bounds check; int romanToInt(std::string s) { std::map roman{{'I',1},{'V',5},{'X',10},{'L',50},{'C',100},{'D',500},{'M',1000}}; int total = 0; for (int i = s.size() - 1; i >= 0; --i) { if (roman[s[i]] < roman[s[i+1]]) { total -= roman[s[i]]; } else { total += roman[s[i]]; } } return total; } accesses s[i+1] when i is last index (out-of-bounds); int romanToInt(std::string s) { std::map roman{{'I',1},{'V',5},{'X',10},{'L',50},{'C',100},{'D',500},{'M',1000}}; int total = 0; for (int i = 0; i < s.size(); ++i) { total += roman[s[i]]; } return total; } adds all values ignoring subtraction rule.

3. Final Answer:

   The code in Step 1 -> Option D

4. Quick Check:

   Check bounds and subtract if current < next [OK]

Hint: Check next char exists before subtracting current [OK]

Common Mistakes:

• Not checking index bounds before accessing s[i+1]
• Reversing subtraction logic
• Ignoring subtraction rule completely