題解——括號匹配
文章目錄
- 題解——括號匹配
- 描述
- 輸入
- 輸出
- 樣例輸入
- 樣例輸出
- 提示
- 題解
題目鏈接：傳送門
描述
假設運算式中只包含三種括號：圓括號、方括號和花括號，它們可相互嵌套，如([{}])或({[][()]})等均為正確的格式,而{[]})}或{[()]或([]}均為不正確的格式.
輸入一串括號
如果輸入的右括號多余，輸出: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;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/171633.html
標籤：其他
上一篇：Unity2D游戲開發之Sprite碎裂特效的實作（獨立解耦的組件，附詳細流程和代碼）
下一篇：五子棋