Как я могу выполнить частичное совпадение с java.util.regex. *?

Question

Я использую классы java.util.regex. * Для регулярных выражений в Java и пока все хорошо. Но сегодня у меня другое требование. Например, рассмотрите образец, чтобы быть "aabb". Теперь, если входная строка - это aa, она определенно не будет совпадать, однако есть вероятность, что если я добавлю bb, она станет aabb, и она совпадет. Однако, если бы я начал с cc, то, что бы я ни добавил, он никогда не совпадет.

Я изучил класс Pattern и Matcher, но не нашел способа достичь этого.

Входные данные поступят от пользователя, и система должна дождаться совпадения с шаблоном, иначе они никогда не будут совпадать, независимо от дальнейшего ввода.

Любая подсказка?

Спасибо.

Answer 1

Вы должны были присмотреться к Matcher API; метод hitEnd() работает точно так же, как вы описали:

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);
      }
    }
  }
}

Выход:

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

Насколько я знаю, Java - единственный язык, который предоставляет эту функциональность. Есть также метод requireEnd(), который сообщает вам, может ли большее количество входных данных превратить совпадение в несоответствие, но я не думаю, что оно уместно в вашем случае.

Оба метода были добавлены для поддержки класса Scanner, чтобы он мог применять регулярные выражения к потоку без необходимости считывания всего потока в память.

Answer 2

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

Answer 3

Итак, вы хотите знать не соответствует ли строка String регулярному выражению, но может ли быть более длинная строка, начинающаяся с s, которая будет соответствовать? Извините, регулярные выражения не могут вам помочь, потому что вы не получаете доступа к внутреннему состоянию сопоставителя; вы получаете только логический результат и любые группы, которые вы определили, поэтому вы никогда не узнаете , почему совпадение не удалось.

Если вы хотите взломать библиотеки JDK, вы можете расширить (или, возможно, разветвить) java.util.regex и предоставить больше информации о процессе сопоставления. Если совпадение не удалось из-за того, что вход «использовался», ответом будет true ; если он потерпел неудачу из-за различения символов или других проверок, это будет false . Это похоже на большую работу, потому что ваша проблема полностью противоположна тому, что должны делать регулярные выражения.

Другой вариант: может быть, вы можете просто переопределить задачу, чтобы можно было рассматривать ввод как регулярное выражение и сопоставлять aabb с * aa. **? Вы должны быть осторожны с метасимволами регулярных выражений.

Answer 4

Если вы сделаете каждый символ регулярного выражения необязательным и ослабите ограничения множественности, вы получите то, что хотите. Например, если у вас есть соответствующий шаблон «aa (abc) + bbbb», вы можете иметь шаблон «возможного соответствия» a? A? (A? B? C?) * B? B? B? B? '.

Этот механический способ создания шаблона возможного совпадения не распространяется на сложные конструкции, такие как прямая и обратная ссылки.

Answer 5

Один из способов сделать это - разобрать ваше регулярное выражение в последовательность под-регулярных выражений, а затем собрать их так, чтобы вы могли выполнить частичное совпадение; например «ab c» имеет 3 под-регулярных выражения «a», «b » и «c», которые затем можно собрать как «a (b * (c)?)?».

Ситуация усложняется, когда входное регулярное выражение содержит чередование и группы, но тот же общий подход должен работать.

Проблема с этим подходом состоит в том, что полученное регулярное выражение является более сложным и потенциально может привести к чрезмерному обратному отслеживанию для сложных входных регулярных выражений.

Answer 6

Вы можете сделать это с помощью конечного автомата (http://en.wikipedia.org/wiki/State_machine).. Ваши состояния / переходы представляют собой допустимый ввод и одно состояние ошибки. Затем вы можете передать конечному автомату один символ (возможно, подстроку в зависимости от ваших данных). ) в любой момент. В любой момент вы можете проверить, находится ли ваш конечный автомат в состоянии ошибки. Если он не находится в состоянии ошибки, то вы знаете, что будущие входные данные могут все еще совпадать. Если он находится в состоянии ошибки, то вы знаете что-то ранее произошел сбой, и любой будущий ввод не сделает строку действительной.

Answer 7

В приведенном вами примере вы можете попробовать использовать антишаблон для дисквалификации недействительных результатов. Например, «^ [^ a]» скажет вам, что вы вводите «c ...» не может соответствовать вашему примеру шаблона «aabb».

В зависимости от вашего паттерна вы можете разбить его на более мелкие паттерны, чтобы проверить и использовать несколько совпадений, а затем установить их границы, когда происходит одно совпадение, и вы переходите к следующему. Этот подход может работать, но если ваш шаблон сложен и может иметь подчасти переменной длины, вы можете в конечном итоге переопределить часть соответствия в вашем собственном коде, чтобы скорректировать возможные границы соответствия, чтобы сделать его более или менее жадным. Общая идея псевдокода:

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;
    }
  }
}

Затем вы можете объединить эту идею с анти-шаблонами и иметь анти-субпаттерны, и после каждого совпадения с суб-паттерном вы проверяете следующий анти-шаблон, если он совпадает, вы знаете, что вы потерпели неудачу, в противном случае продолжите соответствующий шаблон. Вы, вероятно, захотите вернуть что-то вроде enum вместо логического (то есть ALL_MATCHED, PARTIAL_MATCH, ANTI_PATTERN_MATCH, ...)

Опять же, в зависимости от сложности вашего фактического паттерна, который вы пытаетесь сопоставить, написание соответствующих суб-паттернов / анти-паттернов может быть трудным, если не невозможным.