ZeroJudge E924: 括號配對

請撰寫一個程式，輸入一行字串後，輸出該字串的括號配對是否正確。
要檢查的括號有圓括號 ()、方括號 []、小於大於括號 <> 和曲括號 {}。

範例測資

範例輸入範例輸出
輸入第一行有一個正整數 T (1 ≤ T ≤ 1000），
代表接下來共有 T 行字串要驗證。
接下來依序有 T 行，每行為需要驗證括號配對的字串 s，字串中只會出現 ()、[]、<> 和 {}。		若配對成功輸出「Y」
若配對失敗輸出「N」
4
{()<>}[]
(){
{(})
())		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。

範例程式碼－ZeroJudge E924: 括號配對

#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";
        }
    }
}

//ZeroJudge E924
//Dr. SeanXD
標籤

相關文章

發佈留言