How do I write a regex to match any string that doesn't meet a particular pattern? I'm faced with a situation where I have to match an (A and ~B) pattern.
+7
A:
You could use a look-ahead assertion:
(?!999)\d{3}
This example matches three digits other than 999.
But if you happen not to have a regular expression implementation with this feature (see Comparison of Regular Expression Flavors), you probably have to build a regular expression with the basic features on your own.
A compatible regular expression with basic syntax only would be:
[0-8]\d\d|\d[0-8]\d|\d\d[0-8]
This does also match any three digits sequence that is not 999.
Gumbo
2009-03-04 18:41:03
Look-ahead is not standard regular expression syntax, it is a Perl extension, it will only work in Perl, PCRE (Perl-Compatible RegEx) or other non-standard implementations
Juliano
2009-03-04 19:26:54
It may not be standard, but don't most modern languages support it? What language *doesn't* support look-aheads these days?
Bryan Oakley
2009-03-04 19:45:46
That’s true. But most regex flavors support this feature (see <http://www.regular-expressions.info/refflavors.html>).
Gumbo
2009-03-04 19:49:02
Turns out that the windows findstr function only supports pure DFA-style regex anyway, so I need to just do it all differently. You still get the answer, though.
notnot
2009-03-04 21:38:04
Won't work, [] defines a character class, and matches a single character, not a subpattern.
Richard
2009-03-04 18:43:48
Wouldn't work at all. [^XYZ] simply won't match the characters X, Y, or Z. Meaning not only will it not-match "XYZ", but also "ZXY", which is not a pattern matched by the regex XYZ. Meaning that this "solution" fails the basic requirements.
Devin Jeanpierre
2009-03-04 18:45:41
he's right, my bad. I think thats just highlighted a bug in some regex i have!
Andrew Bullock
2009-03-04 21:38:58
A:
A[^B]
literally matches, A, and ~ B
so the following match
AC
AD
AF
and these doesn't
AB
Q
I think it works by making a character class of everything thats not B ([AC-Za-z0-9]) I believe that includes all off the asciibet.
Ape-inago
2009-03-04 18:47:15
[^B] merely says "any *character* other than B". The original question was related to an expression. You can't just put an arbitrary expression inside [].
Bryan Oakley
2009-03-04 19:00:24
" I'm faced with a situation where I have to match an (A and ~B) pattern."technically, A[^B] is that pattern...
Ape-inago
2009-03-06 20:20:01
+4
A:
Match against the pattern and use the host language to invert the boolean result of the match. This will be much more legible and maintainable.
Ben S
2009-03-04 18:48:29
Then I just end up with (~A or B) instead of (A and ~B). It doesn't solve my problem.
notnot
2009-03-04 21:06:38
Pseudo-code:String toTest;if (toTest.matches(A) AND !toTest.matches(B)) { ... }
Ben S
2009-03-04 21:54:23
I should have been more clear - the pieces are not fully independent. If A matches part of the string, then we care if ~B matches the rest of it (but not necessarily the whole thing). This was for the windows command-line findstr function, which i found is restricted to true regexs, so moot point.
notnot
2009-03-04 22:07:46
+2
A:
This seems somewhat a basic question of Formal Languages or Theoretical Computer Science classes. I'm assuming that it is not homework based on your reputation and previous answers, so I'm answering this.
The complement of a regular language is also a regular language, but to construct it you have to build the DFA for the regular language, and make any valid state change into an error. See this for an example. What the page doesn't say is that it converted /(ac|bd)/ into /(a[^c]?|b[^d]?|[^ab])/. The conversion from a DFA back to a regular expression is not trivial. It is easier if you can use the regular expression unchanged and change the semantics in code, like suggested before.
Juliano
2009-03-04 19:11:16
If I were dealing with actual regex's then this would all be moot. Regex now seems to refer to the nebulous CSG-ish (?) space of pattern matching that most langauges support. Since I need to match (A and ~B), there's no way to remove the negation and still do it all in one step.
notnot
2009-03-04 21:48:40
Lookahead, as described above, would have done it if findstr did anything beyond true DFA regexs. The whole thing is sort of odd and I don't know why I have to do this command-line (batch now) style. It's just another example of my hands being tied.
notnot
2009-03-04 21:53:19
@notnot: You are using findstr from Windows? Then you just need /v. Like:findstr A inputfile | findstr /v B > outputfile.txtThe first matches all lines with A, the second matches all lines that doesn't have B.
Juliano
2009-03-04 22:04:01
Thanks! That's actually exactly what I needed. I didn't ask the question that way, though, so I still giving the answer to Gumbo for the more generalized answer.
notnot
2009-03-05 17:16:10