重学数据结构005——栈的应用之平衡符号

        之前学习了栈的基本操作，并且学习了栈的两种实现方式：链式存储和顺序存储(数组)。现在看看栈都有哪些应用。栈的一个主要应用是平衡符号。

        初学者在编写代码并且编译时，难免会因为少写了一个')'和被编译器报错。也就是说，编译器会去匹配括号是否匹配。当你输入了一个'('，很自然编译器回去检查你是否有另一个')'符号与之匹配。如果所有的括号都能够成对出现，那么编译器是能够通过的。否则编译器会报错。例如字符序列“(a+b)”是匹配的，而字符序列"(a+b]"则不是。

        在检测括号匹配的算法中使用到了栈，算法描述如下：创建一个空栈，读取字符序列直到结尾。如果字符是开放符号'(''[''{'，将其入栈；如果是一个封闭符号')'']''}'，则当栈为空时报错。否则，将栈顶元素弹出。如果弹出的符号不是对应的开放符号，则报错。当字符序列结束，判断栈是否为空，为空则报错。

        下面是我的实现代码：

 

#include <stdio.h>
#include <stdlib.h>
#define ElementType char


typedef struct Node *PtrToNode;
typedef PtrToNode Stack;
typedef struct Node
{
	ElementType Element;
	PtrToNode Next;
};

int IsEmpty(Stack S);
Stack CreateStack();
void DisposeStack(Stack S);
void MakeEmpty(Stack S);
void Push(ElementType X,Stack S);
ElementType Top(Stack S);
void Pop(Stack S);

//判断栈是否为空
int IsEmpty(Stack S)
{
	return S->Next == NULL;
}
//创建链栈
Stack CreateStack()
{
	Stack S = malloc(sizeof(struct Node));
	if(S == NULL)
	{
		printf("No enough memory!");
		return NULL;
	}
	S->Next = NULL;
	MakeEmpty(S);
	return S;
}

void MakeEmpty(Stack S)
{
	if(S == NULL)
	{
		printf("Use CreateStack First!");
	}
	else
	{
		while(!IsEmpty(S))
		{
			Pop(S);
		}
	}
}

void Push(ElementType X,Stack S)
{
	PtrToNode Tmp;
	Tmp = malloc(sizeof(struct Node));
	if(Tmp != NULL)
	{
		Tmp->Element = X;
		Tmp->Next = S->Next;
		S->Next = Tmp;
	}
	else
	{
		printf("Out of space!");
	}
}

void Pop(Stack S)
{
	
	if(IsEmpty(S))
	{
		printf("The Stack is Empty!");
	}
	else
	{
		PtrToNode Tmp = S->Next;
		S->Next = Tmp->Next;
		free(Tmp);
	}
}

ElementType Top(Stack S)
{
	if(IsEmpty(S))
	{
		printf("The stack is empty!");
		return 0;
	}
	else
	{
		return S->Next->Element;
	}
}

//平衡符号判断
void balance(char *ch,Stack S)
{
	ElementType c;
	MakeEmpty(S);
	while((c=*ch) != '\0')
	{
		printf("%c\n",c);
		switch(c)
		{
		case '(':
		case '[':
		case '{':
			Push(c,S);
			break;
		case ')':
			if(IsEmpty(S))
			{
				fprintf(stderr,"The symbols not balance!\n");
				return;
			}
			else
			{
				if(Top(S)=='(')
				{
					Pop(S);
				}
				else 
				{
					fprintf(stderr,"The symbols not balance!\n");
					return;
				}
			}
			break;
		case ']':
			if(IsEmpty(S))
			{
				fprintf(stderr,"The symbols not balance!\n");
				return;
			}
			else
			{
				if(Top(S)=='[')
				{
					Pop(S);
				}
				else 
				{
					fprintf(stderr,"The symbols not balance!\n");
					return;
				}
			}
			break;
		case '}':
			if(IsEmpty(S))
			{
				fprintf(stderr,"The symbols not balance!\n");
				return;
			}
			else
			{
				if(Top(S)=='{')
				{
					Pop(S);
				}
				else 
				{
					fprintf(stderr,"The symbols not balance!\n");
					return;
				}
			}
			break;
		default:
			break;
		}
		ch++;
	}
	if(IsEmpty(S)) 
	{
		fprintf(stdout,"The Symbols Balance!\n");
	}
	else
	{
		fprintf(stderr,"The Symbols Not Balance!\n");
	}
}

int main(void)
{
	char ch[] = "(a+b){[d]c*d}{";
	Stack S = CreateStack();
	balance(ch,S);
	return 0;
}