| Parentheses Balance |
You are given a string consisting of parentheses () and []. A string of this type is said to be correct:
- (a)
- if it is the empty string
- (b)
- if A and B are correct, AB is correct,
- (c)
- if A is correct, (A) and [A] is correct.
Write a program that takes a sequence of strings of this type and check their correctness. Your program can assume that the maximum string length is 128.
Input
The file contains a positive integer n and a sequence of n strings of parentheses () and [], one string a line.
Output
A sequence of Yes or No on the output file.
Sample Input
3 ([]) (([()]))) ([()[]()])()
Sample Output
Yes No Yes
Miguel Revilla
2000-08-14
括号匹配问题，就是摸拟一个栈的操作：‘(’和‘[’相当于入栈操作，‘)’和‘]’相当于出栈操作
注意处理完一行之后栈必需为空才能输出Yes
1 #include<iostream> 2 #include<cstdio> 3 4 using namespace std; 5 6 int main() 7 { 8 int kase; 9 10 scanf("%d",&kase); 11 getchar(); 12 13 while(kase--) 14 { 15 int f=0; 16 char s[150],Stack[150]; 17 bool finished=false,yes=true; 18 19 gets(s); 20 21 for(int i=0;(!finished)&&s[i]!=‘\0‘;i++) 22 { 23 switch(s[i]) 24 { 25 case ‘(‘:Stack[f++]=‘(‘;break; 26 case ‘[‘:Stack[f++]=‘[‘;break; 27 case ‘)‘:if(f>0&&Stack[f-1]==‘(‘) 28 f--; 29 else 30 { 31 finished=true; 32 yes=false; 33 } 34 break; 35 case ‘]‘:if(f>0&&Stack[f-1]==‘[‘) 36 f--; 37 else 38 { 39 finished=true; 40 yes=false; 41 } 42 break; 43 } 44 } 45 46 printf("%s\n",yes&&(f==0)?"Yes":"No"); 47 } 48 49 return 0; 50 }