数据结构 |
您所在的位置：网站首页 › 判断表达式中括号是否匹配 › 数据结构 |
数据结构
|
《数据结构》严蔚敏版习题3.2.2，括号匹配问题。是顺序栈的课后习题。原问题：假设表达式中允许包括两种括号：圆括号和方括号，其嵌套方式随意，即（【】（））等都是正确的格式，【（】）是不正确的格式。设计一个算法检查输入的字符串中的括号是否是匹配的。 /-------------------------------------------------------------/ 思路：使用栈来解决，遇到（、【就入栈，遇到）、】且刚还能和栈顶元素匹配是就出栈，遇到其他元素不做处理。字符转中所有的元素都处理完后，查看栈的长度，若为空栈说明括号匹配，栈非空则说明括号不匹配。 所以需要一个可以存储字符元素的栈，以及匹配的各种方法： #include #include #define INITSIZE 100 #define INCRSIZE 10 #define ERROR 0 #define OK 1 typedef int Status; typedef struct { char *base; char *top; int size; }SqStack; Status InitStack(SqStack *s){ s->base=(char *)malloc(INITSIZE*sizeof(char)); if(!s->base){ return ERROR; } s->top=s->base; s->size=INITSIZE; return OK; } Status DestroyStack(SqStack *s){ if(!s->base){ exit(1); } free(s->base); s->base=NULL; } Status ClearStack(SqStack *s){ s->top=s->base; } Status StackEmpty(SqStack *s){ if(s->top==s->base){ return 1; }else{ return 0; } } int StackLength(SqStack *s){ return (s->top-s->base); } Status GetTop(SqStack s,char *e){ if(s.top==s.base){ return ERROR; } *e=*(s.top-1); return OK; } Status Push(SqStack *s,char e){ if(s->top-s->base>=s->size){ s->base=(char *)realloc(s->base,(s->size+INCRSIZE)*sizeof(char)); if(!s->base){ exit(1); } s->top=s->base+s->size; s->size+=INCRSIZE; } *(s->top)=e; s->top++; return OK; } Status Pop(SqStack *s,char *e){ if(s->top==s->base){ return ERROR; } *e=*(--s->top); return OK; } void StackTraverse(SqStack *s){ if(!s->base){ exit(1); } char *t=s->top-1; while(t>=s->base){ printf("%c",*t); t--; } }保存为stack.h的头文件： 然后是设计主函数的算法： 先画出算法流程图： 运行实验： (x+y)+[z-t*(8*7)] 当前栈长：0 括号匹配 -------------------------------- Process exited after 49.2 seconds with return value 0 请按任意键继续. . . /-------------------------------/ (]) 当前栈长：3 括号不匹配 -------------------------------- Process exited after 10.03 seconds with return value 0 请按任意键继续. . .代码运行正确。 |
实现代码：【本文地址】
今日新闻 |
推荐新闻 |