2109 - Ancient Expression

問題

略

解法

文字列を引数とした再帰による構文解析を実装するのが楽。
優先順位が低い方から文字列を見る（同じ優先順位なら同時）（左結合なら右から、右結合なら左から）。
全体が括弧でくくられる式が来たら括弧をはずす。

ソース

vector<vector<char> > g;
vector<bool> type;           // 0:L 1:R

string parse(const string &s) {
  REP(i, g.size()) {
    int start = 0, end = s.size(), d = 1;
    if (type[i]==0) start = s.size()-1, end = 0, d = -1;
    int a = 0;
    for (int j=start; j!=end; j+=d) {
      if (s[j] == '(') a++;
      else if(s[j] == ')') a--;
      else if (a==0) {
        FOR(it, g[i]) {
          if (s[j] == *it)
            return "("+ parse(s.substr(0,j)) + string(1,*it) + parse(s.substr(j+1)) + ")";
        }
      }
    }
  }
  if (s[0] == '(') {
    return parse(s.substr(1,s.size()-2));
  }
  return s;
}

int main() {
  int T;
  cin >> T;

  REP(t,T) {
    if (t) cout << endl;
    int G;cin >> G;
    g.clear();
    type.clear();
    REP(i,G) {
      char A; cin >> A;
      int M; cin >> M;
      type.push_back(A=='R');
      vector<char> tmp(M);
      REP(j,M) cin>>tmp[j];
      g.push_back(tmp);
    }
    int n;cin >> n;
    REP(i,n) {
      string e;
      cin >> e;
      cout << parse(e) << endl;
    }
  }
}