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