纯C解决括号匹配问题
2013年10月15日 00:41先看问题描述
描述
假设一个算术表达式中可以包含三种括号：圆括号“(”和“)” 、方圆括号“[”和“]”、和花括号“{”和“}”，且这三种括号可按任意的次序嵌套使用(如：…[…{…}…[…]…]…[…]…(…)…)。编写判别给定表达式中所含括号是否正确配对出现的算法。若正确配对则输出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代码
#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++版的代码
#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;
}
文章作者: qbeenslee
