AOJ 2584 Broken Cipher Generator
問題ページ
Broken Cipher Generator | Aizu Online Judge
考えたこと
- 明らかに構文解析でBNFまで書いてあるので実装をしようとする。
- BNFをよく見ると
が左再帰なのでそのままは書けない。 - ググって左再帰の除去を調べると
= | empty とすればよさそう。 - emptyの判定どうするのかわからないが
- '['なら+1、']'なら-1とかして[]の中かどうかの判定をしようとする
→ [AA[A]A] とかで真ん中の括弧の判定が面倒
----解説を見る----
']'を指しているかどうか、idx < s.size()かどうかを見ればempty判定できる。言われてみれば当たり前。
#define __USE_MINGW_ANSI_STDIO 0 #include <bits/stdc++.h> using namespace std; typedef long long ll; #define int ll typedef vector<int> VI; typedef vector<VI> VVI; typedef vector<ll> VL; typedef vector<VL> VVL; typedef pair<int, int> PII; #define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i) #define REP(i, n) FOR(i, 0, n) #define ALL(x) x.begin(), x.end() #define IN(a, b, x) (a<=x&&x<b) #define MP make_pair #define PB push_back #ifdef int const ll INF = (1LL<<60); #else const int INF = (1LL<<30); #endif const double PI = 3.14159265359; const double EPS = 1e-12; const int MOD = 1000000007; template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); } template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); } template<class S,class T> ostream &operator <<(ostream& out,const pair<S,T>& a){ out<<'('<<a.first<<','<<a.second<<')'; return out; } int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0}; typedef string::const_iterator State; string str(State&); char letter(State&); string s; string cipher(State& begin) { // cout << "c:" << *begin << endl; string ret = ""; while(begin != s.end() && *begin != ']') { ret += str(begin); // cout << ret << endl; } return ret; } string str(State& begin) { // cout << "s:" << *begin << endl; string ret; if(*begin == '[') { begin++; ret = cipher(begin); begin++; reverse(ALL(ret)); } else { ret = letter(begin); } return ret; } char letter(State& begin) { // cout << "l:" << *begin << endl; int tmp = 0; while(*begin == '+' || *begin == '-') { if(*begin == '+') tmp++; else tmp--; begin++; } char ret = *begin; begin++; if(ret == '?') return 'A'; while(tmp > 0) ret = ret=='Z'?'A':ret+1, tmp--; while(tmp < 0) ret = ret=='A'?'Z':ret-1, tmp++; return ret; } signed main(void) { while(true) { cin >> s; if(s == ".") break; State begin = s.begin(); cout << cipher(begin) << endl; } return 0; }