纯C解决括号匹配问题

先看问题描述
描述
假设一个算术表达式中可以包含三种括号:圆括号“(”和“)” 、方圆括号“[”和“]”、和花括号“{”和“}”,且这三种括号可按任意的次序嵌套使用(如:…[…{…}…[…]…]…[…]…(…)…)。编写判别给定表达式中所含括号是否正确配对出现的算法。若正确配对则输出yes,否则输出no。

输入

测试数据有多组,处理到文件尾。每组测试数据在同一行中输入不超过50个字符的算术表达式(不要求算术表达式一定合法)。

输出

根据算术表达式中的括号是否正确配对输出yes或no。

样例输入

a*[b+c*{d-e}+5*6-[7*8]*9]+[3*10]+5*18*(3*e)+5
3-[4+c*{9-5}+a*6-[d*e]+3
3-{[((()))]}+3

样例输出

yes
no
yes


鄙人纯C代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include<stdio.h>
#include<stdlib.h>
#define MAX 101
typedef struct node {
char flag;
struct node *next;
}linklist;
linklist* push(linklist *last,char w)
{
linklist*p=(linklist*)malloc(sizeof(linklist));
p->flag=w;
p->next=last;
return p;
}
int main()
{
char a[MAX];
while(gets(a))
{
bool result=0;
int i;
linklist*p=push(NULL,NULL);
for(i=0;a[i];i++)
{
int x=2;
switch (a[i])
{
case '(':x--;
case '[':
case '{':
p=push(p,a[i]+x);
break;
case ')':
case ']':
case '}':
{
if(p->next==NULL) goto END;
/*这里缺了free(空间),要小心*/
else
{
if(a[i]==p->flag)
p=p->next;
else
goto END;
}
}
}
}
if(p->next==NULL)
result=1;
END:puts(result?"yes":"no");
}
return 0;
}

还有C++版的代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include<stack>
using namespace std;
bool GetResult(char *a)
{
stack<char>p;
for(int i=0,x;a[i];i++)
{
x=2;
switch (a[i])
{
case '(':x--;
case '[':
case '{':p.push(a[i]+x);break;
case ')':
case ']':
case '}':
{
if(!p.empty()&&a[i]==p.top())
p.pop();
else
return 0;
}
}
}
return p.empty();
}
int main()
{
char string_buffer[150];
while(gets(string_buffer))
puts(GetResult(string_buffer)?"yes":"no");
return 0;
}

本文为原创,转载请遵守本站版权声明

更新于:2015年10月24日 01:10