Регулярное выражение не соответствует набору строк

Question

Как построить регулярное выражение, не содержащее набор строк внутри.

В этом примере я хочу проверить текстовое поле Адресная строка 1, чтобы оно не содержало никаких вторичных частей адреса, таких как «Apt», «Bldg», «Ste», «Unit» и т. Д.

Answer 1

Регулярное выражение может использоваться для проверки того, что строка не содержит набора слов. Вот проверенный фрагмент кода Java с закомментированным регулярным выражением, который делает именно это:

if (s.matches("(?sxi)" +
    "# Match string containing no 'bad' words.\n" +
    "^                # Anchor to start of string.\n" +
    "(?:              # Step through string one char at a time.\n" +
    "  (?!            # Negative lookahead to exclude words.\n" +
    "    \\b          # All bad words begin on a word boundary\n" +
    "    (?:          # List of 'bad' words NOT to be matched.\n" +
    "      Apt        # Cannot be 'Apt',\n" +
    "    | Bldg       # or 'Bldg',\n" +
    "    | Ste        # or 'Ste',\n" +
    "    | Unit       # or 'Unit'.\n" +
    "    )            # End list of words NOT to be matched.\n" +
    "    \\b          # All bad words end on a word boundary\n" +
    "  )              # Not at the beginning of bad word.\n" +
    "  .              # Ok. Safe to match this character.\n" +
    ")*               # Zero or more 'not-start-of-bad-word' chars.\n" +
    "$                # Anchor to end of string.")
    ) {
    // String has no bad words.
    System.out.print("OK: String has no bad words.\n");
} else {
    // String has bad words.
    System.out.print("ERR: String has bad words.\n");
} 

Это предполагает, что слова должны быть "целыми" словами и что "плохие" слова должны распознаваться независимо от регистра. Также обратите внимание (как правильно сказали другие), что это не так эффективно, как просто проверять наличие плохих слов и затем принимать логическое НЕ.

Answer 2

Более теоретический ответ:

Детерминированные конечные автоматы имеют взаимно однозначное соответствие с регулярными выражениями;то есть для каждого обычного языка вы можете создать DFA, который будет принимать именно те строки, которые содержатся в обычном языке.И для каждого обычного языка вы можете создать регулярное выражение, которое будет соответствовать только строкам на этом языке.Таким образом, для любого регулярного выражения можно создать DFA, который принимает точно такие же строки, и наоборот.

Недетерминированный конечный автомат (NFA) можно превратить в детерминированный конечный автомат (DFA) с помощьюпостроение состояния DFA для каждой комбинации состояний в NFA.(Это | Q | ² состояний, что является конечным числом.)

С этим знанием мы можем обратить DFA A и создать DFA A', который принимает каждыйстрока, которую A отклоняет, и отклоняет каждую строку, которую A принимает.

Это можно сделать, превратив все конечные состояния во временные начальные состояния, а начальное состояние - в конечное состояние.Затем мы добавляем epsilon-переходы из нового начального состояния в каждое из этих временных начальных состояний, чтобы сделать его действительным NFA (epsilon-NFA, если вы хотите придираться).Затем мы превращаем его в DFA, поскольку мы знаем, что можем это сделать.

Единственный оставшийся шаг - превратить наш новый DFA в регулярное выражение.Алгоритм для этого глупо прост: для каждого пути от начального до конечного состояний мы включаем его в регулярное выражение, используя | (или) для каждой ветви, конкатенацию для последовательных состояний и * (закрытие клины) длякаждый цикл.

Answer 3

Вы делаете отрицание строк, которые вам не нужны - например,

"ten" !~ /one|two|three/

Это дает вам:

print "one" !~ /one|two|three/ --> false
print "two" !~ /one|two|three/ --> false
print "ten" !~ /one|two|three/ --> true

Answer 4

Вместо того чтобы пытаться создать регулярное выражение для сопоставления строк, которые не содержат эти подстроки, почему бы не создать регулярное выражение для сопоставления строк, которые do содержат одну или несколько из них?Затем, если это регулярное выражение возвращает true, вы знаете, что у вас неверная строка.