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
题目大意:确定括号是否匹配。
注意:空语句输出Yes
解题思路:左括号入栈,右括号匹配出栈。
#include<string.h> #include<stack> #include<cstdio> using namespace std; #define N 200 int main() { int n; char str[N]; int bo; scanf("%d", &n); getchar(); while(n--) { // Init. memset(str, 0, sizeof(str)); bo = 1; stack<char> q; // Read. gets(str); int m = strlen(str); for(int i = 0; i < m ; i++) { if(str[i] == '(' || str[i] == '[') q.push(str[i]); else if(str[i] == ')') { if(q.empty() || q.top() != '(') { bo = 0; break; } else q.pop(); } else if(str[i] == ']') { if(q.empty() || q.top() != '[') { bo = 0; break; } else q.pop(); } } if(bo && q.empty()) printf("Yes\n"); else printf("No\n"); } return 0;}