南郵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
時間制限(通常/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;
}
}
}