括号匹配问题

《括号匹配问题》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、实验报告括号匹配问题、一、实验目的：1、熟练掌握数据结构基本知识；2、通过括号匹配的实验，了解栈的表示和栈的基本操作，掌握栈“后进先出”的特性并能够应用这一特性。二、实验工具：C-Free三、实验内容：设表达式中包含三种括号：圆括号、方括号和花括号，它们可互相嵌套，如([{}])或（{([][()])}）等均为正确格式，而（{[]）、{[()]或([]}等均不正确。在算法中可设置一个栈，每读入一个括号，若是左括号，则直接入栈，等待相匹配的同类右括号；若读入的是右括号，且与当前栈顶的左括号同类型，则二者匹配将栈顶的左括号出栈，否则属于不合法情况。另外，如果输入序列已读完，而栈

2、中仍有等待匹配的左括号，或者读入了一个右括号，而栈中已无等待匹配的同类型的左括号，均属不合法情况。当输入序列和栈同时为空时，说明所有括号完全匹配。四、实验过程：#include#include#defineSTACKINCREAMENT10#defineSTACK_INIT_SIZE100#defineOVERFLOW-2#defineOK1#defineERROR0typedefintstatus;typedefcharSElemtype;typedefstruct{SElemtype*base;SElemtype*top;statu

3、sstacksize;}sqstack;statusInit(sqstack*s){s->base=(SElemtype*)malloc(STACK_INIT_SIZE*sizeof(SElemtype));if(!s->base)exit(OVERFLOW);s->top=s->base;s->stacksize=STACK_INIT_SIZE;returnOK;}statuspush(sqstack*s,SElemtypee){if(s->top-s->base>=s->stacksize){s->base=(SElemtype*)realloc(s->base,(s-

4、>stacksize+STACKINCREAMENT)*sizeof(SElemtype))if(!s->base)exit(OVERFLOW);s->top=s->base+s->stacksize;s->stacksize+=STACKINCREAMENT;}*s->top++=e;returnOK;}statuspop(sqstack*s,SElemtype*e){if(s->top==s->base)returnERROR;*e=*--s->top;returnOK;}statusstackempty(sqstack*s){if(s->top==s->base)re

5、turnOK;returnERROR;}statusParenthesis_match(sqstack*s,char*str){inti=0,flag=0;SElemtypee;while(str[i]!=''){switch(str[i]){case'(':push(s,str[i]);break;case'[':push(s,str[i]);break;case')':{pop(s,&e);if(e!='(')flag=1;}break;case']':{pop(s,&e);if(e!='[')flag=1;}break;default:break;}if(flag

6、)break;i++;}if(!flag&&stackempty(s))printf("括号匹配成功!");elseprintf("括号匹配失败!");returnOK;}intmain(){charstr[100],enter;sqstacks;Init(&s);printf("请输入字符串:");scanf("%s",str);scanf("%c",&enter);Parenthesis_match(&s,str);return0;}实验结果：