題解——括號匹配

題解——括號匹配

題目連結：傳送門

描述

假設表示式中只包含三種括號：圓括號、方括號和花括號，它們可相互巢狀，如([{}])或({[][()]})等均為正確的格式,而{[]})}或{[()]或([]}均為不正確的格式.

輸入一串括號
如果輸入的右括號多餘，輸出:Extra right brackets
如果輸入的左括號多餘, 輸出:Extra left brackets
如果輸入的括號不匹配，輸出:Brackets not match
如果輸入的括號匹配，輸出:Brackets match

輸入

{{{{)))

輸出

Brackets not match

樣例輸入

{([)]}

樣例輸出

Brackets not match

提示

利用棧結構

題解

因為棧的結構恰好是先進後出，所以我們用字串讀取所有括號後，從左到右掃描一遍，如果：

• 掃描到左括號(或[或{，將它入棧，繼續掃描；
• 掃描到右括號)或]或}，判斷當前棧頂元素是不是與之匹配的左括號，如果：
  • 這時候棧頂沒有元素了，那麼說明右括號多了，輸出Extra right brackets，掃描結束；
  • 恰好匹配，則將左括號出棧並繼續掃描；
  • 不匹配，輸出Brackets not match，掃描結束；

按上面的方式掃描，如果中間沒有因為特殊原因終止，而是順利掃描完了整個字串，那麼：

• 如果此時棧內還有元素，注意上面的操作中只有左括號入棧，沒有右括號入棧，所以說明左括號多了，輸出Extra left brackets
• 如果此時棧空了，說明正好匹配完，輸出Brackets match

#include <iostream>
#include <cstring>
#include <stack> //方便起見，直接用stl裡的棧啦
using namespace std;
stack<char> st;
char s[1000];
int main()
{
    cin>>s;
    bool f=1; //用於標記「因為特殊原因結束掃描」
    for(int i=0;i<strlen(s);i++){
        if(s[i]=='('||s[i]=='['||s[i]=='{')
            st.push(s[i]);
        if(s[i]==')'||s[i]==']'||s[i]=='}'){
            if(st.empty()){
                cout<<"Extra right brackets"<<endl;
                f=0; //因為特殊原因結束掃描
                break;
            }
            else{
                int sum=(int)s[i]+(int)st.top(); //用ascii碼檢驗括號是否匹配
                if(sum==123+125||sum==91+93||sum==40+41)
                {
                    st.pop();
                    continue;
                }
                else{
                    cout<<"Brackets not match"<<endl;
                    f=0; //因為特殊原因結束掃描
                    break;
                }
            }
        }
    }
    if(f)
    {
        if(st.empty())
            cout<<"Brackets match"<<endl;
        else
            cout<<"Extra left brackets"<<endl;
    }
    return 0;
}