題干：

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.

Input

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.

Output

For each test case, output “Valid” in one line if the expression is valid, or “Invalid” if not.

Sample Input

2?
{{[[(())]]}}?
({[}])

Sample Output

Valid?
Invalid

解題報告：

? ? 水題模擬不解釋。就是找到關鍵元素在于，對于第一個出現的右括號，與之相鄰的一定是左括號，抓住這一點，程序很好寫了。

AC代碼：

#include<bits/stdc++.h> #define ll long long using namespace std; bool iszuo(char ch) {return ch=='(' || ch=='[' || ch=='{'; } bool isyou(char ch) {return ch==')' || ch==']' || ch=='}'; } char s[1005]; int main() {int t;cin>>t;getchar();while(t--) {stack<char> sk;//getline(cin,s);cin.getline(s,1005);int len = strlen(s);int flag = 1;for(int i = 0; i<len; i++) {if(iszuo(s[i])) sk.push(s[i]);else {if(sk.empty()) {flag=0;break;}if(s[i] ==')') {if(sk.top() != '(') {flag=0;break;}}else if(s[i] == ']') {if(sk.top() != '[') {flag=0;break;}}else {if(sk.top() != '{') {flag=0;break;}}sk.pop();}}if(flag && sk.empty()) puts("Valid");else puts("Invalid");}return 0; }

總結：

? ?雖然是一道水題但是還是有很多值得總結的地方。比如要時刻看看是否棧為空，包括最后輸出的地方，因為棧不空時，顯然是invalid的情況！

? ?還有就是因為整個就在用sk.top()和s[i]這兩個值，所以別用錯了，比如有個地方的sk.top()我就寫成了s[i]

總結

以上是生活随笔為你收集整理的【HRBUST - 1054 】Brackets! Brackets! （括号匹配，思维，STL栈）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。