ZeroJudge E924: 括號配對

題目敘述

每筆測資第一行有一個正整數N，接下來會有N行，每行會有一個字串，字串只會包含 ( )、[ ]、{ }、< > 這四種括號。要求輸出這樣的括號排序能不能配對成功。

範例輸入 #1

4

{()<>}[]

(){

{(})

())

範例輸出 #1

Y

N

N

N

解題思路

如果字串長度為奇數直接輸出N。可以使用Stack的概念做這題，如果跑到的字元是左括號的話就將這個字元Push_Back到一個Vector中，如果跑到一個右括號則判斷Vector中的最後一個資料是否能和這個右括號配對。如果配對成功那就使用Pop_Back將Vector最後一個資料刪除，如果配對失敗就直接輸出N然後Break掉For迴圈。另外判斷的時候也需要注意一下Vector內目前有沒有資料，如果Vector的Size是0的話代表突然有一個右括號出現，直接輸出N然後Break。For迴圈結束後也需要判斷Vector中還有沒有殘留的左括號，如果有的話同樣也是輸出N。

解題程式碼如下 (僅供參考)：

#include <iostream>
#include <map>
#include <vector>
using namespace std;

int main() {
    cin.sync_with_stdio(0);
    cin.tie(0);
    int N;
    cin >> N;
    map<char, char>MAP;
    MAP[')'] = '(';
    MAP[']'] = '[';
    MAP['>'] = '<';
    MAP['}'] = '{';
    for (int i = 0; i<N; i++)
    {
        string str;
        cin >> str;
        if (str.length() % 2 != 0) cout << "N\n";
        else
        {
            vector<char>v;
            bool ok = true;
            for (int j = 0; j<str.length(); j++)
            {
                char ch = str[j];
                if (ch == '(' || ch == '[' || ch == '<' || ch == '{') v.push_back(ch);
                else
                {
                    if (v.size() == 0)
                    {
                        ok = false;
                        cout << "N\n";
                        break;
                    }
                    if (v[int(v.size())-1] == MAP[str[j]]) v.pop_back();
                    else
                    {
                        ok = false;
                        cout << "N\n";
                        break;
                    }
                }
            }
            if (ok && v.size() != 0) cout << "N\n";
            else if (ok) cout << "Y\n";
        }
    }
}