句子的语法匹配。这个用DFA确实可以很方便做出来，用递归判断之类的应该也可以。感觉用dfa只需要保证状态转换图对了，基本上就不会出bug了，但是其它的方法去匹配这种类似正则表达式的字符串就容易出错多了。
百度百科的DFA定义如下：
英文全称：Deterministic Finite Automaton, 简写：DFA
DFA定义：一个确定的有穷自动机（DFA）M是一个五元组：M=（K，Σ，f，S，Z）其中
① K是一个有穷集，它的每个元素称为一个状态；
② Σ是一个有穷字母表，它的每个元素称为一个输入符号，所以也称Σ为输入符号字母表；
③ f是转换函数，是K×Σ→K上的映射，即，如 f（ki，a）=kj，（ki∈K，kj∈K）就意味着，
当前状态为ki，输入符为a时，将转换为下一个状态kj，我们把kj称作ki的一个后继状态；
④ S ∈ K是唯一的一个初态；
⑤ Z⊂K是一个终态集，终态也称可接受状态或结束状态。
该题的状态转换图：
![]()
现在再根据状态转换图，写一个模拟转换关系的匹配就非常方便了。。。
代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
| #include <string>
#include <vector>
#include <sstream>
#include <iostream>
#include <algorithm>
using namespace std;
string strNouns[8] =
{
"tom", "jerry", "goofy", "mickey",
"jimmy", "dog", "cat", "mouse"
};
bool IsNoun(string str)
{
for (int i = 0; i < 8; ++i)
{
if (str == strNouns[i])
{
return true;
}
}
return false;
}
bool IsVerb(string str)
{
return str == "hate" || str == "love"
|| str == "know" || str == "like"
|| str == "hates" || str == "loves"
|| str == "knows" || str == "likes";
}
bool IsArticle(string str)
{
return str == "a" || str == "the";
}
bool CheckState(vector<string> vs)
{
if (vs.empty()) return false;
int nState = 0;
for (int i = 0; i < vs.size(); ++i)
{
switch (nState)
{
case 0:
if (IsArticle(vs[i]))
{
nState = 1;
break;
}
else if (IsNoun(vs[i]))
{
nState = 2;
break;
}
else
{
return false;
}
case 1:
if (IsNoun(vs[i]))
{
nState = 2;
break;
}
else
{
return false;
}
case 2:
if (vs[i] == "and")
{
nState = 0;
break;
}
else if (IsVerb(vs[i]))
{
nState = 3;
break;
}
else
{
return false;
}
case 3:
if (IsArticle(vs[i]))
{
nState = 4;
break;
}
else if (IsNoun(vs[i]))
{
nState = 5;
break;
}
else
{
return false;
}
case 4:
if (IsNoun(vs[i]))
{
nState = 5;
break;
}
else
{
return false;
}
case 5:
if (vs[i] == "and")
{
nState = 3;
break;
}
else if (vs[i] == ",")
{
nState = 0;
break;
}
else
{
return false;
}
}
}
return nState == 5;
}
int main()
{
int nT;
scanf("%d%*c", &nT);
while (nT--)
{
vector<string> vs;
string line, str;
getline(cin, line);
stringstream ss(line);
while (ss >> str)
{
vs.push_back(str);
}
printf("%s\n", CheckState(vs) ? "YES I WILL" : "NO I WON'T");
}
return 0;
}
|
