kmjp's blog

競技プログラミング参加記です

KUPC2015 : F - 逆ポーランド記法

これは割とすぐ解けた。
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;
	
}

まとめ

面白かったです。