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

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

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

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

下面是我的实现代码：

#include<stdio.h>
#include<stdlib.h>
#defineElementTypechar


typedefstructNode*PtrToNode;
typedefPtrToNodeStack;
typedefstructNode
{
ElementTypeElement;
PtrToNodeNext;
};

intIsEmpty(StackS);
StackCreateStack();
voidDisposeStack(StackS);
voidMakeEmpty(StackS);
voidPush(ElementTypeX,StackS);
ElementTypeTop(StackS);
voidPop(StackS);

//判断栈是否为空
intIsEmpty(StackS)
{
returnS->Next==NULL;
}
//创建链栈
StackCreateStack()
{
StackS=malloc(sizeof(structNode));
if(S==NULL)
{
printf("Noenoughmemory!");
returnNULL;
}
S->Next=NULL;
MakeEmpty(S);
returnS;
}

voidMakeEmpty(StackS)
{
if(S==NULL)
{
printf("UseCreateStackFirst!");
}
else
{
while(!IsEmpty(S))
{
Pop(S);
}
}
}

voidPush(ElementTypeX,StackS)
{
PtrToNodeTmp;
Tmp=malloc(sizeof(structNode));
if(Tmp!=NULL)
{
Tmp->Element=X;
Tmp->Next=S->Next;
S->Next=Tmp;
}
else
{
printf("Outofspace!");
}
}

voidPop(StackS)
{

if(IsEmpty(S))
{
printf("TheStackisEmpty!");
}
else
{
PtrToNodeTmp=S->Next;
S->Next=Tmp->Next;
free(Tmp);
}
}

ElementTypeTop(StackS)
{
if(IsEmpty(S))
{
printf("Thestackisempty!");
return0;
}
else
{
returnS->Next->Element;
}
}

//平衡符号判断
voidbalance(char*ch,StackS)
{
ElementTypec;
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,"Thesymbolsnotbalance!\n");
return;
}
else
{
if(Top(S)=='(')
{
Pop(S);
}
else
{
fprintf(stderr,"Thesymbolsnotbalance!\n");
return;
}
}
break;
case']':
if(IsEmpty(S))
{
fprintf(stderr,"Thesymbolsnotbalance!\n");
return;
}
else
{
if(Top(S)=='[')
{
Pop(S);
}
else
{
fprintf(stderr,"Thesymbolsnotbalance!\n");
return;
}
}
break;
case'}':
if(IsEmpty(S))
{
fprintf(stderr,"Thesymbolsnotbalance!\n");
return;
}
else
{
if(Top(S)=='{')
{
Pop(S);
}
else
{
fprintf(stderr,"Thesymbolsnotbalance!\n");
return;
}
}
break;
default:
break;
}
ch++;
}
if(IsEmpty(S))
{
fprintf(stdout,"TheSymbolsBalance!\n");
}
else
{
fprintf(stderr,"TheSymbolsNotBalance!\n");
}
}

intmain(void)
{
charch[]="(a+b){[d]c*d}{";
StackS=CreateStack();
balance(ch,S);
return0;
}