Учебный пример: Римские цифры

Скорее всего вы видели римские цифры, даже если вы в них не разбираетесь. Вы могли видеть их на копирайтах старых фильмов и ТВ-шоу («Copyright MCMXLVI» вместо «Copyright 1946»), или на стенах в библиотеках университетов («учреждено MDCCCLXXXVIII» вместо «учреждено 1888»). Вы могли видеть их в структуре библиографических ссылок. Эта система отображения цифр относится к древней Римской империи (отсюда и название).

В римских цифрах семь символов, которые повторяются в различных комбинациях для отображения цифр.

• I = 1
• V = 5
• X = 10
• L = 50
• C = 100
• D = 500
• M = 1000

Нижеследующие правила позволяют конструировать римские цифры:

• Иногда символы складываются. I это 1, II это 2, и III это 3. VI это 6 (посимвольно, «5 и 1»), VII это 7, и VIII это 8.
• Десятичные символы (I, X, C, и M) могут быть повторены до 3 раз. Для образования 4 вам необходимо отнять от следующего высшего символа пятёрки. Нельзя писать 4 как IIII; вместо этого, она записывается как IV («на 1 меньше 5»). 40 записывается как XL («на 10 меньше 50»), 41 как XLI, 42 как XLII, 43 как XLIII, и 44 как XLIV («на 10 меньше 50, и на 1 меньше 5»).
• Иногда символы… обратны сложению. Разместив определённые символы до других, вы вычитаете их от конечного значения. Например 9, вам необходимо отнять от следующего высшего символа десять: 8 это VIII, но 9 это IX («на 1 меньше 10»), не VIIII (так как символ I не может быть повторён 4 раза). 90 это XC, 900 это CM.
• Пятёрки не могут повторяться. 10 всегда отображается как X, никогда как VV. 100 всегда C, никогда LL.
• Римские цифры читаются слева направо, поэтому положение символа имеет большое значение. DC это 600; CD это совершенно другая цифра (400, «на 100 меньше 500»). CI это 101; IC это даже не является допустимым Римским числом (так как вы не можете вычитать 1 прямо из 100; вам необходимо записать это как XCIX, «на 10 меньше 100, и на 1 меньше 10»).

 

Проверка на тысячи

Что необходимо сделать чтобы проверить что произвольная строка является допустимым римским числом? Давайте будем брать по одному символу за один раз. Так как римские числа всегда записываются от высшего к низшему, начнём с высшего: с тысячной позиции. Для чисел от 1000 и выше, используются символы M.

>>> import re
>>> pattern = '^M?M?M?$' ①
>>> re.search(pattern, 'M') ②
UNIQae610d7ca506639d-nowiki-00000039-QINU
>>> re.search(pattern, 'MM') ③
<_sre.SRE_Match object at 0106C290>
>>> re.search(pattern, 'MMM') ④
<_sre.SRE_Match object at 0106AA38>
>>> re.search(pattern, 'MMMM') ⑤
>>> re.search(pattern, '') ⑥
<_sre.SRE_Match object at 0106F4A8>

• ① Этот патерн состоит из трёх частей. ^ совпадает с началом строки. Если его не указать, патерн будет совпадать с М без учёта положения в строке, а это не то что нам надо. Вы должны быть уверены что символы М если присутствуют, то находятся в начале строки. M? Опционально совпадает с одним символом M. Так это повторяется три раза то патерн совпадёт от нуля до трёх раз с символом М в строке. И символ $ совпадёт с концом строки. Когда комбинируется с символом ^ в начале, это означает что патерн должен совпасть с полной строкой, без других символов до и после символов М.

• ② Сущность модуля re это функция search(), которая использует патерн регулярного выражения (pattern) и строку ('M') и ищет совпадения в соответствии регулярному выражению. Если совпадение обнаружено, search() возвращает объект который имеет различные методы описания совпадения; если совпадения не обнаружено, search() возвращает None, в Python значение нуля (null). Всё о чём мы заботимся в данный момент, совпадёт ли патерн, это можно сказать глянув на значение возвращаемое функцией search(). 'M' совпадает с этим регулярным выражением, так как первое опциональное M совпадает, а второе опциональное М и третье игнорируется.

• ③ 'MM' совпадает так как первое и второе опциональное М совпадает а третье игнорируется

• ④ 'MMM' совпадает полностью, так как все три символа М совпадают

• ⑤ 'MMMM' не совпадает. Все три М совпадают, но регулярное выражение настаивает на конце строки, (так как требует символ $), а строка ещё не кончилась (из за четвёртого М). Поэтому search() возвращает None.

• ⑥ Занимательно то, что пустая строка также совпадает с регулярным выражением, так как все символы М опциональны.

Проверка на сотни

? делает патерн необязательным

Расположение сотен более сложное чем тысяч, так как существует несколько взаимно исключающих путей записи и зависит от значения.

• 100 = C
• 200 = CC
• 300 = CCC
• 400 = CD
• 500 = D
• 600 = DC
• 700 = DCC
• 800 = DCCC
• 900 = CM

Таким образом есть четыре возможных патерна:

• CM
• CD
• От ноль до трёх символов C (ноль если месть сотен пусто)
• D, от последующх нулей до трёх символов C

Два последних патерна комбинированные:

• опциональное D, за ним от нуля до трёх символов C

Этот пример показывает как проверить позицию сотни в римском числе.

>>> import re
>>> pattern = '^M?M?M?(CM|CD|D?C?C?C?)$' ①
>>> re.search(pattern, 'MCM') ②
UNIQae610d7ca506639d-nowiki-00000040-QINU
>>> re.search(pattern, 'MD') ③
UNIQae610d7ca506639d-nowiki-00000041-QINU
>>> re.search(pattern, 'MMMCCC') ④
UNIQae610d7ca506639d-nowiki-00000042-QINU
>>> re.search(pattern, 'MCMC') ⑤
>>> re.search(pattern, '') ⑥
UNIQae610d7ca506639d-nowiki-00000043-QINU

• ① Этот патерн стартует также как и предыдущий, проверяя сначала строки (^), потом тысячи (M?M?M?). Следом идёт новая часть в скобках, которая описывает три взаимоисключающих патерна разделённых вертикальной линией: CM, CD и D?C?C?C? (который является опциональным D и следующими за ним от нулей до трёх опциональных символов C). Парсер регулярного выражения проверяет каждый из этих патерновв последовательности от левого к правому, выбирая первый подходящий и игнорируя последующие.

• ② 'MCM' совпадает так как первый M совпадает, второй и третий символ M игнорируется, символы CM совпадают (и CD и D?C?C?C? патерны после этого не анализируются). MCM это римское представление числа 1900.

• ③ 'MD' совпадает так как первый M совпадает, второй и третий символ M игнорируется, и патерн D?C?C?C? Совпадает с D (три символа C опциональны и игнорируются). MD это римское представление числа 1500.

• ④ 'MMMCCC' совпадает так как первый M совпадает, и патерн D?C?C?C? сопадает с CCC (символ D опциональный и игнорируются). MMMCCC i это римское представление числа 3300.

• ⑤ 'MCMC' не совпадает. Первый символ M совпадает, второй и третий символ M игнорируется, также совпадает CM, но патерн $ не совпадает так как вы ещё не в конце строки (вы ещё имеете не совпадающий символ C). Символ C не совпадает как часть патерна D?C?C?C?, так как исключающий патерн CM уже совпал.

• ⑥ Занимательно то, что пустая строка всё ещё совпадает с регулярным выражением, так как все символы М опциональны и игнорируются и пустая строка совпадает с патерном D?C?C?C? где все символы опциональны и игнорируются.

Опаньки! Вы заметили как быстро регулярные выражения становятся отвратительными? И пока что мы обработали только позиции тысяч и сотен в римском представлении чисел. Но если последуете далее, вы обнаружите что десятки и единицы описать будет легче, так как они имеют такой же патерн. Тем временем давайте рассмотрим другой путь описать этот патерн.

⁂

Использование синтаксиса {n, m}

модификатор {1,4} совпадает с 1 до 4 вхождением патерна

В предыдущей секции мы имели дело с патерном где одинаковый символ может повториться до трёх раз. Существует другой путь записать это регулярное выражение, которое многие люди найдут более читаемым. Для начала взглянем на метод который мы уже использовали в предыдущем примере.

>>> import re
>>> pattern = '^M?M?M?$'
>>> re.search(pattern, 'M') ①
UNIQae610d7ca506639d-nowiki-00000045-QINU
>>> pattern = '^M?M?M?$'
>>> re.search(pattern, 'MM') ②
UNIQae610d7ca506639d-nowiki-00000046-QINU
>>> pattern = '^M?M?M?$'
>>> re.search(pattern, 'MMM') ③
UNIQae610d7ca506639d-nowiki-00000047-QINU
>>> re.search(pattern, 'MMMM') ④
>>>

• ① Тут патерн совпадает с началом строки и первым опциональным М, но не со вторым и третьим (но это нормально так как они опциональны), а также с концом строки.

• ② Тут патерн совпадает с началом строки, с первым и вторым опциональным символом М, но не с третьим (это нормально так как он опционален) и с концом строки.

• ③ Тут патерн совпадает с началом строки и со всеми тремя опциональными символами М и также с концом строки.

• ④ Тут патерн совпадает с началом строки и со всеми тремя опциональными символами М, но не совпадает с концом строки (так как присутствует ещё одно М), таким образом патерн не совпадает и возвращает None.

>>> pattern = '^M{0,3}$' ①
>>> re.search(pattern, 'M') ②
UNIQae610d7ca506639d-nowiki-00000049-QINU
>>> re.search(pattern, 'MM') ③
<_sre.SRE_Match object at 0x008EE090>
>>> re.search(pattern, 'MMM') ④
<_sre.SRE_Match object at 0x008EEDA8>
>>> re.search(pattern, 'MMMM') ⑤
>>>

• ① Этот патерн говорит: «Совпасть с началом строки, потом с от нуля до трёх символов М находящимися где угодно, потом с концом строки». Символы 0 и 3 могут быть любыми цифрами, если вам необходимо совпадение с 1 и более символами М, необходимо записать М{1,3}.

• ② Тут патерн совпадает с началом строки, потом с одним из возможных трёх символов М, потом с концом строки.

• ③ Тут патерн совпадает с началом строки, потом с двумя из возможных трёх символов М, потом с концом строки.

• ④ Тут патерн совпадает с началом строки, потом с тремя из возможных трёх символов М, потом с концом строки.

• ⑤ Тут патерн совпадает с началом строки, потом с двумя из возможных трёх символов М, но не совпадает с концом строки.

Регулярное выражение позволяет до трёх символов М до конца строки, но у вас четыре, и патерн возвращает None.