数据结构实验之栈四：括号匹配
Time Limit: 1000ms Memory limit: 65536K 有疑问？点这里^_^
题目描述
给你一串字符，不超过50个字符，可能包括括号、数字、字母、标点符号、空格，你的任务是检查这一串字符中的( ) ,[ ],{ }是否匹配。
输入
输入数据有多组，处理到文件结束。
输出
如果匹配就输出“yes”，不匹配输出“no”
示例输入
sin(20+10)
{[}]
示例输出
yes
no
字符为 ( { [ 时 直接入栈。
字符为 ) ] } 时 判断栈顶字符是否为对应括号，是则弹出栈顶字符，不是则终止循环输出no
字符为其他时不作处理。
最后栈为空时，且flag为1，匹配成功。
#include <stdio.h>
#include <stdlib.h>#include <string.h>
typedef struct {
char *base;
char *top;
int Lsize;
}Sqstack;
Sqstack Create(Sqstack &s)
{
s.base=(char *)malloc(1010*sizeof(char));
s.top=s.base;
return s;
}
Sqstack push(Sqstack &s,char e){
*s.top++=e;
}
char gettop(Sqstack &s)
{
char e;
e=*(s.top-1);
return e;
}
char pop(Sqstack &s){
char a;
if(s.top==s.base)return -1;
s.top--;
a=*s.top;
return a ;
}
int Empty(Sqstack &s){
if(s.top==s.base) return 1;
else return 0;
}
char clearstack(Sqstack &s){
s.top=s.base;
}
Sqstack Match(Sqstack &s,char b[],int l){
int i;
int flag=1;
for(i=0;i<l;i++){
if(b[i]=='('||b[i]=='['||b[i]=='{'){ //字符为 ( { [ 时 直接入栈。
push(s,b[i]);
}else if(b[i]==')'){ 判断栈顶字符是否为对应括号，是则弹出栈顶字符，不是则终止循环输出no
if(gettop(s)!='('){
printf("no\n");
flag=0;
break;
}else{
pop(s);
}
}
else if(b[i]==']'){
if(gettop(s)!='['){
printf("no\n");
flag=0;
break;
}else{
pop(s);
}
}
else if(b[i]=='}'){
if(gettop(s)!='{'){
printf("no\n");
flag=0;
break;
}else {
pop(s);
}
}
}
if(Empty(s)&&flag==1){ //栈为空时，且flag为1，匹配成功。
printf("yes\n");
}
else if(flag) printf("no\n"); //栈不为空，但是也么有上面的输出no，例如只输入了个 [
clearstack(s);
}
int main()
{
int i,len;
char a[51];
Sqstack S;
S=Create(S);
while(gets(a)){
len=strlen(a);
Match(S,a,len);
}
}