Right-to-left solution that is a bit more Pythonic (no indexes) and relatively short.
Algorithm:
- Reverse the roman numeral and map it to a list of numbers
- Figure out which numbers should be subtracted and then sum the list
Example:
'xiv' => sum(5, -1, 10) => 14
def parse_roman(s):
numerals = {'M':1000, 'D':500, 'C':100, 'L':50, 'X':10, 'V':5, 'I':1}
n = 0
last_value = 0
# e.g. convert 'xiv' to (5, 1, 10)
for value in (numerals[c] for c in reversed(s.upper())):
# debugging
v = (value, -value)[value < last_value]
print('{:6} += {:5} <== cur, prev = {}, {}'.format(n, v, value, last_value))
# subtract smaller values that come after larger ones, otherwise add
n += (value, -value)[value < last_value]
last_value = value
return n
Output:
parse_roman('MMCMXCVIII')
0 += 1 <== cur, prev = 1, 0
1 += 1 <== cur, prev = 1, 1
2 += 1 <== cur, prev = 1, 1
3 += 5 <== cur, prev = 5, 1
8 += 100 <== cur, prev = 100, 5
108 += -10 <== cur, prev = 10, 100
98 += 1000 <== cur, prev = 1000, 10
1098 += -100 <== cur, prev = 100, 1000
998 += 1000 <== cur, prev = 1000, 100
1998 += 1000 <== cur, prev = 1000, 1000
2998
Note: It would be nice to find a (short, inline) method for changing the signs of the sequence on the fly. For example, (5, 1, 10) ==> (5, -1, 10).
Update: This is as close as I got before giving up. It's identical to the code above, but it uses itertools.tee() with zip() to generate pairs of the previous and current values to eliminate the need for the state variables. The single call to next(cur) makes that list one shorter than prev which is all the state we need to figure out whether to add or subtract the current value.
Example:
cur, prev = (5, 1, 10), (5, 1, 10)
# Take one from cur and zip the rest
next(cur) + sum(... zip(cur, prev))
# 5 + ... zip( (1, 10), (5, 1, 10) ) ==> 5 + ... ((1, 5), (10, 1))
Code:
from itertools import tee
def parse_roman(s):
numerals = {'M':1000, 'D':500, 'C':100, 'L':50, 'X':10, 'V':5, 'I':1}
cur, prev = tee(numerals[c] for c in reversed(s.upper()))
return next(cur) + sum((cur, -cur)[cur < prev] for cur, prev in zip(cur,prev))
