TopCoder SRM 628 Div2 Medium BracketExpressions

Div2 Mediumの割にちょっと面倒な問題。
http://community.topcoder.com/stat?c=problem_statement&pm=13243

問題

"(){}"で構成された文字列のうち、開きかっこと閉じかっこの対応が取れているものを有効な文字列とする。
(厳密な定義は問題文参照)

ここで"(){}"及び"X"で構成された文字列が与えられる。
"X"は"()[]{}"のいずれかと置換できるとき、文字列を有効な文字列に出来るか。

解法

有効文字列の判定はスタックを使うと文字列長Lに対しO(L)で出来る。
今回の問題ではXは最大5個なので、Xの埋め方はたった6^5通り。
よってXを総当たりで埋め、有効性を判定すればよい。

class BracketExpressions {
	public:
	int L;
	string S,S2;
	
	bool check() {
		stack<char> ST;
		ITR(it,S2) {
			char ch=ST.empty()?'*':ST.top();
			if((ch=='(' && *it==')') || (ch=='[' && *it==']') || (ch=='{' && *it=='}')) ST.pop();
			else ST.push(*it);
		}
		return ST.empty();
		
	}
	
	bool dfs(int cur) {
		if(cur==L) return check();
		if(S[cur]=='X') {
			bool ret=false;
			string s="()[]{}";
			ITR(it,s) S2[cur]=*it, ret |= dfs(cur+1);
			return ret;
		}
		else return dfs(cur+1);
	}
	
	string ifPossible(string expression) {
		S=S2=expression;
		L=S.size();
		return dfs(0)?"possible":"impossible";
	}
}

まとめ

なんかDiv1 Mediumと言い今回文字列解析多いな。