括号匹配检验.doc

《括号匹配检验.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、括号匹配检验利用栈编写满足下列要求的括号匹配检验程序：假设表达式中允许包含两种括号：圆括号和方括号，其嵌套的顺序随意，即([]())或[([][])]等为正确的格式，[(]或([())或(()])均为不正确的格式。输入一个包含上述括号的表达式，检验括号是否配对。Input第一行：输入一个包含圆括号或方括号、不超过80个字符的表达式串。Output第一行：若输入表达式括号匹配，输出"matching";若不匹配，输出具体信息:"isn'tmatchedpairs",或"lackofleftparenthesis"或"lackofrightparenthesis"ty

2、pedefcharSElemType;#include"malloc.h"#include"stdio.h"#include"math.h"#include"process.h"//exit()#defineOK1#defineERROR0#defineTRUE1#defineFALSE0typedefintStatus;//Status是函数的类型,其值是函数结果状态代码，如OK等#defineSTACK_INIT_SIZE10//存储空间初始分配量#defineSTACKINCREMENT2//存储空间分配增量structSqStack{SElemType*b

3、ase;//在栈构造之前和销毁之后，base的值为NULLSElemType*top;//栈顶指针intstacksize;//当前已分配的存储空间，以元素为单位};//顺序栈StatusInitStack(SqStack&S){S.base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType));S.top=S.base;if(!S.base)returnERROR;S.stacksize=STACK_INIT_SIZE;returnOK;}StatusStackEmpty(SqStackS){if(S.bas

4、e==S.top)returnTRUE;elsereturnFALSE;}StatusPush(SqStack&S,SElemTypee){if(S.top-S.base>=S.stacksize){S.base=(SElemType*)realloc(S.base,(STACK_INIT_SIZE+S.stacksize)*sizeof(SElemType));if(!S.base)returnERROR;S.top=S.base+S.stacksize;S.stacksize=S.stacksize+STACK_INIT_SIZE;}*S.top=e;S.to

5、p++;returnOK;}StatusPop(SqStack&S,SElemType&e){if(S.base==S.top)returnERROR;e=*--S.top;returnOK;}voidcheck(){//对于输入的任意一个字符串，检验括号是否配对SqStacks;SElemTypech[80],*p,e;if(InitStack(s))//初始化栈成功{//printf("请输入表达式");scanf("%s",ch);p=ch;while(*p)//没到串尾switch(*p){case'(':case'[':Push(s,*p);p++;

6、break;//左括号入栈，且p++case')':case']':if(!StackEmpty(s))//栈不空{Pop(s,e);//弹出栈顶元素if(*p==')'&&e!='('

7、

8、*p==']'&&e!='[')//弹出的栈顶元素与*p不配对{printf("isn'tmatchedpairs");exit(ERROR);}else{p++;break;//跳出switch语句}}else//栈空{printf("lackofleftparenthesis");exit(ERROR);}default:p++;//其它字符不处理，指针向后移}if

9、(StackEmpty(s))//字符串结束时栈空printf("matching");elseprintf("lackofrightparenthesis");}}voidmain(){check();}