简单的通配符匹配算法

  1 #pragma once
  2 #ifndef CHECKER
  3 #define CHECKER
  4 
  5 #include <iostream>
  6 #include <string>
  7 #include <sstream>
  8 using namespace std;
  9 
 10 class Checker
 11 {
 12 public:
 13     Checker(void){}
 14     ~Checker(void){}
 15 
 16     // 匹配模式
 17     enum MatchMode
 18     {
 19         // 全部匹配
 20         ALL,
 21         // 任意匹配
 22         ANY,
 23         // 都不匹配
 24         NONE
 25     };
 26 
 27     // 是否匹配
 28     int isMatch(string input, string* patterns, int pLen, MatchMode mode){
 29         istringstream ss = istringstream(input);
 30         int matchOne = 0;
 31         istringstream ssPattern;
 32         switch (mode)
 33         {
 34         case Checker::ALL:
 35             for (int i = 0; i < pLen; i++)
 36             {
 37                 matchOne = isMatch(ss, ssPattern);
 38                 if(!matchOne)
 39                     return false;
 40             }
 41             return true;
 42         case Checker::ANY:
 43             for (int i = 0; i < pLen; i++)
 44             {
 45                 matchOne = isMatch(ss, ssPattern);
 46                 if(matchOne)
 47                     return true;
 48             }
 49             return false;
 50         case Checker::NONE:
 51             for (int i = 0; i < pLen; i++)
 52             {
 53                 matchOne = isMatch(ss, ssPattern);
 54                 if(matchOne)
 55                     return false;
 56             }
 57             return true;
 58         default:
 59             return false;
 60         }
 61     }
 62 
 63     // 是否匹配
 64     int isMatch(string input, string pattern){
 65         istringstream ss = istringstream(input);
 66         istringstream ssPattern = istringstream(pattern);
 67         return isMatch(ss, ssPattern);
 68     }
 69 
 70     // 是否匹配
 71     int isMatch(istream &input, istream &pattern)
 72     {
 73         char left,right;
 74         while (Token t = getToken(pattern, false))
 75         {
 76             switch (t)
 77             {
 78             case END:
 79                 return true;
 80             case CONT:
 81                 if(!pattern.get(right))
 82                     return true;
 83                 input.get(left);
 84                 if(left != right)
 85                     return false;
 86                 break;
 87             case STAR:
 88             {
 89                 t = getToken(pattern, true);
 90                 if(t != CONT){
 91                     if(!isMatch(input, pattern))
 92                         return false;
 93                     break;
 94                 }else{
 95                     if(!pattern.get(right))
 96                         return true;
 97                     int flag = 0;
 98                     while (input.get(left))
 99                     {
100                         if(flag = (left == right))
101                             break;
102                     }
103                     // cant‘t find match till end of file
104                     // i.e "abcd" didn‘t match "*e"
105                     if(input.eof() && !flag)
106                         return false;
107                     else
108                         break;
109                 }
110             }
111             case QUS:
112             {
113                 t = getToken(pattern, true);
114                 if(t != CONT){
115                     if(!isMatch(input, pattern))
116                         return false;
117                     break;
118                 }else{
119                     if(!pattern.get(right))
120                         return true;
121                     // skip one char
122                     input.get(left).get(left);
123                     if(left != right)
124                         return false;
125                     break;
126                 }
127             }
128             case SPEC:
129             {
130                 SymbolToken simbol = getSimbol(pattern);
131                 switch (simbol)
132                 {
133                     case SBL_POS_INT:
134                     {
135                         int num = getInt(input);
136                         if(num < 0){
137                             cerr << "Error : only positive int is supported.";
138                             return false;
139                         }
140                         break;
141                     }
142                     case SBL_REAL:
143                     {
144                         double num;
145                         if(!(input >> num))
146                             cerr << "Error : failed in parsing input into double.";
147                         break;
148                     }
149                     case SBL_WRD:
150                     {
151                         if(!input.get(left))
152                             return false;
153                         if(!isalpha(left))
154                             return false;
155                         break;
156                     }
157                     case SBL_SLASH:
158                     {
159                         if(!input.get(left))
160                             return false;
161                         if(left != ‘\\‘)
162                             return false;
163                         break;
164                     }
165                     default:
166                         cerr << "Error : simbol expected.";
167                         return false;
168                 }
169             }
170             default:
171                 break;
172             }
173         }
174         return true;
175     }
176 
177 private:
178     // 令牌
179     enum Token
180     {
181         // 结束
182         END,
183         // 内容
184         CONT,
185         // 通配符*
186         STAR = ‘*‘,
187         //通配符?
188         QUS = ‘?‘,
189         //转义符
190         SPEC = ‘\\‘, 
191     };
192 
193     enum SymbolToken
194     {
195         // 结束
196         UNKNOWN,
197         // 正整数
198         SBL_POS_INT = ‘d‘,
199         // 字符
200         SBL_WRD = ‘w‘,
201         // 实数
202         SBL_REAL = ‘r‘,
203         // 转义符
204         SBL_SLASH = ‘\\‘
205     };
206 
207     // 获取符号令牌
208     SymbolToken getSimbol(istream& stream){
209         char c = 0;
210         if(!stream.get(c))
211             return UNKNOWN;
212         return SymbolToken(c);
213     }
214 
215     // 获取正整数
216     int getInt(istream& stream){
217         char c;
218         int result = 0;
219         while (stream.get(c) && c >= ‘0‘ && c <=‘9‘)
220         {
221             result = result*10 + c - ‘0‘;
222         }
223         stream.putback(c);
224         return result;
225     }
226 
227     // 获取令牌
228     Token getToken(istream& stream, bool putback){
229         char c = 0;
230         if(!stream.get(c))
231             return END;
232         Token result;
233         switch (c)
234         {
235         case ‘*‘:case ‘?‘:case ‘\\‘:
236             result = Token(c);
237             if(putback)
238                 stream.putback(c);
239             break;
240         default:
241             stream.putback(c);
242             result = CONT;
243         }
244         return result;
245     };
246 
247     int isMatch(istream &input, istream &pattern){
248         char left;
249         SymbolToken simbol = getSimbol(pattern);
250         switch (simbol)
251         {
252             case SBL_POS_INT:
253             {
254                 int num = getInt(input);
255                 if(num < 0){
256                     cerr << "Error : only positive int is supported.";
257                     return false;
258                 }
259                 break;
260             }
261             case SBL_REAL:
262             {
263                 double num;
264                 if(!(input >> num))
265                     cerr << "Error : failed in parsing input into double.";
266                 break;
267             }
268             case SBL_WRD:
269             {
270                 if(!input.get(left))
271                     return false;
272                 if(!isalpha(left))
273                     return false;
274                 break;
275             }
276             case SBL_SLASH:
277             {
278                 if(!input.get(left))
279                     return false;
280                 if(left != ‘\\‘)
281                     return false;
282                 break;
283             }
284             default:
285                 cerr << "Error : simbol expected.";
286                 return false;
287         }
288     }
289 };
290 #endif

Checker c;
string input,pattern;
while (cin)
{
    cout << endl;
    cin >> input;
    cin >> pattern;
    cout << c.isMatch(input , pattern);
}