hnu 10076 Jimmys Riddles DFA

 句子的語法匹配。這個用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是一個終態集，終態也稱可接受狀態或結束狀態。

   該題的狀態轉換圖：
  
   現在再根據狀態轉換圖，寫一個模擬轉換關系的匹配就非常方便了。。。
   代碼如下：
#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;
}