括号匹配(栈和队列)

括号匹配(栈和队列)

时间: 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;
}

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

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注