これは割とすぐ解けた。
http://kupc2015.contest.atcoder.jp/tasks/kupc2015_f
問題
逆ポーランド記法で書かれた数式が与えられる。
ここで、逆ポーランド記法では通常スタックを使い式を計算していくが、代わりにキューを使う場合を考える。
元の数式を並べ替え、キューで計算しても同じ結果が出るようにせよ。
解法
まず1回逆ポーランド記法を素直に計算し、各演算子ではどの値をどの値を処理するかを洗い出す。
例えば(中置記法で)A-Bという数式があったとする。(A,Bも何かしらの式とする。)
逆ポーランド記法ならAB-の順となる。
しかしキューを使った場合はキューがBAの状態で-が適用される。
ここでA=C*Dの形だったとする。
するとキューがBAになる前はDCBだったことになる。
ここでB=E+Fの形ならば、直前のキューはFEDCとなる。
同様に考えていくと、キューの末尾がある演算の結果である場合、演算の元となる2値を先頭に追加する、ということを演算子がなくなるまで繰り返せばよい。
考え方としては、最終的な値から、演算を巻き戻していくイメージ。
式の数値及び演算子の登場順は、上記処理の逆順である。
int N; string A; int L[101]; int R[101]; void solve() { int i,j,k,l,r,x,y; string s; cin>>A; N=A.size(); stack<int> S; FOR(i,N) { if(!isdigit(A[i])) { R[i]=S.top(); S.pop(); L[i]=S.top(); S.pop(); } S.push(i); } queue<int> Q; Q.push(S.top()); while(Q.size()) { x=Q.front(); Q.pop(); s+=A[x]; if(!isdigit(A[x])) { Q.push(L[x]); Q.push(R[x]); } } reverse(ALL(s)); cout<<s<<endl; }
まとめ
面白かったです。