题目描述
栈内只存放左括号,每次有右括号出现,就出栈来判断
- 三种情况结束匹配:
1.括号左右不匹配
2.右括号想匹配,但是栈空
3.扫描完字符串,栈内还有左括号
王道写法
样例
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
#define MaxSize 100000
typedef struct {
int top;
char data[MaxSize];
}SqStack;
void InitStack(SqStack &s){
s.top=-1;
}
bool EmptyStack(SqStack s){
if(s.top== -1 ) return true;
else return false;
}
bool Push(SqStack &s,char &e){
if(s.top == MaxSize - 1) return false;
s.data[++s.top]=e;
return true;
}
bool Pop(SqStack &s,char &e){
if(EmptyStack(s)) return false;
e=s.data[s.top--];
return true;
}
bool Match(string s){
SqStack stk;
InitStack(stk);
for(int i=0;i<s.size();i++){
if(s[i]=='<'||s[i]=='{'||s[i]=='('||s[i]=='['){
Push(stk,s[i]);
} else{
//栈空直接结束
if(EmptyStack(stk)) return false;
char topElem;
Pop(stk,topElem);
if(s[i]=='>'&&topElem!='<') return false;
if(s[i]=='}'&&topElem!='{') return false;
if(s[i]==')'&&topElem!='(') return false;
if(s[i]==']'&&topElem!='[') return false;
}
}
return EmptyStack(stk);
}
int main(){
string s;
cin>>s;
if(Match(s)) {
cout<<"yes";
return 0;
}
cout<<"no";
return 0;
}