纯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; }