学步园

  栈的特点之一是FILO（先进后出），基于这个特点在这里给出栈的部分基础应用：

1：括号匹配；

  所谓的括号匹配就是一个表达式中包括变量、常量、操作符、圆括号，圆括号可以嵌套, 编写程序判断表达式中的括号是否正确匹配。输入任意一个表达式，判断其中括号是否匹配。

  利用栈的特性可以很简单的解决这个问题，对于一个表达式从第一个字符开始处理，如果遇到左括号就入站，如果遇到右括号就与栈顶元素匹配，如果右括号与栈顶元素无法匹配那么程序可以终止。因为很显然这个表达式的括号不匹配。而且程序的开始和结束时，括号匹配的表达式所对应的栈是空的。

例如《《（》》》

还有《《《》》

下面给出函数代码：

void Match(SqStack *s)
{
	char ch;
	while((ch = getchar()) != '\n')
	{
		switch (ch)
		{
			case '(': Push(s,ch);break;
			case '<': Push(s,ch);break;
			case '[': Push(s,ch);break;
			case '{': Push(s,ch);break;
			case ')': if(GetTop(s) == '('){Pop(s);break;}
					  else
						{printf("括号不匹配.\n");return;}
			case '>': if(GetTop(s) == '<'){Pop(s);break;}
					  else
					  {printf("括号不匹配.\n");return;}
			case ']': if(GetTop(s) == '['){Pop(s);break;}
					  else
					  {printf("括号不匹配。\n");return;}
			case '}': if(GetTop(s) == '{'){Pop(s);break;}
					  else
					  {printf("括号不匹配。\n");return;}
		}
	}
	if (IsEmpty(s))
		printf("括号不匹配。\n");
	else
		printf("括号匹配.\n");
	
}

这个函数可以处理的括号有四种< ( [ {}])>

里面有关于栈的函数在前面已经写过，这里还是把程序的完整代码贴出来好一些：

#include <stdio.h>
#include <stdlib.h>
#define STACK_INIT_SIZE 100		//栈空间的初始分配量
#define STACKINCREMENT 10		//存储空间的分配增量

typedef char SElemType;
typedef struct
{
	SElemType *base;	//在构造栈之前和销毁栈之后,base的数值为NULL
	SElemType *top;		//栈顶指针
	int stacksize;		//显示栈当前的容量
}SqStack;


//创建一个空栈
int InitStack(SqStack *s);
//销毁栈
int DestroyStack(SqStack *s);
//清空栈
int ClearStack(SqStack *s);
//判断栈是否为空栈
int StackEmpty(SqStack *s);
//计算栈的长度
int StackLength(SqStack *s);
//获取栈顶元素
int GetTop(SqStack *s);
//将一个元素推入站内
int Push(SqStack *s,SElemType data);
//将一个元素退出栈
int Pop(SqStack *s);
//对于栈内的每一个元素调用函数
int StackTraverse(SqStack *s);


int InitStack(SqStack *s)
{
	s->base = (SElemType *)malloc(sizeof(SElemType)*STACK_INIT_SIZE);		//为栈分配基础空间
	if(!s->base)exit(1);		//分配失败的话就退出
	s->top = s->base;			//栈顶指针指向栈底
	s->stacksize = STACK_INIT_SIZE;	//初始化栈的大小

	return 1;
}


int Push(SqStack *s,SElemType data)
{
	if(s->top-s->base >= s->stacksize)		//如果栈的空间不够再增加
	{
		s->base = (SElemType *)realloc(s->base,(s->stacksize + STACKINCREMENT)*sizeof(SElemType));
		if(!s->base)exit(1);		//在原来空间的基础上额外增加空间

		s->top = s->base + s->stacksize;	//栈顶指针加1
		s->stacksize += STACKINCREMENT;		//栈大小增加
	}

	*s->top++ = data;		//元素入栈,栈顶指针加1
	return 1;		//入栈成功
}

int Pop(SqStack *s)
{
	if(s->base == s->top) return 0;		//如果栈为空栈返回出栈失败
	(*--s->top);		//栈顶指针减1
	return 1;			//出栈成功
}

int GetTop(SqStack *s)
{
	if(s->base == s->top)
		return 0;		//空栈返回失败
	return *(s->top-1); //返回栈顶元素
}

int StackLength(SqStack *s)
{
	SElemType *tmp = s->top;	//设置临时变量和栈顶指针相同
	int flag = 0;
	while(tmp != s->base)		//栈顶指针逐个减1知道栈底
	{
		flag ++;
		tmp--;
	}
	return flag;		//返回栈的长度

}

int DestroyStack(SqStack *s)
{
	free(s->base);		//释放掉栈的分配空间
	s->base = s->top = NULL;	//栈顶和栈底指向NULL
	s->stacksize = 0;	//栈的长度还原为0
	return 1;
}

int ClearStack(SqStack *s)
{
	s->top = s->base;	//栈清空最方便只需要将栈顶指针指向栈底
	return 1;
}

int StackTraverse(SqStack *s)
{
	SElemType *tmp = (s->top-1);
	if(s->top == s->base)return 0;
	while(1)
	{
		printf("%d ",*tmp);
		if(tmp == s->base) break;		//这个地方我刚刚犯了一个错误就是忽视栈底base指针指向的区域也有一个数据
		tmp--;
	}

	return 1;
}

int IsEmpty(SqStack *s)
{
	if(s->base == s->top)return 0;
	else return 1;
}

void Match(SqStack *s)
{
	char ch;
	while((ch = getchar()) != '\n')
	{
		switch (ch)
		{
			case '(': Push(s,ch);break;
			case '<': Push(s,ch);break;
			case '[': Push(s,ch);break;
			case '{': Push(s,ch);break;
			case ')': if(GetTop(s) == '('){Pop(s);break;}
					  else
						{printf("括号不匹配.\n");return;}
			case '>': if(GetTop(s) == '<'){Pop(s);break;}
					  else
					  {printf("括号不匹配.\n");return;}
			case ']': if(GetTop(s) == '['){Pop(s);break;}
					  else
					  {printf("括号不匹配。\n");return;}
			case '}': if(GetTop(s) == '{'){Pop(s);break;}
					  else
					  {printf("括号不匹配。\n");return;}
		}
	}
	if (IsEmpty(s))
		printf("括号不匹配。\n");
	else
		printf("括号匹配.\n");
	
}
int main()
{
	SqStack s;

	//初始化栈并且创建栈
	InitStack(&s);
	Match(&s);
	//清空栈
	ClearStack(&s);
	//销毁栈
	DestroyStack(&s);
	return 0;
}