栈的经典用法——判断括号是否匹配

栈的经典用法——判断括号是否匹配

#简单说明栈的特征： 本处使用顺序栈判断括号匹配，首先我们知道栈是一种只能在一段操作的线性表。其插入，删除仅能在一端进行操作，就像一个瓶子一样，不管是取东西还是放东西都只能在瓶口进行，那么最后最先进栈的元素就一定是最后出栈的元素。利用这一特性，我们就可以判断括号是否匹配了。

#主要思路如下： 我们从左到右依次扫描需要判断的字符串，遇见“（”，“{”，“[”就入栈，遇见“）”，“]”，“]”就出栈。若三种左括号没有全部入栈便碰到了右括号那显然不匹配。碰到左括号进栈，碰到与其相匹配的右括号时出栈，当字符串扫描到‘\0’,并且此时栈为空则括号匹配，否则不匹配。

#创建顺序栈

#include#include#definetypedef char datatype;//创建stacktypedef struct { datatype data[MAXSIZE]; int top;}SeqStack;//初始化stackvoid Init_SeqStack(SeqStack **s){//这里需要使用二级指针，只有通过二级指针或返回指针的函数才可在主调函数中访问到被调函数中生成的线性表，初学者尤其注意 *s=(SeqStack*)malloc(sizeof(SeqStack)); (*s)->top=-1;}//判空，空则返回1int Empty_SeqStack(SeqStack *s){ if(s->top==-1) return 1; else return 0;}void Push_SeqStack(SeqStack *s,datatype x){ if(s->top==MAXSIZE-1) puts("the stack is full!");//有换行符 else { s-> top++; s->data[s->top]=x; }}void Pop_SeqStack(SeqStack *s){ if(s->top==-1) puts("the stack is empty!"); else s->top--;}

#判断是否匹配的函数

void Match_SeqStack(SeqStack *s,datatype test[]){ int i=0; while(test[i]!='\0') { //遇见左括号入栈 if(test[i]=='('||test[i]=='['||test[i]=='{') { Push_SeqStack(s,test[i]); i++; continue; //每入栈一个元素就进行下一次循环，扫描下一个字符 } //当遇见匹配的右括号时，则将栈顶左括号出栈 //用if....... else if...... if 的结构保证每扫描到一个匹配的右括号，只有一个匹配的字符出栈，每执行完一个判断框之后的程序则continue进行下一次循环 if(test[i]==')'&&s->data[s->top]=='(') { Pop_SeqStack(s); i++; continue; } else if(test[i]==']'&&s->data[s->top]=='[') { Pop_SeqStack(s); i++; continue; } else if(test[i]=='}'&&s->data[s->top]=='{') { Pop_SeqStack(s); i++; continue; } else break; } //防止不是因为扫描完而退出循环 if(Empty_SeqStack(s)&&test[i]=='\0') printf("match!\n"); else printf("don't match!\n");}

#main函数部分

int main(){ int i=0; SeqStack *s; datatype test[20]; Init_SeqStack(&s); puts("please input the brackets you want test:"); scanf("%s",test); Match_SeqStack(s,test); return 0;}

这是我的第一篇blog 目前还在学习阶段 希望能通过写博客来总结学习过程中的错误，经验 并且可以帮助到更多的初学者

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。