Roman numerals to decimal in SQL

Earlier this week I got tangled up doing a Roman Numeral conversion in my head. So of course my second thought, right after “Doh!”, was “I bet I can write a SQL statement to do this for me next time.”

The algorithm to convert roman numerals to decimal numbers is straightforward.

    For each character, starting from the RIGHT (lowest value Roman numeral):

  • Convert the character into the value it represents
  • If the character’s value is greater than or equal to the previous one, add the value to the running total
  • If character’s value is less than the previous one, subtract the value from the running total

Let’s look at a couple of examples:

    IX
    Starting from the right:

  • X = 10; Running total = 10
  • I = 1; 1 < 10; Running total = 9
  • Final result: 9
    MCMLXXVII
    Starting from the right:

  • I = 1; Running total = 1
  • I = 1; Running total = 2
  • V = 5; Running total = 7
  • X = 10; Running total = 17
  • X = 10; Running total = 27
  • L = 50; Running total = 77
  • M = 1000; Running total = 1077
  • C = 100; 100 < 1000; Running total = 977
  • M = 1000; Running total = 1977

Here’s an online converter

This is a lovely place to use Recursive With in SQL. We’ll use a CTE, aka recursive subquery, to chomp the string one character at a time from the right, keeping a running total as we go; first decode the character, then add or subtract as appropriate to the running total until we’re out of characters.

See my previous post on Recursion with Recursive With. From that post, here’s the recursive WITH basic syntax:

WITH Tablename (col1, col2, col3...) AS
(SELECT A, B, C... FROM dual                         --anchor member
UNION ALL
SELECT newA, newB, newC... FROM Tablename WHERE...   --recursive member
)
SELECT ... FROM Tablename WHERE ...

Let’s start with just identifying the characters and substrings we want to work on, using substr and length.
Substr: http://docs.oracle.com/database/121/SQLRF/functions196.htm#SQLRF06114
Length: http://docs.oracle.com/database/121/SQLRF/functions100.htm#SQLRF00658

WITH Roman (Numeral) AS
(SELECT 'MDCCVIII' AS Numeral FROM dual),
RomToDec (ThisOne, Remaining, Pos) AS
(SELECT CAST(NULL AS varchar2(4000)) AS ThisOne, Roman.Numeral AS Remaining , LENGTH(Roman.Numeral) AS Pos 
FROM Roman
UNION ALL
SELECT  
substr(RomToDec.Remaining,LENGTH(RomToDec.Remaining),1)  AS ThisOne, 
substr(RomToDec.Remaining,1,LENGTH(RomToDec.Remaining)-1) AS Remaining,
LENGTH(RomToDec.Remaining)-1 AS Pos
FROM RomToDec                           
WHERE Pos > 0
)
SELECT ThisOne, Remaining, Pos FROM RomToDec
;
VAL THISONE  REMAINING     POS
0     -       MDCCVIII     8
0     I       MDCCVII      7
0     I       MDCCVI       6
0     I       MDCCV        5
0     V       MDCC         4
0     C       MDC          3
0     C       MD           2
0     D       M            1
0     M       -            0
0     -       -            -

Now we use CASE to turn the Roman Numeral character into a number.
Case: http://docs.oracle.com/database/121/SQLRF/expressions004.htm#SQLRF20037

WITH Roman (ThisOne) AS
(SELECT 'M' AS ThisOne FROM dual)
SELECT 
CASE ThisOne 
  WHEN 'M' THEN 1000
  WHEN 'D' THEN 500
  WHEN 'C' THEN 100
  WHEN 'L' THEN 50
  WHEN 'X' THEN 10
  WHEN 'V' THEN 5
  WHEN 'I' THEN 1
ELSE 0 END AS ThisDec
FROM Roman;

I’m only going to deal with values of less than 5000 so M will be the largest we need. I’m going to patch that in to my query-in-progress, and also add a “Val” column to hold the running total:

WITH Roman (Numeral) AS
(SELECT 'MDCCVIII' AS Numeral FROM dual),
RomToDec (Val, ThisOne, ThisDec, Remaining, Pos) AS
(SELECT 0 AS Val, CAST(NULL AS varchar2(4000)) AS ThisOne, 0 AS ThisDec, Roman.Numeral AS Remaining , LENGTH(Roman.Numeral) AS Pos 
FROM Roman
UNION ALL
SELECT 
RomToDec.Val, 
substr(RomToDec.Remaining,LENGTH(RomToDec.Remaining),1)  AS ThisOne, 
CASE substr(RomToDec.Remaining,LENGTH(RomToDec.Remaining),1)  
  WHEN 'M' THEN 1000
  WHEN 'D' THEN 500
  WHEN 'C' THEN 100
  WHEN 'L' THEN 50
  WHEN 'X' THEN 10
  WHEN 'V' THEN 5
  WHEN 'I' THEN 1
ELSE 0 END AS ThisDec,
substr(RomToDec.Remaining,1,LENGTH(RomToDec.Remaining)-1) AS Remaining,
LENGTH(RomToDec.Remaining)-1 AS Pos
FROM RomToDec                           
WHERE Pos > 0
)
SELECT Val, ThisOne, ThisDec, Remaining, Pos FROM RomToDec
;
VAL    THISONE  THISDEC     REMAINING    POS
0      -        0           MDCCVIII     8
0      I        1           MDCCVII      7
0      I        1           MDCCVI       6
0      I        1           MDCCV        5
0      V        5           MDCC         4
0      C      100           MDC          3
0      C      100           MD           2
0      D      500           M            1
0      M     1000           -            0

An alternative to using CASE here would be to add another inline table in the WITH clause and join with it:

WITH Roman (Numeral) AS
(SELECT 'MDCCVIII' AS Numeral FROM dual),
CharValues (Numeral, VALUE) AS (
SELECT 'M', 1000 FROM dual UNION ALL
SELECT 'D', 500  FROM dual UNION ALL
SELECT 'C', 100  FROM dual UNION ALL
SELECT 'L', 50   FROM dual UNION ALL
SELECT 'X', 10   FROM dual UNION ALL
SELECT 'V', 5    FROM dual UNION ALL
SELECT 'I', 1    FROM dual ),
RomToDec (Val, ThisOne, ThisDec, Remaining, Pos) AS
(SELECT 0 AS Val, CAST(NULL AS varchar2(4000)) AS ThisOne, 0 AS ThisDec, Roman.Numeral AS Remaining , LENGTH(Roman.Numeral) AS Pos 
FROM Roman
UNION ALL
SELECT 
RomToDec.Val, 
substr(RomToDec.Remaining,LENGTH(RomToDec.Remaining),1)  AS ThisOne, 
nvl(CharValues.Value,0) ThisDec,
substr(RomToDec.Remaining,1,LENGTH(RomToDec.Remaining)-1) AS Remaining,
LENGTH(RomToDec.Remaining)-1 AS Pos
FROM RomToDec LEFT OUTER JOIN CharValues ON ( substr(RomToDec.Remaining,LENGTH(RomToDec.Remaining),1) = CharValues.Numeral )                      
WHERE RomToDec.Pos > 0 
)
SELECT Val, ThisOne, ThisDec, Remaining, Pos FROM RomToDec
;

Now finally we can add or subtract ThisDec from the running total using the rule:

    For each character starting from the left,

  • If character’s value is >= previous character’s value, add it to the running total
  • If character’s value is < previous character's value, subtract it from the running total

To implement this, I added another column to the recursive member, LastDec, which just holds the previous value of the ThisDec column. I also could have used the LAST analytic function here, but since we’re using recursive subquery it’s trivially easy to just populate the LastDec column with RomToDec.ThisDec .

WITH Roman (Numeral) AS
(SELECT 'MCMLXXXVII' AS Numeral FROM dual),
RomToDec (ThisVal, ThisOne, ThisDec, LastDec, Remaining, Pos) AS
(SELECT 0 AS ThisVal, CAST(NULL AS varchar2(4000)) AS ThisOne, 
0 AS ThisDec, 0 AS LastDec,
Roman.Numeral AS Remaining , LENGTH(Roman.Numeral) AS Pos 
FROM Roman
UNION ALL
SELECT 
CASE 
  WHEN RomToDec.ThisDec >= RomToDec.LastDec THEN RomToDec.ThisVal + ThisDec 
  ELSE RomToDec.ThisVal-ThisDec
END AS ThisVal, 
substr(RomToDec.Remaining,LENGTH(RomToDec.Remaining),1)  AS ThisOne, 
CASE substr(RomToDec.Remaining,LENGTH(RomToDec.Remaining),1)  
  WHEN 'M' THEN 1000
  WHEN 'D' THEN 500
  WHEN 'C' THEN 100
  WHEN 'L' THEN 50
  WHEN 'X' THEN 10
  WHEN 'V' THEN 5
  WHEN 'I' THEN 1
ELSE 0 END AS ThisDec,
RomToDec.ThisDec AS LastDec,
substr(RomToDec.Remaining,1,LENGTH(RomToDec.Remaining)-1) AS Remaining,
LENGTH(RomToDec.Remaining)-1 AS Pos
FROM RomToDec                           
WHERE Pos >= 0
)
SELECT * FROM RomToDec ;

And the final result:

WITH Roman (Numeral) AS
(SELECT 'MCMLXXXVII' AS Numeral FROM dual),
RomToDec (ThisVal, ThisOne, ThisDec, LastDec, Remaining, Pos) AS
(SELECT 0 AS ThisVal, CAST(NULL AS varchar2(4000)) AS ThisOne, 
0 AS ThisDec, 0 AS LastDec,
Roman.Numeral AS Remaining , LENGTH(Roman.Numeral) AS Pos 
FROM Roman
UNION ALL
SELECT 
CASE 
  WHEN RomToDec.ThisDec >= RomToDec.LastDec THEN RomToDec.ThisVal + ThisDec 
  ELSE RomToDec.ThisVal-ThisDec
END AS ThisVal, 
substr(RomToDec.Remaining,LENGTH(RomToDec.Remaining),1)  AS ThisOne, 
CASE substr(RomToDec.Remaining,LENGTH(RomToDec.Remaining),1)  
  WHEN 'M' THEN 1000
  WHEN 'D' THEN 500
  WHEN 'C' THEN 100
  WHEN 'L' THEN 50
  WHEN 'X' THEN 10
  WHEN 'V' THEN 5
  WHEN 'I' THEN 1
ELSE 0 END AS ThisDec,
RomToDec.ThisDec AS LastDec,
substr(RomToDec.Remaining,1,LENGTH(RomToDec.Remaining)-1) AS Remaining,
LENGTH(RomToDec.Remaining)-1 AS Pos
FROM RomToDec                           
WHERE Pos >= 0
)
SELECT thisVal
FROM RomToDec 
WHERE pos IS NULL
;
THISVAL
1987

By the way, you can run these queries right in LiveSQL rather than starting up a test DB.

LiveSQL

Here’s a direct link to the final query in LiveSQL, ready to run!

Note that this SQL doesn’t validate the Roman numeral. For example, IXVIII is an invalid Roman numeral, but this SQL statement will return 17 instead of giving an error.

Today’s image is a photograph by Staci Bigelow

3 comments

Leave a Reply

Your email address will not be published. Required fields are marked *