【问题描述】
利用栈解决括号匹配问题。
【基本要求】
采用链式存储实现栈的初始化、入栈、出栈操作。给定一个括号序列，里面包括圆括号、方括号和花括号，编程检验该括号序列中括号是否配对。代码：
#include<bits/stdc++.h> using namespace std; typedef struct linknode{ char data; struct linknode *next; }LinkSNode; void InsitStack(LinkSNode *&s) //初始化栈 { s=(LinkSNode *)malloc(sizeof(LinkSNode)); s->next=NULL; } void DestoryStack(LinkSNode *&s) //销毁栈 { LinkSNode *pre=s,*p=s->next; while(p!=NULL) { free(pre); pre=p; p=pre->next; } free(pre); } bool StackEmpty(LinkSNode *&s) //空栈判断 { return s->next==NULL; } void Push(LinkSNode *&s,char e) //进栈 { LinkSNode *p; p=(LinkSNode *)malloc(sizeof(LinkSNode)); p->data=e; p->next=s->next; s->next=p; } bool pop(LinkSNode *&s,char &e) //出栈 { LinkSNode *p; if(s->next==NULL) return false; p=s->next; e=p->data; s->next=p->next; free(p); return true; } bool top(LinkSNode *&s,char &e) //取栈顶元素 { if(s->next==NULL) return false; e=s->next->data; return true; } bool match(string a,int n) //括号配对函数 { int i=0;char e; bool match=true; LinkSNode *st; InsitStack(st); while(i<n && match) { switch(a[i]) { case '(': case '[': case '{': Push(st,a[i]); break; case ')': if(top(st,e)==true) { if(e!='(') match=false; else pop(st,e); } else match=false; break; case ']': if(top(st,e)==true) { if(e!='[') match=false; else pop(st,e); } else match=false; break; case '}': if(top(st,e)==true) { if(e!='{') match=false; else pop(st,e); } else match=false; break; } /* if(a[i]=='(') Push(st,a[i]); else if(a[i]==')') { if(top(st,e)==true) { if(e!='(') match=false; else pop(st,e); } else match=false; } if(a[i]=='[') Push(st,a[i]); else if(a[i]==']') { if(top(st,e)==true) { if(e!='[') match=false; else pop(st,e); } else match=false; } if(a[i]=='{') Push(st,a[i]); else if(a[i]=='}') { if(top(st,e)==true) { if(e!='{') match=false; else pop(st,e); } else match=false; } */ i++; } if(!StackEmpty(st)) match=false; DestoryStack(st); return match; } int main() { string a; cin >> a; int len=a.length(); bool ans=match(a,len); if(ans==true) cout << "YES" << endl; else cout << "NO" << endl; }
