這道題用C語言怎么寫，真是難倒我了

justcoding

今天參加某司的筆試，要求用C語言實現(xiàn)下面這道題：
把數(shù)據(jù)讀入比較字符串string[],然后讀入一個模式字符串，要求查找string[]中和模式字符串的所有匹配，輸出行號、匹配字符串。匹配時不區(qū)分大小寫，并且可以有一個用中括號表示的模式匹配。如"aa[123]bb", 就是說aa1bb, aa2bb, aa3bb都算匹配。
以下是實例，輸入格式如下
4    //要輸入的比較字符串行數(shù)
Aab  //比較字符串
a2B
ab
ABB
a[a2b]b   //模式字符串
輸出如下
1 Aab
2 a2B
4 ABB
其中，1,2,4是輸入時的比較字符串行號

對于這道題，我感覺就是加了中括號里的模式匹配不好解決，沒想到好的辦法，當時想了半天都不知所措，請大家給點意見

MMMIX

回復 1# justcoding


    允許用正則庫么？

MeRcy_PM

如果只有簡單的[]里面沒其他表達式的話，簡單想法直接開一條鏈表記錄整個表達式，碰到[]這種就再建一個子鏈表把可能的值串起來。

1. struct {
   
2.     struct list *next;
   
3.     enum type;
   
4.     union {
   
5.         key;
   
6.         list;
   
7.     }
   
8. };

復制代碼

或者用自動狀態(tài)機吧

bruceteen

隨手寫一個，不知道對不對

1. #include <stdbool.h>
   
2. #include <ctype.h>
   
3. 
   
4. bool match( const char* s, const char* t )
   
5. {
   
6.     for( ; *s && *t; ++s,++t )
   
7.     {
   
8.         if( *t == '[' )
   
9.         {
   
10.             for( ++t; *t && *t!=']' && tolower(*s)!=tolower(*t); ++t );
    
11. 
    
12.             if( *t=='\0' || *t==']' )
    
13.                 return false;
    
14. 
    
15.             for( ; *t && *t!=']'; ++t );
    
16.         }
    
17.         else if( tolower(*s)!=tolower(*t) )
    
18.             return false;
    
19.     }
    
20. 
    
21.     return !*s && !*t;
    
22. }
    
23. 
    
24. #include <stdio.h>
    
25. 
    
26. int main( void )
    
27. {
    
28.     printf( "%s\n", match("Aab","a[a2b]b")?"true":"false" );
    
29.     printf( "%s\n", match("a2B","a[a2b]b")?"true":"false" );
    
30.     printf( "%s\n", match("ab","a[a2b]b")?"true":"false" );
    
31.     printf( "%s\n", match("ABB","a[a2b]b")?"true":"false" );
    
32. }

復制代碼

justcoding

回復 2# MMMIX
這個我倒沒問，而且不是你說我還不知道有正則庫這個東西，汗


   

captivated

回復 5# justcoding


    這個東西, 如果用正則庫確實不難. 如果不用正則庫, 就相當于自己寫正則庫中的部分實現(xiàn)了.
    考慮到是一個題目的話, 實際上應該是看樓主知不知道正則庫這回事了... 搜索C語言正則庫即可...
    如果是要求正則全匹配而且不準用正則庫的話, HoHo, 就相當于寫一個正則庫了, 這工作量... 不然呢, flex 什么的也是一個選擇吧...

captivated

仔細看了下好像是只要求匹配中括號, 那不用正則庫也是可以處理的... 不過確實還是有些麻煩, 粗略寫來估計 bug 不少.

yjh777

fnmatch(3)

yjh777

1. /*
   
2. * Copyright (c) 1989, 1993, 1994
   
3. *        The Regents of the University of California.  All rights reserved.
   
4. *
   
5. * This code is derived from software contributed to Berkeley by
   
6. * Guido van Rossum.
   
7. *
   
8. * Redistribution and use in source and binary forms, with or without
   
9. * modification, are permitted provided that the following conditions
   
10. * are met:
    
11. * 1. Redistributions of source code must retain the above copyright
    
12. *    notice, this list of conditions and the following disclaimer.
    
13. * 2. Redistributions in binary form must reproduce the above copyright
    
14. *    notice, this list of conditions and the following disclaimer in the
    
15. *    documentation and/or other materials provided with the distribution.
    
16. * 3. All advertising materials mentioning features or use of this software
    
17. *    must display the following acknowledgement:
    
18. *        This product includes software developed by the University of
    
19. *        California, Berkeley and its contributors.
    
20. * 4. Neither the name of the University nor the names of its contributors
    
21. *    may be used to endorse or promote products derived from this software
    
22. *    without specific prior written permission.
    
23. *
    
24. * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
    
25. * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
    
26. * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
    
27. * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
    
28. * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
    
29. * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
    
30. * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
    
31. * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
    
32. * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
    
33. * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
    
34. * SUCH DAMAGE.
    
35. *
    
36. * From FreeBSD fnmatch.c 1.11
    
37. * $Id: fnmatch.c,v 1.3 1997/08/19 02:34:30 jdp Exp $
    
38. */
    
39. 
    
40. #if defined(LIBC_SCCS) && !defined(lint)
    
41. static char sccsid[] = "@(#)fnmatch.c        8.2 (Berkeley) 4/16/94";
    
42. #endif /* LIBC_SCCS and not lint */
    
43. 
    
44. /*
    
45. * Function fnmatch() as specified in POSIX 1003.2-1992, section B.6.
    
46. * Compares a filename or pathname to a pattern.
    
47. */
    
48. 
    
49. #include <ctype.h>
    
50. #include <string.h>
    
51. #include <stdio.h>
    
52. 
    
53. #include "fnmatch.h"
    
54. 
    
55. #define        EOS        '\0'
    
56. 
    
57. static const char *rangematch(const char *, char, int);
    
58. 
    
59. int
    
60. fnmatch(const char *pattern, const char *string, int flags)
    
61. {
    
62.         const char *stringstart;
    
63.         char c, test;
    
64. 
    
65.         for (stringstart = string;;)
    
66.                 switch (c = *pattern++) {
    
67.                 case EOS:
    
68.                         if ((flags & FNM_LEADING_DIR) && *string == '/')
    
69.                                 return (0);
    
70.                         return (*string == EOS ? 0 : FNM_NOMATCH);
    
71.                 case '?':
    
72.                         if (*string == EOS)
    
73.                                 return (FNM_NOMATCH);
    
74.                         if (*string == '/' && (flags & FNM_PATHNAME))
    
75.                                 return (FNM_NOMATCH);
    
76.                         if (*string == '.' && (flags & FNM_PERIOD) &&
    
77.                             (string == stringstart ||
    
78.                             ((flags & FNM_PATHNAME) && *(string - 1) == '/')))
    
79.                                 return (FNM_NOMATCH);
    
80.                         ++string;
    
81.                         break;
    
82.                 case '*':
    
83.                         c = *pattern;
    
84.                         /* Collapse multiple stars. */
    
85.                         while (c == '*')
    
86.                                 c = *++pattern;
    
87. 
    
88.                         if (*string == '.' && (flags & FNM_PERIOD) &&
    
89.                             (string == stringstart ||
    
90.                             ((flags & FNM_PATHNAME) && *(string - 1) == '/')))
    
91.                                 return (FNM_NOMATCH);
    
92. 
    
93.                         /* Optimize for pattern with * at end or before /. */
    
94.                         if (c == EOS)
    
95.                                 if (flags & FNM_PATHNAME)
    
96.                                         return ((flags & FNM_LEADING_DIR) ||
    
97.                                             strchr(string, '/') == NULL ?
    
98.                                             0 : FNM_NOMATCH);
    
99.                                 else
    
100.                                         return (0);
     
101.                         else if (c == '/' && flags & FNM_PATHNAME) {
     
102.                                 if ((string = strchr(string, '/')) == NULL)
     
103.                                         return (FNM_NOMATCH);
     
104.                                 break;
     
105.                         }
     
106. 
     
107.                         /* General case, use recursion. */
     
108.                         while ((test = *string) != EOS) {
     
109.                                 if (!fnmatch(pattern, string, flags & ~FNM_PERIOD))
     
110.                                         return (0);
     
111.                                 if (test == '/' && flags & FNM_PATHNAME)
     
112.                                         break;
     
113.                                 ++string;
     
114.                         }
     
115.                         return (FNM_NOMATCH);
     
116.                 case '[':
     
117.                         if (*string == EOS)
     
118.                                 return (FNM_NOMATCH);
     
119.                         if (*string == '/' && flags & FNM_PATHNAME)
     
120.                                 return (FNM_NOMATCH);
     
121.                         if ((pattern =
     
122.                             rangematch(pattern, *string, flags)) == NULL)
     
123.                                 return (FNM_NOMATCH);
     
124.                         ++string;
     
125.                         break;
     
126.                 case '\\':
     
127.                         if (!(flags & FNM_NOESCAPE)) {
     
128.                                 if ((c = *pattern++) == EOS) {
     
129.                                         c = '\\';
     
130.                                         --pattern;
     
131.                                 }
     
132.                         }
     
133.                         /* FALLTHROUGH */
     
134.                 default:
     
135.                         if (c == *string)
     
136.                                 ;
     
137.                         else if ((flags & FNM_CASEFOLD) &&
     
138.                                  (tolower((unsigned char)c) ==
     
139.                                   tolower((unsigned char)*string)))
     
140.                                 ;
     
141.                         else if ((flags & FNM_PREFIX_DIRS) && *string == EOS &&
     
142.                              ((c == '/' && string != stringstart) ||
     
143.                              (string == stringstart+1 && *stringstart == '/')))
     
144.                                 return (0);
     
145.                         else
     
146.                                 return (FNM_NOMATCH);
     
147.                         string++;
     
148.                         break;
     
149.                 }
     
150.         /* NOTREACHED */
     
151. }
     
152. 
     
153. static const char *
     
154. rangematch(const char *pattern, char test, int flags)
     
155. {
     
156.         int negate, ok;
     
157.         char c, c2;
     
158. 
     
159.         /*
     
160.          * A bracket expression starting with an unquoted circumflex
     
161.          * character produces unspecified results (IEEE 1003.2-1992,
     
162.          * 3.13.2).  This implementation treats it like '!', for
     
163.          * consistency with the regular expression syntax.
     
164.          * J.T. Conklin (conklin@ngai.kaleida.com)
     
165.          */
     
166.         if ( (negate = (*pattern == '!' || *pattern == '^')) )
     
167.                 ++pattern;
     
168. 
     
169.         if (flags & FNM_CASEFOLD)
     
170.                 test = tolower((unsigned char)test);
     
171. 
     
172.         for (ok = 0; (c = *pattern++) != ']';) {
     
173.                 if (c == '\\' && !(flags & FNM_NOESCAPE))
     
174.                         c = *pattern++;
     
175.                 if (c == EOS)
     
176.                         return (NULL);
     
177. 
     
178.                 if (flags & FNM_CASEFOLD)
     
179.                         c = tolower((unsigned char)c);
     
180. 
     
181.                 if (*pattern == '-'
     
182.                     && (c2 = *(pattern+1)) != EOS && c2 != ']') {
     
183.                         pattern += 2;
     
184.                         if (c2 == '\\' && !(flags & FNM_NOESCAPE))
     
185.                                 c2 = *pattern++;
     
186.                         if (c2 == EOS)
     
187.                                 return (NULL);
     
188. 
     
189.                         if (flags & FNM_CASEFOLD)
     
190.                                 c2 = tolower((unsigned char)c2);
     
191. 
     
192.                         if ((unsigned char)c <= (unsigned char)test &&
     
193.                             (unsigned char)test <= (unsigned char)c2)
     
194.                                 ok = 1;
     
195.                 } else if (c == test)
     
196.                         ok = 1;
     
197.         }
     
198.         return (ok == negate ? NULL : pattern);
     
199. }

復制代碼

http://web.mit.edu/freebsd/csup/fnmatch.c