home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
Crawly Crypt Collection 2
/
crawlyvol2.bin
/
program
/
c
/
berm122s
/
patmat.c
< prev
next >
Wrap
C/C++ Source or Header
|
1993-08-16
|
3KB
|
62 lines
#include <stdio.h>
/* Function: patmat
Purpose : Regular Expression Pattern Matching
Author : Sreenath Chary
Notice : Quite brilliantly optimized by Arjen G. Lentz
(according to Mr. Lentz himself)
Usage : Pass two string pointers as parameters. The first being a raw
string & the second a pattern the raw string is to be matched
against. If the raw string matches the pattern,then the function
returns 1, else it returns 0.
e.g. patmat("abcdefghi","*ghi") returns a 1.
patmat("abcdefghi","??c??f*") returns a 1.
patmat("abcdefghi","*dh*") returns a 0.
patmat("abcdefghi","*def") returns a 0.
The asterisk is a wild card to allow any characters from its first
appearance to the next specific character. The character ? is a
wild card for only one character in the position it appears.
Combinations such as "*?" or "?*" or "**" are illegal for obvious
reasons & the functions may goof, though I think it will still
work.
Logic : The only simple way I could devise is to use recursion. Each
character in the pattern is taken & compared with the character in
the raw string. If it matches then the remaining amount of the
string & the remaining amount of the pattern are passed as
parameters to patmat again until the end of the pattern. If at
any stage the pattern does not match,then we go back one level &
at this level if the previous character was a asterisk in the
pattern, we hunt again from where we left off, otherwise we return
back one more level with a not found & the process goes on till
the first level call.
Only one character at a time is considered, except when the
character is an asterisk. You'll get the logic as the program
unfolds.
*/
int patmat(char *raw, char *pat) /* regular expression pattern matching */
{
if (!*pat) /* end of both is ok, only pat is mismatch */
return (!*raw);
if (*pat == '*') { /* wildcard '*' */
if (!*++pat) /* last pat char? ok */
return (1);
do if ((*raw == *pat || *pat == '?') && /* match/wild ? */
patmat(raw + 1,pat + 1)) /* match rest of pat */
return (1);
while (*raw++);
}
else if (*raw && (*pat == '?' || *pat == *raw)) /* match/wild ? */
return (patmat(++raw,++pat)); /* try & match rest of it*/
return (0); /* no match found */
}/*patmat()*/
/* end of patmat.c */