南郵OJ 1436 Brackets


Brackets
時間制限(通常/Java):
1000 MS/3000 MS運転メモリ制限:65536 KByte
合計コミット:144テスト合格:35
試合の説明
There are six kinds of brackets: ‘(‘, ‘)’, ‘[‘, ‘]’, ‘{’, ‘}’. dccmx’s girl friend is now learning java programming language, and got mad with brackets! Now give you a string of brackets. Is it valid? For example: “(([{}]))” is valid, but “([)]” is not.
入力
First line contains an integer T (T<=10): the number of test case.
Next T lines, each contains a string: the input expression consists of brackets.
The length of a string is between 1 and 100.
しゅつりょく
For each test case, output “Valid” in one line if the expression is valid, or “Invalid” if not.
サンプル入力
2 {{[[(())]]}} ({[}])
サンプル出力
Valid Invalid
テーマソース
NUPT ACM 2010 Personal Ranking Contest
#include<iostream>
#include<string>
#include<stack>
using namespace std;


bool match(char c1, char c2){
	if('('==c1 && ')'==c2 ||
		'['==c1 && ']'==c2 ||
		'{'==c1 && '}'==c2){
		return 1;
	}
	return 0;
}
int main(){
	int n,i,len;
	string s;
	stack<char> cStack;
	cin>>n;
	while(n--){
		while(!cStack.empty()){
			cStack.pop();
		}
		cin>>s;
		len = s.length();
		for(i=0; i<len; i++){
			if('('==s[i] || '['==s[i] || '{'==s[i]){
				cStack.push(s[i]);
			}else if(')'==s[i] || ']'==s[i] || '}'==s[i]){
				if(!cStack.empty() && match(cStack.top(),s[i]) ){
					cStack.pop();
				}else{
					break;
				}
			}
		}
		if(i>=len && cStack.empty()){
			cout<<"Valid"<<endl;
		}else{
			cout<<"Invalid"<<endl;
		}
	}
}