以下、文字列 \(S\) について、\(\lvert S\rvert\) でその長さを表し、文字列の間の \(+\) は文字列の連結を表すものとします。

カラフル括弧列の帰納的定義

カラフル括弧列の定義より、カラフル括弧列の長さは偶数である必要があります。 長さ \(2\) のカラフル括弧列は明らかに (), [], <> のみです。また、ここで、長さ \(N\) \((N\geq 4)\)の括弧列について次が成り立ちます。

• 長さ \(N-2\) のカラフル括弧列 \(S'\) を (), [], <>のいずれかで挟んだもの、すなわち (+S’+), [+S’+], <+S’+> はいずれもカラフル括弧列である。
• 長さの和が \(N\) であるカラフル括弧列 \(S',T'\) \((\lvert S'\rvert+\lvert T'\rvert=N)\) を連結したもの \(S=S'+T'\) はカラフル括弧列である。

ここで、これがカラフル括弧列の帰納的な定義にもなっていることを示します。 すなわち、任意の長さ \(N\) の括弧列は上のいずれかの形で書けることを示します。
長さ \(N\) のカラフル括弧列 \(T\) について、定義よりその文字列を空文字列にするような操作列が存在します。このとき、最初の \(T\) の \(1\) 文字目を削除する操作が操作列の中に存在し、その操作によって消されたもう \(1\) つの文字が最初の \(T\) において何文字目にあったかで場合分けします。
これが \(N\) 文字目(すなわち \(T\) の末尾) であった時、\(1\) 文字目と \(N\) 文字目を同時に削除できる、特に連続しているということは、それまでに \(2\) 文字目から \((N-1)\) 文字目は操作の繰り返しによってすべて削除されています。よって、\(T\) の \(2\) 文字目から \((N-1)\) 文字目までをとった部分文字列はカラフル括弧列であり、\(1,N\) 文字目も最後の操作によって削除されたことから、上の事実（帰納的定義）の \(1\) つめに該当することがわかります。
次に \(2\leq k<N\) 番目の場合について考えます。このとき、\(i\leq k<j\) であるような整数の組 \((i,j)\) について、操作列の中で元の \(T\) において \(i\) 文字目と \(j\) 文字目の文字が操作で同時に消されることはありません、なぜなら、\(k\) 文字目が残っている限り \(k-1\) 文字目以前と \(k+1\) 文字目以降が \(T\) 内で連続することはなく、\(k\) 文字目自身も \(1\) 文字目と同時に削除されるため該当せず、元の \(1\) 文字目と \(k\) 文字目を削除する操作の後は 元々 \(k\) 文字目以前の文字は \(T\) に存在しなくなるからです。よって、操作列は元の文字列において \(k\) 文字目以前に関するものと \((k+1)\) 文字目以降に関するものに分けることができ、それぞれ別に考えることで、\(T\) の \(1\) 文字目から \(k\) 文字目まで取り出した部分文字列と、\((k+1)\) 文字目から \(N\) 文字目まで取り出した部分文字列はそれぞれカラフル括弧列となっていることがわかります。よって、この場合は上の事実（帰納的定義）の \(2\) つめに該当します。

よって、上記がカラフル括弧列の帰納的な定義となっていることが示されました。
なお、ここで、カラフル括弧列を列挙するとき（種類数を数えるときなど）には、複数のカラフル括弧列への分解方法が一意でないことなどに注意する必要がありますが、今回はカラフル括弧列であるか否かのみが重要なので詳しくは議論しません。

解法

さて、この判定方法はいくつか考えられますが、例えば stack 等のデータ構造を使う次のような方法があります。

与えられた文字列 \(S\) に対して、\(i=1,2,\ldots,\lvert S\rvert\) の順で次のように処理を行います。

• \(S\) の \(i\) 文字目が (, [,< のいずれかならば stack に その文字を(先頭に)追加する。
• そうでないとき、すなわち\(S\) の \(i\) 文字目が ), ],> のいずれかであるとき、stack が空である、あるいはの 先頭が対応する括弧（例えば、] ならば [ ）でない ならば \(S\) はカラフル括弧列ではない。対応する括弧ならば stack の先頭を削除する。

このようにして処理を行ったとき、最後まで処理を行うことができ、かつ最後の時点で stack が空となっていたならば \(S\) はカラフル括弧列であり、そうでないならば \(S\) はカラフル括弧列ではありません。

この判定法の正当性を示すには、カラフル括弧列に対して正常に終了しstack が空となることと、逆にそのようになったとき、カラフル括弧列であることを示せば良いです。
前者については、長さ \(2\) のときは明らかに成り立ち、\(4\) 以上のものについてもカラフル括弧列の帰納的な定義から数学的帰納法を用いて示すことができます。
後者については、最後まで処理できたとき、それぞれ stack から先頭を削除したタイミングについて、その stack からの削除操作を行なった時の文字と、stack から削除された文字が stack に追加された時の文字をペアとして文字列から削除する操作からなる操作列であって、 \(S\) を空文字列にするようなものを構成することができ、よって \(S\) はカラフル括弧列となります。なお、操作列内の順序については、削除時点での stack の要素数について降順になるようにすると、かならず部分文字列の削除操作を行うことができます。

この判定法の計算量は \(O(\lvert S\rvert)\) であり、十分高速です。
よって、この問題を解くことができました。

C++ による解答例:

#include <bits/stdc++.h>
using namespace std;

int main(void){
	int n;
	string s;
	stack<char> st;

	cin>>s;
	n=s.size();
	for(int i=0;i<n;i++){
		if((s[i]=='(')||(s[i]=='[')||(s[i]=='<'))st.push(s[i]);
		else{
			bool flag=false;
			if(st.empty()){
			  cout<<"No"<<endl;
				return 0;
			}
			if((s[i]==')')&&(st.top()!='('))flag=true;
			if((s[i]==']')&&(st.top()!='['))flag=true;
			if((s[i]=='>')&&(st.top()!='<'))flag=true;
			if(flag){
				cout<<"No"<<endl;
				return 0;
			}
			st.pop();
		}
	}
	if(st.empty())cout<<"Yes"<<endl;
	else cout<<"No"<<endl;
}