acwing3683 括号匹配--栈的应用_算法给的安全感的博客-爱代码爱编程
项目场景:
利用栈先进后出的性质可以实现对左右括号的匹配问题。
问题描述
苗苗今天刚刚学会使用括号,不过他分不清小括号,中括号,大括号和尖括号,不知道怎么使用这些括号,请帮助他判断括号使用是否正确。
输入格式
共一行,包含一个由 <,(,{,[,>,),},] 构成的字符串。
输出格式
如果输入的字符串中的括号正确匹配则输出 yes,否则输出 no。
数据范围
输入字符串长度不超过 10000。
原因分析:
栈的性质是先进后出,可以先将左边括号存入栈中,加进来的元素与栈顶元素匹配,如果能实现匹配,则将栈顶元素出栈即可实现。
#include<iostream>
#include<algorithm>
#include<stack>
using namespace std;
const int N = 100010;
stack<char> c;
int main(){
string str;
cin>>str;
for(int i=0;i<str.size();i++){
//左边符号
if(str[i]=='<' || str[i]=='(' || str[i]=='{' ||str[i]=='['){
c.push(str[i]);
}
//右边符号
else{
if(c.empty()){
cout<<"no"<<endl;
return 0;
}
else if( (str[i]=='>'&&c.top()=='<') ||
(str[i]==')'&&c.top()=='(' ) || (str[i]=='}'&&c.top()=='{') || (str[i]==']'&&c.top()=='[') ){
c.pop();
}
else {
cout<<"no"<<endl;
return 0;
}
}
}
if(c.empty()) cout<<"yes"<<endl;
else cout<<"no"<<endl;