数据结构实验之栈四：括号匹配
Time Limit: 1000MS Memory limit: 65536K
题目描述
给你一串字符，不超过50个字符，可能包括括号、数字、字母、标点符号、空格，你的任务是检查这一串字符中的( ) ,[ ],{ }是否匹配。
输入
输入数据有多组，处理到文件结束。
输出
如果匹配就输出“yes”，不匹配输出“no”
示例输入
sin(20+10)
{[}]
示例输出
yes
no
常规解法：
注意，此处建链栈方法必须是这样的。
1 #include<stdio.h>
2 #include<malloc.h>
3 #include<string.h>
4 typedef char elemtype;
5 typedef struct node
6 {
7 char data;
8 struct node *next;
9 }stack;
10 stack *top;
11 void push(elemtype n)//进栈
12 {
13 stack *p;
14 p=(stack *)malloc(sizeof(stack));
15 p->data=n;
16 p->next=top->next;
17 top->next=p;
18 }
19 void pop()//出栈
20 {
21 stack *q;
22 q=top->next;
23 top->next=q->next;
24 free(q);//释放内存
25 }
26 char gettop()//取栈顶元素
27 {
28 return top->next->data;
29 }
30 void judge(char a[])
31 {
32 int i,tag=0,len=strlen(a);
33 for(i=0;i<len;i++)
34 {
35 if(a[i]=='('||a[i]=='['||a[i]=='{')
36 {
37 push(a[i]);//进栈
38 continue;
39 }
40 if(a[i]!=')'&&a[i]!=']'&&a[i]!='}')//输入的不是括号
41 continue;
42 if(top->next==NULL)//有了右半个括号，但是没有左半个括号的情况
43 {
44 printf("no
");
45 break;
46 }
47 if(a[i]-gettop()==1||a[i]-gettop()==2)//判断是否匹配
48 pop(); //出栈
49 else
50 {
51 printf("no
");
52 break;
53 }
54 }
55 if(i==len)//如果没有遍历到头，此语句不执行
56 {
57 if(top->next==NULL)
58 printf("yes
");
59 else printf("no
");
60 }
61 top->next=NULL;//置栈空
62 }
63 int main()
64 {
65 top=(stack *)malloc(sizeof(stack));//申请头节点空间
66 top->next=NULL;//头节点指向空
67 char a[100];
68 while(gets(a)!=NULL)
69 {
70 judge(a);
71 }
72 return 0;
73 }
数组模拟方法：
1 #include <stdio.h>
2 #include <stdlib.h>
3 #include <string.h>
4 #define MAXN 200
5 int st[MAXN];
6 int main(){
7 int top, i, len, flag;
8 char s[100];
9 while(gets(s)){
10 len = strlen(s);
11 top = 0; flag = 1;
12 for(i=0; i<len; i++){
13 if(s[i] == '(' || s[i] == '[' || s[i] == '{')
14 st[top++] = s[i];
15 else if(s[i] == ')'){
16 if(top && st[top-1] == '(')
17 st[--top];
18 else {printf("no
"); flag = 0; break;}
19 }
20 else if(top && s[i] == ']'){
21 if(st[top-1] == '[')
22 st[--top];
23 else {printf("no
"); flag = 0;break; }
24 }
25 else if(top && s[i] == '}'){
26 if(st[top-1] == '{')
27 st[--top];
28 else {printf("no
"); flag = 0;break;}
29 }
30 }
31 if(flag){
32 if(top == 0) printf("yes
");
33 else printf("no
");
34 }
35 }
36 return 0;
37 }