Roman to Integer Conversion in DSA Rust - 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, book chapters, and movie titles. Your program will help translate these into numbers we use every day.

🎯 Goal: Build a Rust program that converts a Roman numeral string into its integer value using a dictionary and a loop.

📋 What You'll Learn

Create a dictionary mapping Roman numeral characters to their integer values.

Create a variable to hold the total integer value.

Use a loop to process each character in the Roman numeral string.

Handle the subtraction rule where a smaller numeral before a larger numeral means subtraction.

Print the final integer value.

💡 Why This Matters

🌍 Real World

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

💼 Career

Understanding how to map characters to values and process strings with rules is useful in parsing, data processing, and building interpreters or compilers.

1

Create the Roman numeral dictionary

Create a HashMap called roman_map that maps these exact Roman numeral characters to their integer values: 'I' to 1, 'V' to 5, 'X' to 10, 'L' to 50, 'C' to 100, 'D' to 500, and 'M' to 1000.

DSA Rust

use std::collections::HashMap;

// Create the roman_map HashMap with Roman numeral keys and integer values
// Your code here

Hint

Use HashMap::new() to create the map and insert to add each Roman numeral and its value.

2

Set up the Roman numeral string and total variable

Add a variable called roman and set it to the string "MCMXCIV". Also create a variable called total and set it to 0.

DSA Rust

use std::collections::HashMap;

fn main() {
    let mut roman_map = HashMap::new();
    roman_map.insert('I', 1);
    roman_map.insert('V', 5);
    roman_map.insert('X', 10);
    roman_map.insert('L', 50);
    roman_map.insert('C', 100);
    roman_map.insert('D', 500);
    roman_map.insert('M', 1000);

    // Create the roman string and total integer variable
    // Your code here
}

Hint

Use let roman = "MCMXCIV"; and let mut total = 0; to create these variables.

3

Convert Roman numeral to integer using a loop

Use a for loop with index i from 0 to roman.len() - 1 to process each character in roman. Inside the loop, get the integer value of the current character and the next character from roman_map. If the current value is less than the next value, subtract the current value from total. Otherwise, add the current value to total. After the loop, add the value of the last character to total.

DSA Rust

use std::collections::HashMap;

fn main() {
    let mut roman_map = HashMap::new();
    roman_map.insert('I', 1);
    roman_map.insert('V', 5);
    roman_map.insert('X', 10);
    roman_map.insert('L', 50);
    roman_map.insert('C', 100);
    roman_map.insert('D', 500);
    roman_map.insert('M', 1000);

    let roman = "MCMXCIV";
    let mut total = 0;

    // Loop through roman string except last character
    // Your code here
}

Hint

Convert the string to a vector of chars. Use a for loop from 0 to length - 1. Compare current and next values from the map. Add or subtract accordingly. Finally, add the last character's value.

4

Print the final integer value

Write a println! statement to print the value of total.

DSA Rust

use std::collections::HashMap;

fn main() {
    let mut roman_map = HashMap::new();
    roman_map.insert('I', 1);
    roman_map.insert('V', 5);
    roman_map.insert('X', 10);
    roman_map.insert('L', 50);
    roman_map.insert('C', 100);
    roman_map.insert('D', 500);
    roman_map.insert('M', 1000);

    let roman = "MCMXCIV";
    let mut total = 0;

    let chars: Vec = roman.chars().collect();
    for i in 0..chars.len() - 1 {
        let current = roman_map[&chars[i]];
        let next = roman_map[&chars[i + 1]];
        if current < next {
            total -= current;
        } else {
            total += current;
        }
    }
    total += roman_map[&chars[chars.len() - 1]];

    // Print the total value
    // Your code here
}

Hint

Use println!("{}", total); to show the final number.

Practice

1. What is the main rule to convert Roman numerals to integers?

easy

A. Multiply values of all symbols

B. Add values of symbols, subtract if a smaller symbol is before a larger one

C. Add values only if symbols are the same

D. Subtract values of all symbols

Solution

1. Step 1: Understand Roman numeral rules

   Roman numerals are added normally, but if a smaller numeral appears before a larger one, it is subtracted.

2. Step 2: Apply the rule to conversion

   When converting, add each symbol's value unless a smaller symbol precedes a larger one, then subtract the smaller.

3. Final Answer:

   Add values of symbols, subtract if a smaller symbol is before a larger one -> Option B

4. Quick Check:

   Roman to integer = add or subtract based on order [OK]

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

Common Mistakes:

• Always adding without subtraction
• Multiplying values instead of adding
• Ignoring order of symbols

2. Which Rust code snippet correctly defines a function header for converting a Roman numeral string to an integer?

easy

A. fn roman_to_int(s: &str) -> i32 {

B. fn romanToInt(s: String) -> int {

C. function roman_to_int(s: &str) -> i32 {

D. fn roman_to_int(s: &String) -> i64 {

Solution

1. Step 1: Check Rust function syntax

   Rust functions start with fn, use snake_case, and specify parameter types and return type correctly.

2. Step 2: Validate each option

   fn roman_to_int(s: &str) -> i32 { uses correct Rust syntax: fn, snake_case, &str parameter, and i32 return type. Others have syntax errors or wrong types.

3. Final Answer:

   fn roman_to_int(s: &str) -> i32 { -> Option A

4. Quick Check:

   Rust fn header with &str and i32 return [OK]

Hint: Use fn, snake_case, &str param, i32 return [OK]

Common Mistakes:

• Using camelCase instead of snake_case
• Wrong parameter or return types
• Using 'function' keyword (not Rust)

3. What is the output of this Rust code snippet?

fn main() {
    let s = "IX";
    let result = roman_to_int(s);
    println!("{}", result);
}

fn roman_to_int(s: &str) -> i32 {
    let mut total = 0;
    let mut prev = 0;
    for c in s.chars().rev() {
        let value = match c {
            'I' => 1,
            'V' => 5,
            'X' => 10,
            _ => 0,
        };
        if value < prev {
            total -= value;
        } else {
            total += value;
        }
        prev = value;
    }
    total
}

medium

A. 6

B. 11

C. Error

D. 9

Solution

1. Step 1: Trace characters in reverse

   Input "IX" reversed is 'X' then 'I'. 'X' = 10, 'I' = 1.

2. Step 2: Calculate total with subtraction rule

   Start total=0, prev=0. 'X' (10) >= prev(0), total=10, prev=10. Next 'I' (1) < prev(10), total=10-1=9, prev=1.

3. Final Answer:

   9 -> Option D

4. Quick Check:

   "IX" = 9 [OK]

Hint: Traverse string backward, subtract if smaller before larger [OK]

Common Mistakes:

• Not reversing string for correct subtraction
• Adding all values without subtraction
• Misassigning values to characters

4. Identify the bug in this Rust function for Roman to integer conversion:

fn roman_to_int(s: &str) -> i32 {
    let mut total = 0;
    let mut prev = 0;
    for c in s.chars() {
        let value = match c {
            'I' => 1,
            'V' => 5,
            'X' => 10,
            _ => 0,
        };
        if value > prev {
            total += value - 2 * prev;
        } else {
            total += value;
        }
        prev = value;
    }
    total
}

medium

A. Loop should iterate in reverse order

B. Subtracting twice prev is incorrect

C. Match arms missing some Roman numerals

D. prev variable should be mutable

Solution

1. Step 1: Inspect the match expression

   The match only handles 'I'(1), 'V'(5), 'X'(10). It misses 'L'(50), 'C'(100), 'D'(500), 'M'(1000), causing other symbols to map to 0 and produce wrong results.

2. Step 2: Verify other options

   A: Forward iteration with 'value - 2*prev' is valid for handling subtractive notation. B: The 2*prev subtraction corrects the previously added prev value. D: 'prev' is already mutable.

3. Final Answer:

   Match arms missing some Roman numerals -> Option C

4. Quick Check:

   Match must cover I,V,X,L,C,D,M [OK]

Hint: Include match arms for all Roman numerals [OK]

Common Mistakes:

• Incomplete match arms
• Not handling all Roman numerals
• Forgetting to make prev mutable (already mutable here)

5. Given the Roman numeral string "MCMXCIV", what integer does the following Rust function return?

fn roman_to_int(s: &str) -> i32 {
    let mut total = 0;
    let mut prev = 0;
    for c in s.chars().rev() {
        let value = match c {
            'I' => 1,
            'V' => 5,
            'X' => 10,
            'L' => 50,
            'C' => 100,
            'D' => 500,
            'M' => 1000,
            _ => 0,
        };
        if value < prev {
            total -= value;
        } else {
            total += value;
        }
        prev = value;
    }
    total
}

hard

A. 1994

B. 1904

C. 2004

D. None of the above

Solution

1. Step 1: Reverse and assign values

   Reverse "MCMXCIV" to "VICXMCM". Values: V=5, I=1, C=100, X=10, M=1000, C=100, M=1000.

2. Step 2: Calculate total with subtraction rule

   Start total=0, prev=0. - V(5) >= prev(0): total=5, prev=5 - I(1) < prev(5): total=5-1=4, prev=1 - C(100) >= prev(1): total=4+100=104, prev=100 - X(10) < prev(100): total=104-10=94, prev=10 - M(1000) >= prev(10): total=94+1000=1094, prev=1000 - C(100) < prev(1000): total=1094-100=994, prev=100 - M(1000) >= prev(100): total=994+1000=1994, prev=1000

3. Final Answer:

   1994 -> Option A

4. Quick Check:

   "MCMXCIV" = 1994 [OK]

Hint: Reverse string, subtract if smaller before larger [OK]

Common Mistakes:

• Not reversing string before processing
• Misassigning values to symbols
• Ignoring subtraction rule