括號匹配

題目

在程式設計當中我們只會用到三種括號：圓括號()，方括號[]和花括號{}，編譯器在編譯的時候會檢查括號是否正確匹配。例如{[()]}、{()[]{}}都是合法的匹配。但是([)]則是不合法的匹配。請編寫一個程式來判斷輸入的括號序列是否合法。

輸入

測試數據由多組，每組數據有一行，爲( ) [ ] { }組成的序列，長度不超過1000

輸出

對於每組數據輸出一行，如果是合法匹配則輸出YES，不合法則輸出NO，請注意大小寫

樣例輸入

{([()]{})}

樣例輸出

YES

思路小導

本題也是解法衆多，但是萬變不離其中，無論如何我們要用到的都是棧的相關知識，在你不懂如何使用棧，修改棧中元素時，不管C語言還是C++都可以直接使用陣列在作爲基底，對出棧和進棧等等操作（push(),pop(),empty()…）分別寫一個函數，在主函數中呼叫使用即可，此處我們直接使用棧來實現，來複習練習棧的使用。

程式碼流程

#include<bits/stdc++.h>
#include<iostream>

using namespace std;

bool ok(string &s) {//寫一個判斷括號匹配合法的函數
    stack<char> S;//定義字元棧
    for (auto c:s) {//auto回圈方便遍歷
        if (c == '(' || c == '[' || c == '{')S.push(c);//如果是左括號就進棧
        if (c == ')') {//如果是右括號
            if (S.empty() || S.top() != '(')return false;//先過濾掉棧爲空和棧頂不爲相應左括號的情況
            S.pop();//再移出棧
        }
        if (c == ']') {
            if (S.empty() || S.top() != '[')return false;
            S.pop();
        }
        if (c == '}') {
            if (S.empty() || S.top() != '{')return false;
            S.pop();
        }
    }
    return S.empty();//返回棧爲空
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
   for(string s;cin>>s;){//回圈輸入字串，題目要求多組輸入，若給出固定組數，再回圈前定義輸入即可
        if (ok(s)) {
            cout << "YES" << endl;
        } else {
            cout << "NO" << endl;
        }
    }
    return 0;
}

小結

1.本題首先要知道哪些條件纔可以判斷合法的匹配
2.然後理好思緒每一步要實現的內容
3.正確使用棧
4.操作過程中倘若有誤，一定要多測試，實踐出真知，有時可以用cerr代替cout來輸出表示測試的數據。