[QUIZ #18] Reguläre Ausdrücke - Reverse Engineered


ComFreek

Mod | @comfreek
Moderator
Coding-Quiz {18}
Reguläre Ausdrücke - Reverse Engineered


Regeln
Es ist erlaubt und erwünscht, dass ihr euch direkt in diesem Thema über die Aufgabe austauscht.
Also stellt bei Unklarheiten in der Aufgabenstellung oder Problemen bei der Umsetzung Fragen,
versorgt uns mit nützlichen oder weiterführenden Links, diskutiert mögliche Lösungsansätze.
Macht bei Beiträgen, die allzu viel verraten, aber bitte trotzdem Gebrauch vom [ spoiler ]-Tag.

Sinn der Sache ist nicht, fertige Codes/Libraries zu genau der Aufgabe von irgendwo zu Kopieren.

Die verwendete(n) Programmiersprache(n) steht frei zur Auswahl,
mehrere Lösungen in verschiedenen Sprachen sind erlaubt.

Die Abgabe erfolgt wie immer im Abgabeforum.
Threadname bitte in Form: [Quiz #18] Name (Sprache)
Die Einreichungen sind dort vorerst nicht für andere Teilnehmer sichtbar;
Danach kann natürlich alles gelesen und auch diskutiert werden.
Es ist nur die höchste gemachte Schwierigkeitsstufe abzugeben,
da sie automtisch die Niedrigeren erfüllt. Sofern diese nicht gelöst werden konnte,
sind die Codes für die niedrigeren Stufen natürlich auch willkommen!

Abgabefrist ist Sonntag, der 29. September 2013 um 23:59 Uhr.


Die Aufgabe

Reguläre Ausdrücke sind von jeher ein mächtiges Werkzeug,
welche dem Programmierer an die Hand gelegt wird.
Normalerweise prüft solch ein RegExp, ob ein Text zu ihm passt,
doch nun spielen wir das Spiel rückwärts: findet einen Text, der zum RegExp passt!


Allgemeines

"Zeilenbegrenzer" bei den Regexp werde implizit angenommen.
Die Regexp a.c passt also auf abc, nicht aber auf mnoabcqrst
(was zB. .*a.c.* wäre)

Von den Regexp sollen mindestens unterstützt werden:

  • Fixe String und der Punkt . für ein beliebiges Zeichen
  • * (Etwas beliebig oft wie .*), ? (0 oder 1 mal),
    + (Mindestens einmal), {min,max} (Genaue Grenzen der erlaubten Anzahl)
  • ( | ) Logisches Oder und Klammerung zum Abgrenzen und Schachteln
  • \ Escapen der Steuerzeichen. Escapesequenzen wie \n Zeilenwechsel sind nicht erforderlich
  • [] [^] Beschränken des erlaubten Zeichens, und die Nicht-variante
    Die zulässigen Zeichenbeschränkungen [] :
    • Aufzählungen wie abcdef
    • Gruppen wie a-z A-Z 0-9
    • \s Whitespace
    • \d Zahlen (entspricht [0-9], sofern man Unicode außen vor lässt)
Syntaxänderungen sind erlaubt.

Als Alphabet soll mindestens der ASCII-Code (die ersten 128 Zeichen) zur Verfügung stehen.
Nicht nur abc, 01 oder Ähnliches.

Hinweis: Wer mit Unicode arbeiten will sollte beachten,
dass beim man sich beim Direktzugriff auf Buchstaben eines Strings
ggf. selbst mit verschiedenen Bytelängen pro Zeichen herumärgern kann,
weil zB. Java-char´s nur 2 Byte haben (während es zB. in UTF8 und UTF16 Längeres gibt).

Hier ein paar Regexes, damit ihr eure Parser testen könnt (sofern ihr einen nutzt):
Code:
[0-9]*
[asd]+.?a?([^asd]){2,3}
\s+[^\s]*\\s{2,3}
[0-9][a-z]*.+\s{89,100}.*[uas\s]

Stufe 1
Euer Programm soll für einen regulären Ausdruck R
jeweils mindestens n passende Texte finden
(oder weniger, falls nicht mehr möglich sind)
R und n sind vom Benutzer einzugeben.

Als Beispiele könnt ihr folgende nutzen:

a) n = 10
Code:
[a-zA-Z][^reg](exp|sind).[toll]?

b) n = 1
Code:
[^comfreek]*
:)

Der Einfachkeit halber kann man annehmen, dass die Texte
eine vorgegebene Maximallänge nicht überschreiten.

Bruteforce-Lösungen sind ausdrücklich erlaubt.
Die Verwendung fertiger Sachen zum Prüfen, ob ein String ein Regexp matcht, ist erlaubt.

Art der Eingabe/Ausgabe bleibt euch überlassen (Konsole, Gui, Dateien...)

Stufe 2
Nun erweitert euer Programm so, dass mehrere reguläre Ausdrücke
gleichzeitig berücksichtigt werden.

Das Programm soll nun mindestens n Strings ausgeben,
die jeweils auf alle regulären Ausdrücke passen.


Stufe 3
Diesmal ist es wieder nur ein Regexp, der gelten muss,
aber: Bruteforce-Durchprobieren aller Wörter ist nicht mehr erlaubt.
Damit fällt auch die Annahme zur maximalen Länge weg.

Damit die Aufgabe nicht ganz so schwer wird beschränken wir die Syntax der regulären Ausdrücke:
Es muss nichts unterstützt werden, was irgendwie mit variablen Anzahlen zu tun hat,
also keine * + ? {} mehr.

Die Implementierung ist/sollte zwangsläufig mit Stufe 1 kompatibel sein
(wenn man die vereinfachte Syntax beachtet).

Stufe 4
Noch ein Schritt schwerer: Mehrfache Regexp (die wieder alle zusammen gelten müssen).
nach wie vor kein Bruteforce und vereinfachte Syntax.

Die Implementierung ist/sollte zwangsläufig mit Stufe 1+2+3 kompatibel sein
(wenn man die vereinfachte Syntax beachtet).


Stufe 5
Die Spitze des Ganzen:
Mehrfache Regexp, kein Bruteforce, aber:
Volle Regexp, ohne Vereinfachung.

Wer diese letzte Stufe schafft deckt mit diesem Programm auch alle anderen Stufen ab.


Und jetzt ran an die Tasten und viel Spaß beim Programmieren!
 
Zuletzt bearbeitet von einem Moderator:

sheel

I love Asm
So ist garantiert, dass jeder min. eine Stufe schafft (oder auch nicht) :p
Und so low wirds gar nicht, wenn man den Zeitverbrauch
bei Primitivvarianten für lange Strings beachtet...
 

ibafluss

Erfahrenes Mitglied
Tolles Quiz - ich bin auch dabei.

Bei den Beispielen a) und b): Macht es keinen Unterschied ob ^ innerhalb der [] oder auserhalb der [] ist?

Lg
 

mermshaus

Erfahrenes Mitglied
Doch, macht es. In ^[comfreek]* steht das ^ nicht für die Negierung der Zeichenklasse. Du kannst es dir entweder wegdenken ([comfreek]*) oder es in die Zeichenklasse setzen ([^comfreek]*). Das sind aber ja sowieso nur Beispiele.

Hintergrund: Außerhalb von Zeichenklassen steht ^ für „Eingabe-/Zeilenanfang“. Das wurde aber für die vereinfachte Version von regulären Ausdrücken nicht definiert.

Edit: Technisch gesehen kannst du es interpretieren, wie du willst, denn in der Aufgabenstellung steht: „Syntaxänderungen sind erlaubt.“
 
Zuletzt bearbeitet:

sheel

I love Asm
Sorry, eine Korrektur: Das ^ bei comfreek war innerhalb der Klammern gedacht.
Oben auch ausgebessert.

Syntaxänderungen: Erweitern ist natürlich auch kein Problem,
aber vor allem war gemeint, ggf. andere Zeichen für die Funktionalität verwenden zu dürfen.
Wenn man etwas Fertiges zum Prüfen verwendet...
die genannten Zeichen sind zwar ziemlich allgemeingültig,
aber eventuell muss man doch Änderungen vornehmen, damit der Prüfer die Syntax versteht.

PS: Falls es jemanden verwirrt:
[^comfreek]* sind beliebig viele Buchstaben, in denen kein c, kein o... enthalten sind.
Es geht nicht um das ganze Wort.
Das doppelte e ist ein kleiner Witz in der Hinsicht :)
 

ComFreek

Mod | @comfreek
Moderator
Hmm, nicht unbedingt.

Momentan bin ich eh von der eigtl. Idee abgedriftet, habe jetzt eine eigene Regexengine zum Matchen gebaut :D Allerdings funktioniert mein NegativeTokenGroup ([^abc]) noch nicht.

Würde C++ oder Java echt empfehlen wegen OOP.

/Edit Mittlerweile funktioniert soweit Alles, ich müsste nur noch Regexes parsen.