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
解法1:
一个简单应用栈的题目,只要不要拉下可能的情况;
1 #include <iostream>
2 #include <stdio.h>
3 #include <stdlib.h>
4 #include <iomanip>
5 #include <stack>
6 #include <string.h>
7
8 using namespace std ;
9
10 int PD(char a)
11 {
12 int t;
13 if(a == '[')
14 t = 1;
15 if(a == ']')
16 t = -1;
17 if(a == '(')
18 t = 2;
19 if(a == ')')
20 t = -2;
21 return t;
22 }
23
24 int main()
25 {
26 int n;
27 char a[200];
28 char b[100];
29 cin>>n;
30 gets(b);
31 for(int i = 1;i <= n;i++)
32 {
33 int temp = 1;
34 int len;
35 stack <int >s;
36 gets(a);
37 len = strlen(a) ;
38
39 for(int i = 0;i < len ;i++)
40 {
41 if(a[i] == '(' || a[i] == '[') //左括号都保存
42 s.push( PD(a[i]) );
43 if(a[i] == ')' || a[i] == ']') //右括号分情况判断
44 {
45 if( s.empty() ) {temp = 0;break;}
46 else if( s.top() + PD(a[i]) == 0) { s.pop();}
47 else if( s.top() + PD(a[i]) != 0) { temp = 0;break;}
48 }
49 }
50
51 if(temp == 0 || !s.empty()) cout<<"No"<<endl; //不要拉下可能的情况
52 else if( s.empty()) cout<<"Yes"<<endl;
53
54 }
55
56
57 return 0;
58 }