南邮 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;
		}
	}
}