這題要用給定的文法規則,去檢查輸入的句子是否符合文法。我直接暴力的遞迴...
TIP
雖然題目寫"You can assume that all words will be correctly formed",但實際上加了判斷不和語法的單字才拿到AC。
CODE
#include <iostream> #include <vector> using namespace std; enum { A, MOD, BA, DA, LA, NAM, PREDA }; vector<int> loglan; int n; bool vowel(char c){ return ( c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u' ); } int convert_loglan(string s, int n){ if( !vowel( s[n-1] ) ) return NAM; if( n == 1 ) return A; if( n == 2 ){ switch( s[0] ){ case 'g': return MOD; case 'b': return BA; case 'd': return DA; case 'l': return LA; } } if( n==5 && (( !vowel(s[0]) && !vowel(s[1]) && vowel(s[2]) && !vowel(s[3]) && vowel(s[4]) ) || ( !vowel(s[0]) && vowel(s[1]) && !vowel(s[2]) && !vowel(s[3]) && vowel(s[4]) )) ) return PREDA; return NAM; } bool predstring(int st, int ed){ if( st == ed ) return (loglan[st] == PREDA); //"PREDA" return (loglan[ed] == PREDA && predstring(st, ed-1)); //"<predstring> PREDA" } bool verbpred(int st, int ed){ return (loglan[st] == MOD && predstring(st+1, ed)); //"MOD <predstring>" } bool predname(int st, int ed){ if( st == ed ) return (loglan[st] == NAM); //"NAM" return (loglan[st] == LA && predstring(st+1, ed)); //"LA <predstring>" } bool preds(int st, int ed){ for(int i=st+1; i<ed; ++i){ if( loglan[i] == A ){ return (preds(st, i-1) && preds(i+1, ed)); //"<preds> A <predstring> -> <preds> A <preds>" } } return predstring(st, ed); //"<predstring>" } bool statement(void){ for(int i=1; i<n; ++i){ if( loglan[i] == MOD ){ bool pv = predname(0, i-1) && verbpred(i, n-1); //"<predname><verbpred>" bool pvp = 0; for(int j=i+1; j<n-1; ++j) pvp += (predname(0, i-1) && verbpred(i, j) && predname(j+1, n-1)); //"<predname><verbpred><predname>" return (pvp || pv); } } return 0; } bool predclaim(void){ if( loglan[0] == DA ){ return preds(1, n-1); //"DA <preds>" } for(int i=1; i<n; ++i){ if( loglan[i] == BA ) return (predname(0, i-1) && preds(i+1, n-1)); //"<predname> BA <preds>" } return 0; } bool sentence(void){ return ( statement() || predclaim() ); } int main(){ string s; while( (cin >> s) && (s[0] != '#') ){ int len = s.size(); if( s[len-1] == '.' ){ s.erase(len-1); loglan.push_back( convert_loglan(s, len-1) ); n = loglan.size(); cout << (sentence() ? "Good" : "Bad!") << endl; //initialize loglan.clear(); } else loglan.push_back( convert_loglan(s, len) ); }//while return 0; }
No comments:
Post a Comment