Jak dopasować tylko prawidłowe cyfry rzymskie do wyrażenia regularnego?

165

Myśląc o moim innym problemie , zdecydowałem, że nie mogę nawet utworzyć wyrażenia regularnego, które będzie pasowało do cyfr rzymskich (nie mówiąc już o gramatyce bezkontekstowej, która je wygeneruje)

Problem polega na dopasowaniu tylko prawidłowych cyfr rzymskich. Np. 990 to NIE „XM”, tylko „CMXC”

Mój problem z tworzeniem wyrażenia regularnego do tego polega na tym, że aby zezwolić lub nie na określone znaki, muszę spojrzeć wstecz. Weźmy na przykład tysiące i setki.

Mogę zezwolić na M {0,2} C? M (aby zezwolić na 900, 1000, 1900, 2000, 2900 i 3000). Jednak jeśli dopasowanie jest na CM, nie mogę pozwolić, aby następujące znaki były C lub D (ponieważ mam już 900).

Jak mogę to wyrazić w wyrażeniu regularnym?
Jeśli po prostu nie da się tego wyrazić w wyrażeniu regularnym, czy można to wyrazić w gramatyce bezkontekstowej?

Daniel Magliola
źródło

Odpowiedzi:

328

Możesz użyć do tego następującego wyrażenia regularnego:

^M{0,4}(CM|CD|D?C{0,3})(XC|XL|L?X{0,3})(IX|IV|V?I{0,3})$

Rozbijając go, M{0,4}określa sekcję tysięcy i zasadniczo ogranicza go do między 0a 4000. To stosunkowo proste:

   0: <empty>  matched by M{0}
1000: M        matched by M{1}
2000: MM       matched by M{2}
3000: MMM      matched by M{3}
4000: MMMM     matched by M{4}

Możesz oczywiście użyć czegoś w rodzaju, M*aby zezwolić na dowolną liczbę (w tym zero) tysięcy, jeśli chcesz zezwolić na większe liczby.

Dalej (CM|CD|D?C{0,3}), nieco bardziej skomplikowane, dotyczy sekcji setki i obejmuje wszystkie możliwości:

  0: <empty>  matched by D?C{0} (with D not there)
100: C        matched by D?C{1} (with D not there)
200: CC       matched by D?C{2} (with D not there)
300: CCC      matched by D?C{3} (with D not there)
400: CD       matched by CD
500: D        matched by D?C{0} (with D there)
600: DC       matched by D?C{1} (with D there)
700: DCC      matched by D?C{2} (with D there)
800: DCCC     matched by D?C{3} (with D there)
900: CM       matched by CM

Po trzecie, obowiązuje (XC|XL|L?X{0,3})te same zasady, co poprzednia sekcja, ale dla miejsca dziesiątek:

 0: <empty>  matched by L?X{0} (with L not there)
10: X        matched by L?X{1} (with L not there)
20: XX       matched by L?X{2} (with L not there)
30: XXX      matched by L?X{3} (with L not there)
40: XL       matched by XL
50: L        matched by L?X{0} (with L there)
60: LX       matched by L?X{1} (with L there)
70: LXX      matched by L?X{2} (with L there)
80: LXXX     matched by L?X{3} (with L there)
90: XC       matched by XC

I wreszcie, (IX|IV|V?I{0,3})jest sekcja jednostki, obsługa 0przez 9i podobne do dwóch poprzednich odcinków (cyfry rzymskie, pomimo ich pozornej tajemniczości, przestrzegać pewnych reguł logicznych Po dowiedzieć się, jakie są):

0: <empty>  matched by V?I{0} (with V not there)
1: I        matched by V?I{1} (with V not there)
2: II       matched by V?I{2} (with V not there)
3: III      matched by V?I{3} (with V not there)
4: IV       matched by IV
5: V        matched by V?I{0} (with V there)
6: VI       matched by V?I{1} (with V there)
7: VII      matched by V?I{2} (with V there)
8: VIII     matched by V?I{3} (with V there)
9: IX       matched by IX

Pamiętaj tylko, że to wyrażenie regularne będzie również pasowało do pustego ciągu. Jeśli tego nie chcesz (a Twój silnik wyrażeń regularnych jest wystarczająco nowoczesny), możesz zastosować pozytywne spojrzenie w tył i w przyszłość:

(?<=^)M{0,4}(CM|CD|D?C{0,3})(XC|XL|L?X{0,3})(IX|IV|V?I{0,3})(?=$)

(inną alternatywą jest po prostu sprawdzenie, czy długość nie wynosi wcześniej zero).

paxdiablo
źródło
12
Czy nie powinno to być M {0,3}?
cytryna
3
jakieś rozwiązanie, aby uniknąć dopasowania pustego ciągu?
Facundo Casco
11
@Aashish: Kiedy Rzymianie byli siłą, z którą trzeba było się liczyć, MMMMbyła właściwa droga. Reprezentacja overbar pojawiła się długo po rozpadzie imperium.
paxdiablo
2
@paxdiablo w ten sposób znalazłem błąd mmmcm. Ciąg regx = "^ M {0,3} (CM | CD | D? C {0,3}) (XC | XL | L? X {0,3}) (IX | IV | V? I {0, 3}) $ "; if (input.matches (regx)) -> to ewaluuje do false dla MMMCM / MMMM w java.
amIT
2
/^M{0,3}(?:C[MD]|D?C{0,3})(?:X[CL]|L?X{0,3})(?:I[XV]|V?I{0,3})$/i
Crissov
23

Właściwie twoje założenie jest błędne. 990 IS „XM”, a także „CMXC”.

Rzymianie byli o wiele mniej zaniepokojeni „zasadami” niż nauczyciel z trzeciej klasy. Dopóki to się zgadzało, było OK. Stąd „IIII” było tak samo dobre jak „IV” za 4. A „IIM” było zupełnie fajne dla 998.

(Jeśli masz z tym problem ... Pamiętaj, że pisownia angielska została sformalizowana dopiero w XVIII wieku. Do tego czasu, o ile czytelnik mógł to zrozumieć, była wystarczająco dobra).

James Curran
źródło
8
Jasne, to fajne. Ale moja potrzeba składniowa "ścisłego nauczyciela trzeciej klasy" sprawia, że ​​moim zdaniem o wiele bardziej interesujący problem z wyrażeniami regularnymi ...
Daniel Magliola
5
Słuszna uwaga James, trzeba być surowym autorem, ale wyrozumiałym czytelnikiem.
Corin
@Corin: aka zasada odporności Postela
jfs
13

Wystarczy zapisać go tutaj:

(^(?=[MDCLXVI])M*(C[MD]|D?C{0,3})(X[CL]|L?X{0,3})(I[XV]|V?I{0,3})$)

Pasuje do wszystkich cyfr rzymskich. Nie przejmuje się pustymi ciągami (wymaga co najmniej jednej litery rzymskiej). Powinien działać w PCRE, Perl, Python i Ruby.

Demo online Rubiego: http://rubular.com/r/KLPR1zq3Hj

Konwersja online: http://www.onlineconversion.com/roman_numerals_advanced.htm

smileart
źródło
2
Nie wiem dlaczego, ale główna odpowiedź nie zadziałała w przypadku list autotranslacyjnych w MemoQ. Jednak to rozwiązanie działa - z wyłączeniem symboli początku / końca łańcucha.
orlando2bjr
1
@ orlando2bjr chętnie pomogę. Tak, w tym przypadku dopasowywałem liczbę samodzielnie, bez otoczenia. Jeśli szukasz tego w tekście, na pewno musisz usunąć ^ $. Twoje zdrowie!
smileart
12

Aby uniknąć dopasowania pusty łańcuch trzeba powtórzyć wzór o cztery razy i zastąpić każdy 0z 1kolei, a na konto V, Li D:

(M{1,4}(CM|CD|D?C{0,3})(XC|XL|L?X{0,3})(IX|IV|V?I{0,3})|M{0,4}(CM|C?D|D?C{1,3})(XC|XL|L?X{0,3})(IX|IV|V?I{0,3})|M{0,4}(CM|CD|D?C{0,3})(XC|X?L|L?X{1,3})(IX|IV|V?I{0,3})|M{0,4}(CM|CD|D?C{0,3})(XC|XL|L?X{0,3})(IX|I?V|V?I{1,3}))

W tym przypadku (ponieważ ten wzorzec używa ^i $) lepiej byłoby najpierw sprawdzić puste wiersze i nie zawracać sobie głowy dopasowywaniem ich. Jeśli używasz granic słów , nie masz problemu, ponieważ nie ma czegoś takiego jak puste słowo. (Przynajmniej regex nie definiuje żadnego; nie zaczynaj filozofowania, jestem tutaj pragmatyczny!)


W moim konkretnym przypadku (w prawdziwym świecie) potrzebowałem dopasowywania cyfr na końcówkach słów i nie znalazłem innego sposobu na obejście tego. Musiałem peeling off numery przypisów z mojego zwykłego dokumentu tekstowego, gdzie tekst takich jak „Red Sea cl i Wielkiej Rafy Koralowej CLI ” zostało przekształcone w the Red Seacl and the Great Barrier Reefcli. Ale nadal miałem problemy z ważnymi słowami, takimi jak Tahitii fantasticsą przenoszone do Tahiti fantasti.

Corin
źródło
Mam podobny problem (!): Zrobić "lewe przycięcie" pozostałej / pozostałej liczby rzymskiej listy pozycji (HTML OL typu I lub i). Tak więc, kiedy tam pozostają, muszę czysty (jak trymowania funkcji) z regex na początku (po lewej) elementu tekstu ... Ale bardziej prosta: nigdy nie używać przedmiotów Mlub Cczy L, tak, masz to rodzaj uproszczonego wyrażenia regularnego?
Peter Krauss
... ok, tutaj wydaje się ok (!),(X{1,3}(IX|IV|V?I{0,3})|X{0,3}(IX|I?V|V?I{1,3}))
Peter Krauss
1
nie musisz powtarzać wzoru, aby odrzucić puste ciągi. Możesz użyć asercji
lookahead
7

Na szczęście zakres numerów jest ograniczony do 1–3999 lub mniej więcej. W związku z tym możesz zbudować regex kawałek-posiłek.

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

Każda z tych części będzie dotyczyła kaprysów notacji rzymskiej. Na przykład używając notacji Perl:

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

Powtórz i złóż.

Dodano : <opt-hundreds-part>Można dalej skompresować:

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

Ponieważ klauzula „D? C {0,3}” nie może niczego dopasować, nie ma potrzeby wstawiania znaku zapytania. Najprawdopodobniej nawiasy powinny być typu nieprzechwytywania - w Perlu:

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

Oczywiście we wszystkich również powinna być rozróżniana wielkość liter.

Możesz również rozszerzyć to, aby poradzić sobie z opcjami wymienionymi przez Jamesa Currana (aby zezwolić na XM lub IM dla 990 lub 999 i CCCC dla 400 itd.).

<opt-hundreds-part> = m/(?:[IXC][MD]|D?C{0,4})/;
Jonathan Leffler
źródło
Zaczynając od thousands hundreds tens units, łatwo jest stworzyć FSM, który oblicza i weryfikuje podane cyfry rzymskie
jfs
Co masz na myśli , mówiąc na szczęście, że zakres liczb jest ograniczony do 1–3999 lub mniej więcej ? Kto to ograniczył?
SexyBeast,
@SexyBeast: Nie ma żadnej standardowej notacji rzymskiej dla 5000, nie mówiąc już o większych liczbach, więc regularności, które działały do ​​tego czasu, przestają działać.
Jonathan Leffler
Nie wiem, dlaczego w to wierzysz, ale cyfry rzymskie mogą oznaczać miliony. en.wikipedia.org/wiki/Roman_numerals#Large_numbers
AmbroseChapel
@AmbroseChapel: Jak już wspomniałem, nie ma żadnej (pojedynczej) standardowej notacji dla 5000, nie mówiąc już o większych liczbach. Musisz użyć jednego z wielu rozbieżnych systemów, jak opisano w artykule w Wikipedii, do którego masz link, i napotykasz problemy z ortografią systemu z nadprożami, podprosami lub odwróconym C itd. I będziesz musiał każdemu wyjaśnić, co system, którego używasz i co to oznacza; ludzie na ogół nie rozpoznają cyfr rzymskich poza M. Możesz zdecydować inaczej; to jest wasz przywilej, tak jak moim przywilejem jest podtrzymywanie moich poprzednich komentarzy.
Jonathan Leffler,
7
import re
pattern = '^M{0,3}(CM|CD|D?C{0,3})(XC|XL|L?X{0,3})(IX|IV|V?I{0,3})$'
if re.search(pattern, 'XCCMCI'):
    print 'Valid Roman'
else:
    print 'Not valid Roman'

Dla osób, które naprawdę chcą zrozumieć logikę, zapoznaj się z wyjaśnieniem krok po kroku na 3 stronach na temat diveintopython .

Jedyna różnica w stosunku do oryginalnego rozwiązania (które miało M{0,4}) polega na tym, że stwierdziłem, że „MMMM” nie jest poprawną cyfrą rzymską (również starzy Rzymianie prawdopodobnie nie myśleli o tej ogromnej liczbie i nie zgodzą się ze mną). Jeśli nie zgadzasz się ze starymi Rzymianami, wybacz mi i użyj wersji {0,4}.

Salvador Dali
źródło
1
wyrażenie regularne w odpowiedzi dopuszcza puste cyfry. Jeśli tego nie chcesz; możesz użyć asercji z wyprzedzeniem , aby odrzucić puste łańcuchy (ignoruje również wielkość liter).
jfs
2

Odpowiadam na to pytanie Wyrażenie regularne w Pythonie dla liczb rzymskich ,
ponieważ zostało zaznaczone jako dokładny duplikat tego pytania.

Nazwa może być podobna, ale jest to konkretne pytanie / problem wyrażenia regularnego,
jak widać po odpowiedzi na to pytanie.

Poszukiwane elementy można połączyć w jedną zmianę, a następnie
umieścić w grupie przechwytywania, która zostanie umieszczona na liście za pomocą funkcji findall ()
.
Robi się to tak:

>>> import re
>>> target = (
... r"this should pass v" + "\n"
... r"this is a test iii" + "\n"
... )
>>>
>>> re.findall( r"(?m)\s(i{1,3}v*|v)$", target )
['v', 'iii']

Modyfikacje wyrażenia regularnego w celu uwzględnienia i przechwycenia samych liczb są następujące:

 (?m)
 \s 
 (                     # (1 start)
      i{1,3} 
      v* 
   |  v
 )                     # (1 end)
 $
x15
źródło
1

Jak Jeremy i Pax wskazali powyżej ... '^ M {0,4} (CM | CD | D? C {0,3}) (XC | XL | L? X {0,3}) (IX | IV | V? I {0,3}) $ 'powinno być rozwiązaniem, którego szukasz ...

Konkretny adres URL, który powinien zostać dołączony (IMHO), to http://thehazeltree.org/diveintopython/7.html

Przykład 7.8 to krótka forma wykorzystująca {n, m}

Jonathan Leffler
źródło
1

W moim przypadku próbowałem znaleźć i zamienić wszystkie wystąpienia liczb rzymskich jednym słowem w tekście, więc nie mogłem użyć początku i końca linii. Zatem rozwiązanie @paxdiablo znalazło wiele dopasowań o zerowej długości. Skończyło się na następującym wyrażeniu:

(?=\b[MCDXLVI]{1,6}\b)M{0,4}(?:CM|CD|D?C{0,3})(?:XC|XL|L?X{0,3})(?:IX|IV|V?I{0,3})

Mój ostateczny kod w Pythonie wyglądał następująco:

import re
text = "RULES OF LIFE: I. STAY CURIOUS; II. NEVER STOP LEARNING"
text = re.sub(r'(?=\b[MCDXLVI]{1,6}\b)M{0,4}(?:CM|CD|D?C{0,3})(?:XC|XL|L?X{0,3})(?:IX|IV|V?I{0,3})', 'ROMAN', text)
print(text)

Wynik:

RULES OF LIFE: ROMAN. STAY CURIOUS; ROMAN. NEVER STOP LEARNING
user2936263
źródło
0

Steven Levithan używa tego wyrażenia regularnego w swoim poście, który weryfikuje cyfry rzymskie przed „deromanizacją” wartości:

/^M*(?:D?C{0,3}|C[MD])(?:L?X{0,3}|X[CL])(?:V?I{0,3}|I[XV])$/
Mottie
źródło
0

Widziałem wiele odpowiedzi, które nie obejmują pustych ciągów ani nie używają lookaheads do rozwiązania tego problemu. Chcę dodać nową odpowiedź, która obejmuje puste łańcuchy i nie używa antycypowania. Wyrażenie regularne jest następujące:

^(I[VX]|VI{0,3}|I{1,3})|((X[LC]|LX{0,3}|X{1,3})(I[VX]|V?I{0,3}))|((C[DM]|DC{0,3}|C{1,3})(X[LC]|L?X{0,3})(I[VX]|V?I{0,3}))|(M+(C[DM]|D?C{0,3})(X[LC]|L?X{0,3})(I[VX]|V?I{0,3}))$

Pozwalam na nieskończoność M, M+ale oczywiście ktoś może się zmienićM{1,4} aby zezwolić tylko na 1 lub 4 w razie potrzeby.

Poniżej znajduje się wizualizacja, która pomaga zrozumieć, co robi, poprzedzona dwoma demonstracjami online:

Debuggex Demo

Regex 101 Demo

Wizualizacja wyrażeń regularnych

Bernardo Duarte
źródło
0

Działa to w silnikach regex Java i PCRE i powinno teraz działać w najnowszym JavaScript, ale może nie działać we wszystkich kontekstach.

(?<![A-Z])(M*(CM|CD|D?C{0,3})(XC|XL|L?X{0,3})(IX|IV|V?I{0,3}))(?![A-Z])

Pierwsza część to potworne negatywne spojrzenie za siebie. Ale ze względów logicznych jest to najłatwiejsze do zrozumienia. Zasadniczo pierwsze (?<!)mówi, że nie dopasowuj środka, ([MATCH])jeśli przed środkiem są litery, ([MATCH])a ostatnie (?!)mówi, że nie dopasowuj środka, ([MATCH])jeśli są po nim litery.

Środek ([MATCH])jest po prostu najczęściej używanym wyrażeniem regularnym do dopasowywania sekwencji liczb rzymskich. Ale teraz nie chcesz dopasować tego, jeśli wokół niego są jakieś litery.

Sam zobacz. https://regexr.com/4vce5

ketenks
źródło
-1

Problem rozwiązania Jeremy'ego i Paxa polega na tym, że pasuje ono również do „niczego”.

Następujące wyrażenie regularne wymaga co najmniej jednej cyfry rzymskiej:

^(M{0,4}(CM|CD|D?C{0,3})(XC|XL|L?X{0,3})(IX|IV|V?I{0,3})|[IDCXMLV])$
Marvin Frommhold
źródło
6
to nie zadziała (chyba że używasz bardzo dziwnej implementacji regex) - lewa część |może pasować do pustego ciągu i wszystkich prawidłowych cyfr rzymskich, więc prawa strona jest całkowicie zbędna. i tak, nadal pasuje do pustego ciągu.
DirtY ICE
„Problem rozwiązania Jeremy'ego i Paxa jest”… dokładnie taki sam jak problem, który zawiera ta odpowiedź. Jeśli masz zamiar zaproponować rozwiązanie domniemanego problemu, prawdopodobnie powinieneś go przetestować. :-)
paxdiablo
Mam z tym pusty ciąg
Aminah Nuraini
-2

Pisałbym dla mnie funkcje do mojej pracy. Oto dwie funkcje liczb rzymskich w programie PowerShell.

function ConvertFrom-RomanNumeral
{
  <#
    .SYNOPSIS
        Converts a Roman numeral to a number.
    .DESCRIPTION
        Converts a Roman numeral - in the range of I..MMMCMXCIX - to a number.
    .EXAMPLE
        ConvertFrom-RomanNumeral -Numeral MMXIV
    .EXAMPLE
        "MMXIV" | ConvertFrom-RomanNumeral
  #>
    [CmdletBinding()]
    [OutputType([int])]
    Param
    (
        [Parameter(Mandatory=$true,
                   HelpMessage="Enter a roman numeral in the range I..MMMCMXCIX",
                   ValueFromPipeline=$true,
                   Position=0)]
        [ValidatePattern("^M{0,3}(CM|CD|D?C{0,3})(XC|XL|L?X{0,3})(IX|IV|V?I{0,3})$")]
        [string]
        $Numeral
    )

    Begin
    {
        $RomanToDecimal = [ordered]@{
            M  = 1000
            CM =  900
            D  =  500
            CD =  400
            C  =  100
            XC =   90
            L  =   50
            X  =   10
            IX =    9
            V  =    5
            IV =    4
            I  =    1
        }
    }
    Process
    {
        $roman = $Numeral + " "
        $value = 0

        do
        {
            foreach ($key in $RomanToDecimal.Keys)
            {
                if ($key.Length -eq 1)
                {
                    if ($key -match $roman.Substring(0,1))
                    {
                        $value += $RomanToDecimal.$key
                        $roman  = $roman.Substring(1)
                        break
                    }
                }
                else
                {
                    if ($key -match $roman.Substring(0,2))
                    {
                        $value += $RomanToDecimal.$key
                        $roman  = $roman.Substring(2)
                        break
                    }
                }
            }
        }
        until ($roman -eq " ")

        $value
    }
    End
    {
    }
}

function ConvertTo-RomanNumeral
{
  <#
    .SYNOPSIS
        Converts a number to a Roman numeral.
    .DESCRIPTION
        Converts a number - in the range of 1 to 3,999 - to a Roman numeral.
    .EXAMPLE
        ConvertTo-RomanNumeral -Number (Get-Date).Year
    .EXAMPLE
        (Get-Date).Year | ConvertTo-RomanNumeral
  #>
    [CmdletBinding()]
    [OutputType([string])]
    Param
    (
        [Parameter(Mandatory=$true,
                   HelpMessage="Enter an integer in the range 1 to 3,999",
                   ValueFromPipeline=$true,
                   Position=0)]
        [ValidateRange(1,3999)]
        [int]
        $Number
    )

    Begin
    {
        $DecimalToRoman = @{
            Ones      = "","I","II","III","IV","V","VI","VII","VIII","IX";
            Tens      = "","X","XX","XXX","XL","L","LX","LXX","LXXX","XC";
            Hundreds  = "","C","CC","CCC","CD","D","DC","DCC","DCCC","CM";
            Thousands = "","M","MM","MMM"
        }

        $column = @{Thousands = 0; Hundreds = 1; Tens = 2; Ones = 3}
    }
    Process
    {
        [int[]]$digits = $Number.ToString().PadLeft(4,"0").ToCharArray() |
                            ForEach-Object { [Char]::GetNumericValue($_) }

        $RomanNumeral  = ""
        $RomanNumeral += $DecimalToRoman.Thousands[$digits[$column.Thousands]]
        $RomanNumeral += $DecimalToRoman.Hundreds[$digits[$column.Hundreds]]
        $RomanNumeral += $DecimalToRoman.Tens[$digits[$column.Tens]]
        $RomanNumeral += $DecimalToRoman.Ones[$digits[$column.Ones]]

        $RomanNumeral
    }
    End
    {
    }
}
Vince Ypma
źródło