題目： 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";
    }
}