这道题用C语言怎么写，真是难倒我了

justcoding

今天参加某司的笔试，要求用C语言实现下面这道题：
把数据读入比较字符串string[],然后读入一个模式字符串，要求查找string[]中和模式字符串的所有匹配，输出行号、匹配字符串。匹配时不区分大小写，并且可以有一个用中括号表示的模式匹配。如"aa[123]bb", 就是说aa1bb, aa2bb, aa3bb都算匹配。
以下是实例，输入格式如下
4    //要输入的比较字符串行数
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. };

复制代码

或者用自动状态机吧

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


    这个东西, 如果用正则库确实不难. 如果不用正则库, 就相当于自己写正则库中的部分实现了.
    考虑到是一个题目的话, 实际上应该是看楼主知不知道正则库这回事了... 搜索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