句子的語法匹配。這個用DFA確實可以很方便做出來，用遞歸判斷之類的應(yīng)該也可以。
感覺用dfa只需要保證狀態(tài)轉(zhuǎn)換圖對了，基本上就不會出bug了，但是其它的方法去匹配
這種類似正則表達式的字符串就容易出錯多了。
百度百科的DFA定義如下：
英文全稱：Deterministic Finite Automaton, 簡寫：DFA
DFA定義：一個確定的有窮自動機（DFA）M是一個五元組：M=（K，Σ，f，S，Z）其中
① K是一個有窮集，它的每個元素稱為一個狀態(tài)；
② Σ是一個有窮字母表，它的每個元素稱為一個輸入符號，所以也稱Σ為輸入符號字母表；
③ f是轉(zhuǎn)換函數(shù)，是K×Σ→K上的映射，即，如 f（ki，a）=kj，（ki∈K，kj∈K）就意味著，
當(dāng)前狀態(tài)為ki，輸入符為a時，將轉(zhuǎn)換為下一個狀態(tài)kj，我們把kj稱作ki的一個后繼狀態(tài)；
④ S ∈ K是唯一的一個初態(tài)；
⑤ Z⊂K是一個終態(tài)集，終態(tài)也稱可接受狀態(tài)或結(jié)束狀態(tài)。
該題的狀態(tài)轉(zhuǎn)換圖：
現(xiàn)在再根據(jù)狀態(tài)轉(zhuǎn)換圖，寫一個模擬轉(zhuǎn)換關(guān)系的匹配就非常方便了。。。
代碼如下：
#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)
{
//printf("nState:%d, str:%s\n", nState, vs[i].c_str());
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;
}