alan23273850 的刷題筆記
b304: 00673 - Parentheses Balance
Tags: parenthesis-matching, stack
出處：https://zerojudge.tw/ShowProblem?problemid=b304
提交：https://zerojudge.tw/Submissions?problemid=b304&account=allllllan123456
問題：給定一個長度不到 130 的字串，只包含 ( ) [ ] 四種字元，請問該字串是否滿足括號匹配條件 [1]。
解法：這題是典型的括號匹配問題，用 stack 模擬即可。遇右括號時立刻檢驗是否有對應的左括號，沒有則匹配失敗，最後如果有多餘的左括號也算是匹配失敗。這題因為空字串也算是匹配成功所以輸入方法要使用 getline。
附註：
[1] 滿足括號匹配的條件有三種：空字串本就滿足括號匹配、滿足括號匹配的字串外圍被 ( ) 或 [ ] 包住之後亦滿足括號匹配、兩個滿足括號匹配的字串連接起來亦滿足括號匹配。
1#include <bits/stdc++.h>
2using namespace std;
3
4int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); // IO 優化
5 string str; int T; cin >> T >> ws; // ws 負責吃掉整數後面的換行
6 while (T--) {
7 getline(cin, str); // 選擇用 getline 讀字串是因為怕測資有空字串
8 stack<char> mystack; bool fail = false;
9 for (int i=0; i<str.length() && !fail; i++) {
10 if (str[i]=='[' || str[i]=='(')
11 mystack.push(str[i]);
12 else if (str[i]==']' && !mystack.empty() && mystack.top()=='[' ||
13 str[i]==')' && !mystack.empty() && mystack.top()=='(')
14 mystack.pop();
15 else fail = true;
16 }
17 fail |= !mystack.empty();
18 cout << (fail ? "No\n" : "Yes\n");
19 }
20 return 0;
21}