Permutationen mit regulären Ausdrücken finden

Question

Ich muss einen regulären Ausdruck (für ein Programm in Haskell) erstellen, der die Zeichenfolgen mit "X" und "." Abfängt, vorausgesetzt, es gibt 4 "X" und nur ein ".". Es kann keine Zeichenfolge mit anderen X-zu-Punkt-Beziehungen abfangen. Ich habe darüber nachgedacht, so etwas wie

[X\.]{5} 

Aber es fängt auch „XXXXX“ oder „.....“, so ist es nicht das, was ich brauche.

Answer 1

Das heißt Permutation Parsing, und während "pure" reguläre Ausdrücke können Permutationen nicht analysieren, ist es möglich, wenn Ihre Regex-Engine Lookahead unterstützt. (Siehe this answer für ein Beispiel.)

Allerdings finde ich die Regex in der verknüpften Antwort schwierig zu verstehen. Es ist meiner Meinung nach sauberer, eine Bibliothek zu verwenden, die für die Permutationsanalyse entworfen wurde, wie zum Beispiel megaparsec.

Sie verwenden das Text.Megaparsec.Perm Modul durch eine PermParser in einem quasi- Applicative Stil Bau des <||> Operator, dann in eine reguläre MonadParsec Aktion Umwandlung makePermParser verwenden.

Also hier ist ein Parser, die eine beliebige Kombination von vier X s und einer . erkennt:

import Control.Applicative 
import Data.Ord 
import Data.List 
import Text.Megaparsec 
import Text.Megaparsec.Perm 

fourXoneDot :: Parsec Dec String String 
fourXoneDot = makePermParser $ mkFive <$$> x <||> x <||> x <||> x <||> dot 
    where mkFive a b c d e = [a, b, c, d, e] 
      x = char 'X' 
      dot = char '.' 

ich die Anwendung des mkFive-Funktion, die seine Argumente in einem Fünf-Elemente-Liste nur stopft, bis zu vier Instanzen des x Parsers und eines dot, kombiniert mit <||>.

ghci> parse fourXoneDot "" "XXXX." 
Right "XXXX." 
ghci> parse fourXoneDot "" "XX.XX" 
Right "XXXX." 
ghci> parse fourXoneDot "" "XX.X" 
Left {- ... -} 

Dieser Parser gibt immer "XXXX." denn das ist der Auftrag, das ich die Parser in Kombination: Ich bin mkFive über die fünf Parser Mapping und es ist neu anordnen nicht ihre Argumente. Wenn Sie möchten, dass der Permutationsparser seine Eingabe genau zurückgibt, lautet der Trick track the current position innerhalb der Komponentenparser, und sortieren Sie dann die Ausgabe.

fourXoneDotSorted :: Parsec Dec String String 
fourXoneDotSorted = makePermParser $ mkFive <$$> x <||> x <||> x <||> x <||> dot 

    where mkFive a b c d e = map snd $ sortBy (comparing fst) [a, b, c, d, e] 
      x = withPos (char 'X') 
      dot = withPos (char '.') 
      withPos = liftA2 (,) getPosition 

ghci> parse fourXoneDotSorted "" "XX.XX" 
Right "XX.XX" 

Als the megaparsec docs Note, die Umsetzung des Text.Megaparsec.Perm Modul basiert auf Parsing Permutation Phrases; Die Idee ist ausführlich in dem Dokument und the accompanying slides beschrieben.

Answer 2

Versuchen Sie, die folgende regex:
(?<=^|)(?=[^. ]*\.)(?=(?:[^X ]*X){4}).{5}(?=$|)

Demo here

Wenn Sie ein Wort pro String haben, können Sie die regex durch diese vereinfachen kann:
^(?=[^. \n]*\.)(?=(?:[^X \n]*X){4}).{5}$

Demo here

Answer 3

Die anderen Antworten sehen ziemlich kompliziert aus Ich bin der Meinung, dass es nur fünf Saiten in dieser Sprache gibt.Hier ist ein völlig in Ordnung und sehr gut lesbar Regex dafür:

\.XXXX|X\.XXX|XX\.XX|XXX\.X|XXXX\. 

Answer 4

Sind Sie an regex, oder haben Sie nur an regex am Ende, weil dies eine Frage war nicht mit applicative Parsern zu beantworten versuchen wollte?

Hier ist die einfachste mögliche attoparsec Implementierung ich denken kann:

parseDotXs :: Parser() 
parseDotXs = do 
    dotXs <- count 5 (satisfy (inClass ".X")) 
    let (dots,xS) = span (=='.') . sort $ dotXs 
    if (length dots == 1) && (length xS == 4) then do 
    return() 
    else do 
    fail "Mismatch between dots and Xs" 

Sie müssen möglicherweise etwas anpassen auf Ihrem Eingangstyp abhängig.

Es gibt Unmengen an raffinierten Möglichkeiten, Sachen in anwendungsorientiertem Parsing-Land zu tun, aber es gibt keine Regel, die besagt, dass man Dinge nicht einfach so rocken kann.