土下座しながら探索中

主に競技プログラミング

AOJ 2067 : Reading Brackets in English

AOJ 動的計画法 構文解析 CKY法

問題リンク : Reading Brackets in English | Aizu Online Judge

問題概要 :
S-expression は次のように定義される
1. a list of A は (A) に変換され、
2. a list of A and B は (A B) に変換され、
3. a list of A, B, C, ...,Y and Z は (A B C ... Z) に変換される
A,B,...Zは１０文字以下の大文字の文字列か、1., 2., 3., のいずれか
入力として与えられたS-expressionを変換しようとした際に、その解釈が一意に定まるならその結果を出力し、複数通りの解釈存在するなら"AMBIGUOUS"と出力せよ

一意に定まる例 :
入力 : a list of A, B, C and D
出力 : (A B C D)

一意に定まらない例 :
入力 : a list of a list of A and B
出力 : AMBIGUOUS
( (A) B) ともとれるし、( (A B))ともとれるため

解法 :
(解説を読んで)CYK法で解いた O(n^3)
O(n)で解く解法もあるらしい

"a list of" は冗長なので list に変換し、 "," は必要ないので削除する
まず、問題文で定義されてあるS-expressionをBNFで書いてみる
開始記号 S
L ::= "list"
A ::= "and"
T ::= "A" | "B" | ... (英大文字からなる長さ１０以下の文字列)
S ::= L E | L P
E ::= T | S
P ::= E A E | E P

これをチョムスキー標準形に変換する
L ::= "list"
A ::= "and"
T ::= "A" | "B" | ... (英大文字からなる長さ１０以下の文字列)
S ::= L P
S ::= L T
S ::= L S
P ::= T P
P ::= S P
P ::= T Q
P ::= S Q
Q ::= A T
Q ::= A S
TはBNFのままだが、Tは英大文字からなる長さ１０以下の文字列であれば区別しないのでそのままにしている

これに対してCYK法で答えを求める
dpの際に各マスで各非終端記号が何個存在するのかを数えたいので、非終端記号に０から順番に番号を割り振る
次のようにdp配列を定義する
dp[y][x][非終端記号の番号] := (x,y) で考えられる番号iの非終端記号の数
これを連鎖行列積と同様のループで値を更新していく
更新が終わったあと、dp[0][n-1][開始記号の番号]には入力から考えられる解釈の数が入っている
（解釈の数をまともに計算するとlong long でもオーバーフローするほど多くなるので、２以上の適当な値を上限としておくこと　最終的に必要な情報は解釈が２以上かどうかだけなので）
この値が２以上なら複数通りの解釈が存在するのでAMGIBUOUSとなる
そうでない場合、経路復元で括弧の位置を求める
経路復元のため、dpと同様の形の配列を用意する
連鎖行列積と同様にどこが中心なのかを覚えておく
それに加えて、どの非終端記号からなのかを覚えておく必要もある
経路復元用の配列の値は上書きされることもあるが、そのような場合はその値は使われないか答えがAMBIGUOUSとなるため問題ない




コード :

#include<bits/stdc++.h>

#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)

using namespace std;

typedef pair<int,int> ii;

const string FAIL = "AMBIGUOUS";
int dp[1000][1000][6]; // dp[][][0] -> the number of L, dp[][][1] -> A, dp[][][2] -> T, dp[][][3] -> S, dp[][][4] -> P, dp[][][5] -> Q
int path[1000][1000][6]; // 2以上の場合は上書きして良い、どうせ使われないから（AMBIGUOUSか使われないか）
int topv[1000][1000][6];
int rigv[1000][1000][6];

/*
  開始記号 S
  L ::= "list"
  A ::= "and"
  T ::= "A" | "B" | ...
  S ::= L E | L P
  E ::= T | S
  P ::= E A E | E P
  
  -> Chomsky  Normal Form
  L ::= "list"
  A ::= "and"
  T ::= "A" | "B" | ... | "Z" <- 本来であれば個別に分けるが、今回各文字に意味がなく、区別する必要がないのでこのままにする
  S ::= L P | L T | L S
  P ::= T P | S P | T Q | S Q
  Q ::= A T | A S 
  
 */

vector<string> alphas;
vector<char> lexer(string context){
  vector<char> vec;
  rep(i,(int)context.size()) if( context[i] == ',' ) context[i] = ' ';
  stringstream ss;
  ss << context;
  string token;
  while( !( ss >> token ).fail() ){
    if( token == "a" || token[0] == 'o' ) continue;
    alphas.push_back("$");
    if( token[0] == 'l' )      vec.push_back('L'); // List
    else if( token[0] == 'a' ) vec.push_back('A'); // And
    else {
      vec.push_back('T'); // Terminal
      alphas.back() = token;
    }
  }
  return vec;
}

inline int getType(char c) { 
  return ( c == 'L' ) ? 0 : ( ( c == 'A' ) ? 1 : ( ( 'A' <= c && c <= 'Z' ) ? 2 : ( ( c == 'S' ) ? 3 : ( ( c == 'P' ) ? 4 : 5  ) ) ) );
}

inline int reduce(int a,int b) {
  if( a == 0 && b == 4 ) return 3; // S ::= L P
  if( a == 0 && b == 2 ) return 3; // S ::= L T
  if( a == 0 && b == 3 ) return 3; // S ::= L S
  if( a == 2 && b == 4 ) return 4; // P ::= T P
  if( a == 3 && b == 4 ) return 4; // P ::= S P
  if( a == 2 && b == 5 ) return 4; // P ::= T Q
  if( a == 3 && b == 5 ) return 4; // P ::= S Q
  if( a == 1 && b == 2 ) return 5; // Q ::= A T
  if( a == 1 && b == 3 ) return 5; // Q ::= A S
  return -1;
}

void dfs(int L,int R,int type,vector<ii> &buf){
  if( L == R ) return;
  if( type == 3 ) buf.push_back(ii(L,R));
  dfs(L,path[L][R][type],topv[L][R][type],buf);
  dfs(path[L][R][type]+1,R,rigv[L][R][type],buf);
}

const int LIMIT = 100;
void compute(string context){
  alphas.clear();
  vector<char> tokens = lexer(context);
  int n = tokens.size();
  rep(i,n) rep(j,n) rep(k,6) dp[i][j][k] = 0;
  rep(i,n) dp[i][i][getType(tokens[i])] = 1;
  for(int l=1;l<n;l++){
    for(int i=0;i+l<n;i++){
      int j = i + l;
      for(int k=i;k<j;k++){
	//dp[i][j] = dp[i][k] + dp[k+1][j]
	rep(tpv,6) if( dp[i][k][tpv] ) {
	  rep(riv,6) if( dp[k+1][j][riv] ) {
	    int response = reduce(tpv,riv);
	    if( response == -1 ) continue; // no such rule
	    dp[i][j][response] += dp[i][k][tpv] * dp[k+1][j][riv];
	    dp[i][j][response] = min(dp[i][j][response],LIMIT);
	    path[i][j][response] = k;
	    topv[i][j][response] = tpv;
	    rigv[i][j][response] = riv;
	  }
	}
      }
    }
  }
  
  assert( dp[0][n-1][3] >= 0LL );
  if( dp[0][n-1][3] > 1LL ) puts(FAIL.c_str());
  else {
    vector<ii> buf;
    dfs(0,n-1,3,buf);
    string answer = "";
    vector<int> pR(n,0),pL(n,0);
    rep(i,(int)buf.size()) ++pR[buf[i].second], ++pL[buf[i].first];
    rep(i,(int)alphas.size()) {
      answer += string(pL[i],'(');
      if( alphas[i] != "$" ) answer += "!"+alphas[i]+"?";
      answer += string(pR[i],')');
    }
    string new_answer = "";
    int p = 0;
    rep(i,(int)answer.size()) {
      if( answer[i] == '(' ) ++p;
      if( answer[i] == ')' ) --p;
      new_answer += answer[i];
      if( answer[i] == ')' || answer[i] == '?' ) {
	if( i+1 < (int)answer.size() && answer[i+1] == ')' ) continue;
	new_answer += " ";
      }
    }
    string new_answer3 = "";
    rep(i,(int)new_answer.size()-1) {
      if( new_answer[i] == '!' || new_answer[i] == '?' ) continue;
      if( i+1 < (int)new_answer.size() && new_answer[i] == '(' && new_answer[i+1] == ' ' ) continue;
      if( i+1 < (int)new_answer.size() && new_answer[i] == ' ' && new_answer[i+1] == ')' ) continue;
      new_answer3 += new_answer[i];
    }
    cout << new_answer3 << endl;
  }
}

int main(){
  /*
  int n = 5;
  for(int l=1;l<n;l++){
    for(int i=0;i+l<n;i++){
      int j = i + l;
      for(int k=i;k<j;k++){
	//dp[i][j] = dp[i][k] + dp[k+1][j]
	 cout << "[" << i << "," << j << "] = [" << i << "][" << k << "][" << k+1 << "][" << j << "]" << endl;
      }
    }
  }
  cout << "final => [" << 0 << "," << n-1 << "]" << endl;
  return 0;
  */
  int T;
  cin >> T;
  cin.ignore();
  while( T-- ) {
    string context;
    getline(cin,context);
    compute(context);
  }
  return 0;
}