#155EasyStrings· Parsing with Lookahead

Roman Numeral Reader

A museum stamps the year of every exhibit using roman numerals, and the new catalogue software has to turn each stamp into an ordinary integer. The symbols are `I = 1`, `V = 5`, `X = 10`, `L = 50`, `C = 100`, `D = 500` and `M = 1000`. Symbols are normally written from largest to smallest and their values add up (`VIII = 8`). When a smaller symbol stands **immediately before** a larger one it is subtracted instead: `IV = 4`, `IX = 9`, `XL = 40`, `XC = 90`, `CD = 400`, `CM = 900`. Given a valid roman numeral, return its value.

Input format

`s`: a valid roman numeral made of the characters I, V, X, L, C, D and M.

Output format

An integer between 1 and 3999.

Examples

Input: s = "III"

Output: 3

Three ones add up to 3.

Input: s = "LVIII"

Output: 58

L = 50, V = 5 and III = 3, so 50 + 5 + 3 = 58.

Input: s = "MCMXCIV"

Output: 1994

M = 1000, CM = 900, XC = 90, IV = 4, which adds up to 1994.

Constraints

1 <= s.length <= 15
s is a valid roman numeral in the range [1, 3999].

Study first

Hash Tables

#strings
#hash-table
#math
#parsing