[UVA] 171 Car Trialling

這一題是很典型的語法分析題目。由於此題只需要判別句型是否合文法，最簡單的作法就是依照文法的優先序，不斷把token們組合成更高level的token。最後檢查是不是只剩一個類型為"instruction"的token即可。舉例來說：

//  組合結果     (粗體為token，細體為普通字符, ___ 為待組合tokens，// 文法)           

GO FIRST RIGHT AT "SMITH ST." AND CAS TO 20 KMH 

=> GO FIRST RIGHT AT sign AND CAS TO 20 KMH    

=> GO FIRST RIGHT AT sign AND CAS TO nnn KMH    // CAS -> cas

=> GO FIRST RIGHT AT sign AND cas TO nnn KMH    // cas TO nnn KMH -> change

=> GO FIRST RIGHT AT sign AND change            // AT sign -> where

=> GO FIRST RIGHT where AND change              // change -> time-keeping

=> GO FIRST RIGHT where AND time-keeping         

=> GO when RIGHT where AND time-keeping

=> GO when direction where AND time-keeping     // GO when -> how

=> how direction where AND time-keeping     // how direction where -> directional

=> directional AND time-keeping            

=> navigational AND time-keeping  // navigational AND time-keeping -> instruction

=> instruction

如此一來，題目就變成字串匹配及取代的問題。每次從文法庫中，選一個最優先的文法。從字串中尋找一組符合文法的tokens( -> 的左邊)組，找到的話該刪除該tokens 組，並插入新的token (->的右邊)。文法的優先性從下到上，即從 nnn 跟signwords做到instruction。有recursive定義的文法可以拆成兩組取代:

navigational = directional  navigational AND THEN directional

可以變為：

direction -> navigational

navigation AND THEN navigational -> navigational

有分崎的文法 :

instruction = navigational  time-keeping  navigational AND time-keeping

要先做

navigational AND time-keeping -> instruction

再做

time-keep -> instruction

跟

navigational -> instruction

可以自己想想看。

這一題讓我吃了史無前例的七個WA。最主要的原因又是不小心看題目：

"There will be one or more spaces between items except before a period (.), after the opening speech marks or before the closing speech marks."

要ok, 也就是說要特別check 

1. ""裡面不能是空的

2. 左"後不能直接空白

3. 右"後不能是空白

4. period " . " 前不能是空白

非常靠盃。

如果你還是WA，那麼這個從UVA forum偷來的test case 可能可以幫到你。t2.out是sample output.

May the AC be with you.