ACM: 134 - Loglan-A Logical Language

這題要用給定的文法規則，去檢查輸入的句子是否符合文法。我直接暴力的遞迴...

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;
}