重学数据结构005——栈的应用之平衡符号
? ? ? ? 之前学习了栈的基本操作，并且学习了栈的两种实现方式：链式存储和顺序存储(数组)。现在看看栈都有哪些应用。栈的一个主要应用是平衡符号。
? ? ? ? 初学者在编写代码并且编译时，难免会因为少写了一个')'和被编译器报错。也就是说，编译器会去匹配括号是否匹配。当你输入了一个'('，很自然编译器回去检查你是否有另一个')'符号与之匹配。如果所有的括号都能够成对出现，那么编译器是能够通过的。否则编译器会报错。例如字符序列“(a+b)”是匹配的，而字符序列"(a+b]"则不是。
? ? ? ? 在检测括号匹配的算法中使用到了栈，算法描述如下：创建一个空栈，读取字符序列直到结尾。如果字符是开放符号'(''[''{'，将其入栈；如果是一个封闭符号')'']''}'，则当栈为空时报错。否则，将栈顶元素弹出。如果弹出的符号不是对应的开放符号，则报错。当字符序列结束，判断栈是否为空，为空则报错。
? ? ? ? 下面是我的实现代码：
?
#include <stdio.h>#include <stdlib.h>#define ElementType chartypedef 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;}