Wie kann ich eine teilweise Übereinstimmung mit java.util.regex.* durchführen?

Question

Ich habe die java.util.regex.* Klassen für reguläre Ausdrücke in Java und alles gut so weit verwendet. Aber heute habe ich eine andere Anforderung. Nehmen wir zum Beispiel an, das Muster sei "aabb". Wenn die eingegebene Zeichenkette nun aa ist, wird sie definitiv nicht übereinstimmen, aber es besteht immer noch die Möglichkeit, dass, wenn ich bb anhänge, es zu aabb wird und es passt. Hätte ich jedoch mit cc begonnen, würde es nie passen, egal was ich anhänge.

Ich habe die Klasse Pattern und Matcher untersucht, aber keine Möglichkeit gefunden, dies zu erreichen.

Die Eingabe kommt vom Benutzer, und das System muss warten, bis das Muster übereinstimmt, oder es wird nie übereinstimmen, unabhängig von einer weiteren Eingabe.

Haben Sie einen Hinweis?

Danke.

Answer 1

Sie hätten sich die Matcher-API genauer ansehen sollen; die hitEnd() Methode funktioniert genau wie von Ihnen beschrieben:

import java.util.regex.*;

public class Test
{
  public static void main(String[] args) throws Exception
  {
    String[] ss = { "aabb", "aa", "cc", "aac" };
    Pattern p = Pattern.compile("aabb");
    Matcher m = p.matcher("");

    for (String s : ss) {
      m.reset(s);
      if (m.matches()) {
        System.out.printf("%-4s : match%n", s);
      }
      else if (m.hitEnd()) {
        System.out.printf("%-4s : partial match%n", s);
      }
      else {
        System.out.printf("%-4s : no match%n", s);
      }
    }
  }
}

Ausgabe:

aabb : match
aa   : partial match
cc   : no match
aac  : no match

Soviel ich weiß, ist Java die einzige Sprache, die diese Funktionalität bietet. Außerdem gibt es die requireEnd() Methode, die Ihnen sagt, ob weitere Eingaben eine Übereinstimmung in eine Nicht-Übereinstimmung verwandeln könnten, aber ich glaube nicht, dass dies in Ihrem Fall relevant ist.

Beide Methoden wurden hinzugefügt, um die Scanner-Klasse zu unterstützen, damit sie Regexe auf einen Stream anwenden kann, ohne dass der gesamte Stream in den Speicher eingelesen werden muss.

Answer 2

Pattern p = Pattern.compile(expr);
Matcher m = p.matcher(string);
m.find();

Answer 3

Sie wollen also nicht wissen, ob eine Zeichenkette s mit der Regex übereinstimmt, sondern ob es eine längere Zeichenkette gibt, die mit s beginnt, die passen würde? Regexe können Ihnen hier leider nicht helfen, da Sie keinen Zugriff auf den internen Zustand des Matchers haben; Sie erhalten nur das boolesche Ergebnis und alle von Ihnen definierten Gruppen, so dass Sie nie wissen warum ein Spiel ist fehlgeschlagen.

Wenn Sie bereit sind, die JDK-Bibliotheken zu hacken, können Sie erweitern (oder wahrscheinlich forken) java.util.regex und geben weitere Informationen über den Abgleichvorgang aus. Wenn der Abgleich fehlgeschlagen ist, weil die Eingabe "aufgebraucht" war, lautet die Antwort wahr Wenn sie aufgrund von Charakterdiskriminierung oder anderen Prüfungen scheitern würde, wäre sie falsch . Das scheint aber eine Menge Arbeit zu sein, denn Ihr Problem ist genau das Gegenteil von dem, was Regexe tun sollen.

Eine andere Möglichkeit: Vielleicht können Sie die Aufgabe einfach so umdefinieren, dass Sie die Eingabe als Regexp behandeln und abgleichen können aabb gegen *aa.**? Bei Regex-Metacharakteren müssen Sie allerdings vorsichtig sein.

Answer 4

Für das von Ihnen genannte Beispiel könnten Sie versuchen, ein Anti-Pattern zu verwenden, um ungültige Ergebnisse zu disqualifizieren. Zum Beispiel würde "^[^a]" Ihnen sagen, dass Ihre Eingabe "c..." nicht mit Ihrem Beispielmuster "aabb" übereinstimmen kann.

Je nach Muster können Sie es in kleinere Muster aufteilen und mehrere Abgleicher verwenden, deren Grenzen Sie dann beim Auftreten einer Übereinstimmung festlegen und zum nächsten übergehen. Dieser Ansatz kann funktionieren, aber wenn Ihr Muster komplex ist und Unterteile mit variabler Länge haben kann, müssen Sie möglicherweise einen Teil des Matchers in Ihrem eigenen Code neu implementieren, um die möglichen Grenzen der Übereinstimmung anzupassen, damit er mehr oder weniger gierig ist. Eine Pseudocode-Idee hierfür wäre:

boolean match(String input, Matcher[] subpatterns, int matchStart, int matchEnd){
  matcher = next matcher in list;
  int stop = matchend;
  while(true){
    if matcher.matches input from matchstart -> matchend{
      if match(input, subpatterns, end of current match, end of string){
        return true;
      }else{
        //make this match less greedy
        stop--;
      }
    }else{
      //no match
      return false;
    }
  }
}

Man könnte diese Idee dann mit den Anti-Mustern zusammenführen und Anti-Teilmuster haben, und nach jeder Teilmusterübereinstimmung das nächste Anti-Muster prüfen, wenn es übereinstimmt, weiß man, dass man gescheitert ist, andernfalls setzt man das übereinstimmende Muster fort. Sie würden wahrscheinlich so etwas wie ein Enum anstelle eines Booleans zurückgeben wollen (d.h. ALL_MATCHED, PARTIAL_MATCH, ANTI_PATTERN_MATCH, ...)

Auch hier hängt es von der Komplexität des eigentlichen Musters ab, das Sie abgleichen wollen, und es kann schwierig, wenn nicht gar unmöglich sein, die entsprechenden Submuster/Antipattern zu schreiben.

Answer 5

Eine Möglichkeit, dies zu tun, besteht darin, den Regex in eine Folge von Sub-Regexen zu zerlegen und diese dann so wieder zusammenzusetzen, dass Sie partielle Übereinstimmungen erzielen können, z. B. "ab c" hat 3 Unter-Regexe "a", "b " und "c", die Sie dann als "a(b*(c)?)?" neu zusammensetzen können.

Die Dinge werden komplizierter, wenn der Eingabe-Regex Alternationen und Gruppen enthält, aber der gleiche allgemeine Ansatz sollte funktionieren.

Das Problem bei diesem Ansatz ist, dass die resultierende Regex komplizierter ist und bei komplexen Eingabe-Regexen zu einem übermäßigen Backtracking führen kann.