Klebeband ein Regex-Entscheider

11

Ihre Aufgabe besteht darin, ein Programm zu erstellen, das mithilfe von Codefragmenten aus Sites im StackExchange-Netzwerk bestimmt, ob eine bestimmte Zeichenfolge ein gültiger regulärer Ausdruck ist oder nicht.

Für die Zwecke dieser Herausforderung wird der Dialekt für reguläre Ausdrücke eine abgespeckte und meist minimale Menge von Metazeichen sein : ()*?|\. Daher können Sie keine integrierten Regex-Parser verwenden.

  • \wird verwendet, um Metazeichen zu entkommen. Es muss ein Meta-Zeichen folgen.
  • Nicht entflohene Klammern müssen ausgeglichen sein
  • *und ?muss entweder ein Nicht-Meta-Zeichen, eine Gruppe in Klammern oder ein maskiertes Meta-Zeichen vorangestellt werden.
  • Alle anderen druckbaren ASCII-Zeichen sowie Zeilenumbruch, Tabulator und Leerzeichen müssen als Nicht-Meta-Zeichen unterstützt werden. Was mit einer Zeichenfolge passiert, die andere Zeichen enthält, ist undefiniert.
  • Die tatsächliche Bedeutung des regulären Ausdrucks ist für diese Herausforderung nicht wichtig.

Beispiele

Truthy:
  abc
  a?
  (a|)*
  ()
  a|b*
  \*
  \\
  \\*
  a*b?(cd|e)
  +
  [
  }
  (123\))*
  \|
  (a(b(c|d)*e)*f)*
  (|\)*)
  (abc)+*
  (abc)+
  +abc

^ last test case is an actual newline

Falsy:
  ?abc
  *
  **
  \
  (
  a*?
  a?*
  ?
  a)
  (\)
  (|\)*
  \()
  |*
  (?:abc)
  \\**
  \n

Wertung

Ihre Gesamtpunktzahl ist die Anzahl der Ausschnitte aus Fragen und Antworten rund um StackExchange.

  • Wiederholte Schnipsel zählen so oft, wie sie verwendet werden.
  • Whitespace kann frei hinzugefügt und entfernt werden (aufgrund von Python, Haskell und anderen Whitespace-sensiblen Sprachen) und zählt nicht für Ihre Snippet-Anzahl.
  • Snippets sind von jeder StackExchange-Site zulässig, sofern sie aus Fragen, Antworten und Kommentaren stammen, die älter sind (einschließlich der Bearbeitungszeit - verwenden Sie ggf. ältere Revisionen, falls erforderlich) als diese Herausforderung. (24. September 2019 um 15:30 Uhr UTC)
  • Snippets können von überall in einer Frage, Antwort oder einem Kommentarkörper stammen, unabhängig davon, ob sie sich in einem vorformatierten Codeblock befinden oder nicht.
  • Wenn Sie ein Snippet in die Mitte eines anderen spleißen, zählt das äußere Snippet als zwei Snippets

Die niedrigste Punktzahl gewinnt!

Beefster
quelle
1
@RobinRyder ja, geändert
Beefster
Kann der Beitrag älter oder gleich dieser Herausforderung sein, dh können wir Ausschnitte aus dem Körper dieser Herausforderung verwenden?
Jo King
1
"Als solches werden Sie keine eingebauten Regex-Parser verwenden können." Soll das heißen, dass es so konzipiert ist, dass es für ein einfaches Ja / Nein nicht verwendet wird, oder dass es uns in unseren Antworten verboten ist, Regex überhaupt zu verwenden?
user0721090601
@guifa ist so konzipiert, dass Sie nicht einfach die Regex-Engine Ihrer Sprache verwenden können, um zu sehen, ob sie den angegebenen Regex kompiliert. Jede mir bekannte Sprache unterstützt einen größeren Satz von Metazeichen und spezialisierten Erfassungsgruppen, sodass sie nicht in allen Fällen korrekt mit diesem Zeichensatz übereinstimmen.
Beefster
1
@ JL2210 Das würde es zwei Schnipsel machen: einen für den Anfang und einen für das Ende. Sie können ein einzelnes Snippet verwenden, solange es alle Testfälle besteht und aus einer Antwort / Frage / einem Beitrag stammt, die älter als diese Herausforderung ist
Beefster,

Antworten:

6

Perl 6 , 20 Schnipsel

{$_ eq m/[[<-[()*?|\\]>|\\<[()*?|\\]>|'(' <~~>* ')']<[*?]>?|\|]+/}

Probieren Sie es online aus!

Die Schnipsel stammen aus:

{$_ eq, m/[, <-[, ()*?, |\\, ]>, |\\, <[, ()*?, |\\, ]>, |, '(' <~~>* ')', <[, *?, ]>, ?|, \|, ]+/, }.

Dies ist meistens der gierige Ansatz (der durch alle ein oder zwei Charakterausschnitte deutlich wird). Ich habe SymbolHound verwendet , um nach den einzelnen Zeichen zu suchen, und die einzige wirkliche Optimierung war das '(' <~~>* ')'Snippet, das meiner eigenen Antwort auf rekursive Perl 6-Regexe entnommen ist.

Erläuterung:

Dies prüft grundsätzlich, ob die Eingabe einer gierigen Übereinstimmung eines gültigen regulären Ausdrucks entspricht. Der Grund, warum wir nicht einfach den regulären Ausdruck selbst verwenden und hinzufügen können ^$, um die Enden zu markieren, ist, dass wir einen rekursiven regulären Ausdruck verwenden, der ohne ^$Markierungen nicht funktionieren würde . Der Regex selbst ist:

m/[                             ]+/   # Match one or more times
   [              ]  # Any of 
    <-[()*?|\\]> |     # Not a metacharacter
    \\<[()*?|\\]>      # A metacharacter preceded by a \
    '(' <~~>* ')'      # Brackets surrounding a valid regex
                   <[*?]>?  # Optionally followed by a ? or *
                           | \|    # Or just the | metacharacter

Scherzen
quelle
Bis ~~, danke!
user0721090601
@guifa Ja, das habe ich durch die P6-Spezifikation gelernt , die viele Dinge enthält, die noch nicht richtig dokumentiert wurden. Ich vermute, dass ~~es nicht angezeigt wird, weil es (zum Beispiel <~~0>) noch nicht vollständig implementiert ist , obwohl es dort andere versteckte Juwelen gibt.
Jo King