How do you match only valid roman numerals with a regular expression?

198

Thinking about my other problem, i decided I can't even create a regular expression that will match roman numerals (let alone a context-free grammar that will generate them)

The problem is matching only valid roman numerals. Eg, 990 is NOT "XM", it's "CMXC"

My problem in making the regex for this is that in order to allow or not allow certain characters, I need to look back. Let's take thousands and hundreds, for example.

I can allow M{0,2}C?M (to allow for 900, 1000, 1900, 2000, 2900 and 3000). However, If the match is on CM, I can't allow following characters to be C or D (because I'm already at 900).

How can I express this in a regex?
If it's simply not expressible in a regex, is it expressible in a context-free grammar?

regex roman-numerals

Edit Report

Fortunately, the range of numbers is limited to 1..3999 or thereabouts. Therefore, you can build up the regex piece-meal.

<opt-thousands-part><opt-hundreds-part><opt-tens-part><opt-units-part>

Each of those parts will deal with the vagaries of Roman notation. For example, using Perl notation:

<opt-hundreds-part> = m/(CM|DC{0,3}|CD|C{1,3})?/;

Repeat and assemble.

Added: The <opt-hundreds-part> can be compressed further:

<opt-hundreds-part> = m/(C[MD]|D?C{0,3})/;

Since the 'D?C{0,3}' clause can match nothing, there's no need for the question mark. And, most likely, the parentheses should be the non-capturing type - in Perl:

<opt-hundreds-part> = m/(?:C[MD]|D?C{0,3})/;

Of course, it should all be case-insensitive, too.

You can also extend this to deal with the options mentioned by James Curran (to allow XM or IM for 990 or 999, and CCCC for 400, etc).

<opt-hundreds-part> = m/(?:[IXC][MD]|D?C{0,4})/;

answered 2008-11-06T01:36:18.950

How do you match only valid roman numerals with a regular expression?

1 Answer

Your Answer