括号匹配(栈和队列)

括号匹配(栈和队列)

时间： 1ms        内存：128M

描述：

假设一个算术表达式中可以包含三种括号：圆括号“(”和“)”，方括号“[”和“]”和花括号“{”和“ ”，且这三种括号可按任意的次序嵌套使用（如：…[…{… …[…]…]…[…]…(…)…)。编写判别给定表达式中所含括号是否正确配对出现的算法。输出结果YES 或者 NO。

输入：

5+{[2X5]+2}

输出：

YES

示例输入：

8-[{2+7]}

示例输出：

NO

提示：

参考答案（内存最优[752]）：

#include<stdio.h>
#include<malloc.h>
#define SEN 100

struct sqstack
{
	char *base;
	char *top;
	int size;
};

struct sqstack *initEmptyStack()
{
	struct sqstack *p;
	p=(struct sqstack *)malloc(sizeof(struct sqstack));
	if(p!=NULL)
	{
		p->base=(char *)malloc(sizeof(struct sqstack)*SEN);
		if(p->base!=NULL)
		{
			p->top=p->base;
			p->size=SEN;
			return p;
		}
	}
	else
		free(p);
	return NULL;
}

int push(struct sqstack *p,char a)
{
	*p->top++=a;
	return 0;
}


int gettop(struct sqstack *p)
{
	if(p->base!=p->top)
		return *(p->top-1);
	return 0;
}
int *pop(struct sqstack *p)
{
	--p->top;
	return 0;
}

int main()
{
	char a,b;
	struct sqstack *p;
	p=initEmptyStack();
	while(scanf("%c",&a)&&a!='\n')
	{
		switch(a)
		{
		case '(':
			{
				push(p,a);
				break;
			}
		case '[':
			{
				push(p,a);
				break;
			}
		case '{':
			{
				push(p,a);
				break;
			}
		case ')':
			{
				b=gettop(p);
				if(b!='(')
				{
					printf("NO\n");
					return 0;
				}
				else
				{
					pop(p);
					break;
				}
			}
		case ']':
			{
				b=gettop(p);
				if(b!='[')
				{
					printf("NO\n");
					return 0;
				}
				else
				{
					pop(p);
					break;
				}
			}
		case '}':
			{
				b=gettop(p);
				if(b!='{')
				{
					printf("NO\n");
					return 0;
				}
				else
				{
					pop(p);
					break;
				}
			}
		default :{}
		}
	}
	if(p->base==p->top)
		printf("YES\n");
	else
		printf("NO\n");
	return 0;
}

参考答案（时间最优[0]）：

#include<stdio.h>
#include<malloc.h>
#define SEN 100

struct sqstack
{
	char *base;
	char *top;
	int size;
};

struct sqstack *initEmptyStack()
{
	struct sqstack *p;
	p=(struct sqstack *)malloc(sizeof(struct sqstack));
	if(p!=NULL)
	{
		p->base=(char *)malloc(sizeof(struct sqstack)*SEN);
		if(p->base!=NULL)
		{
			p->top=p->base;
			p->size=SEN;
			return p;
		}
	}
	else
		free(p);
	return NULL;
}

int push(struct sqstack *p,char a)
{
	*p->top++=a;
	return 0;
}


int gettop(struct sqstack *p)
{
	if(p->base!=p->top)
		return *(p->top-1);
	return 0;
}
int *pop(struct sqstack *p)
{
	--p->top;
	return 0;
}

int main()
{
	char a,b;
	struct sqstack *p;
	p=initEmptyStack();
	while(scanf("%c",&a)&&a!='\n')
	{
		switch(a)
		{
		case '(':
			{
				push(p,a);
				break;
			}
		case '[':
			{
				push(p,a);
				break;
			}
		case '{':
			{
				push(p,a);
				break;
			}
		case ')':
			{
				b=gettop(p);
				if(b!='(')
				{
					printf("NO\n");
					return 0;
				}
				else
				{
					pop(p);
					break;
				}
			}
		case ']':
			{
				b=gettop(p);
				if(b!='[')
				{
					printf("NO\n");
					return 0;
				}
				else
				{
					pop(p);
					break;
				}
			}
		case '}':
			{
				b=gettop(p);
				if(b!='{')
				{
					printf("NO\n");
					return 0;
				}
				else
				{
					pop(p);
					break;
				}
			}
		default :{}
		}
	}
	if(p->base==p->top)
		printf("YES\n");
	else
		printf("NO\n");
	return 0;
}

题目和答案均来自于互联网，仅供参考，如有问题请联系管理员修改或删除。