題目: UVa - 673 - Parentheses Balance
題目說明
給一個只包含括弧的字串 ('('
、')'
、'['
、']'
),成對的相鄰括弧可以相互消除,如:
“([()
])()” -> “([[]
()])()” -> “([()
])()” -> “([]
)()” -> “()
()” -> “()
“ -> “”
若消除後的字串為空或原本就為空字串則輸出 "Yes"
,否則輸出 "No"
。
解題思路
基本的 Stack 觀念,使用 Stack 模擬操作即可。
參考解法
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52
| #include <iostream> #include <string> #include <stack>
using namespace std;
static auto __ = [] { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); return 0; }();
string str;
bool solve() { stack<char> s;
for (auto& ch : str) switch (ch) { case ')': if (s.empty() || s.top() != '(') return false; s.pop(); break;
case ']': if (s.empty() || s.top() != '[') return false; s.pop(); break;
default: s.push(ch); break; }
return s.empty(); }
int main() { int T; cin >> T; cin.ignore(); while (T--) { getline(cin, str); if (solve()) cout << "Yes\n"; else cout << "No\n"; } }
|