TopCoder SRM 628, Division 2, Level 2 : BracketExpressions

問題文

　http://community.topcoder.com/stat?c=problem_statement&pm=13243&rd=16009

問題概要

　"(){}[]" に含まれる 6 種類の括弧及び 'X' からなる文字列 が与えられる。'X' を括弧の内任意の一文字に（独立に）置換できるとき、括弧の対応を取ることができるか？
　 に含まれる 'X' の数は高々 5 である。

解法

　'X' の数が高々 5 と少ないので、'X' の置換を全通り試すことができます。括弧からなる文字列の括弧の対応は、スタックを用いることで（文字列長の）線形時間で調べられるので、この方法で間に合います。

コード

#define FOR( e, c ) for ( auto &e : c )

const string brackets = "(){}[]";

class BracketExpressions
{
public:
	string ifPossible(string expression)
	{
		return dfs( expression, 0 ) ? "possible" : "impossible";
	}

	bool dfs( string expression, const int p )
	{
		const int L = expression.size();

		if ( L <= p )
		{
			return valid( expression );
		}

		if ( expression[p] != 'X' )
		{
			return dfs( expression, p + 1 );
		}

		FOR( b, brackets )
		{
			expression[p] = b;
			if ( dfs( expression, p + 1 ) )
			{
				return true;
			}
		}
		return false;
	}

	bool valid( const string &s )
	{
		static map<char,char> bpair = {
			{ ')', '(' },
			{ '}', '{' },
			{ ']', '[' }
		};
		stack<char> stk;

		FOR( c, s )
		{
			switch ( c )
			{
				case '(':
				case '{':
				case '[':
					stk.push( c );
					break;
				default:
					if ( stk.empty() || stk.top() != bpair[ c ] )
					{
						return false;
					}
					stk.pop();
					break;
			}
		}
		return stk.empty();
	}
};