判断算术表达式中的括号是否配对

南京信息工程大学数据结构实验（实习）报告实验（实习）名称顺序表、单链表实验（实习）日期2015-10-11得分指导教师顾韵华系计软院专业计科年级2014级班次2一、实验目的1、掌握栈的顺序实现、栈的基本应用二、实验内容1、给出栈的顺序存储的定义及程序实现。2、应用顺序栈，编程实现由十进制到十六进制的转换。3、设计一个算法，编写程序实现：判断一个算术表达式中的括号是否配对，并求出括号的最大嵌套层数。三、数据结构设计和实现1.进制转换#includestdlib.h#includemalloc.h#defineSTACK_INIT_SIZE100#defineSTACKINCREMENT10//常量定义#defineOK1#defineERROR0#defineOVERFLOW-2#defineTrue1#defineFalse0//函数返回值定义typedefintStatus;typedefintSElemType;typedefstruct{SElemType*base;SElemType*top;intstacksize;}SqStack;StatusInitStack(SqStack&s);//构造一个空栈StatusDestroyStack(SqStack&s);//销毁栈StatusClearStack(SqStack&s);//把s置为空栈StatusStackEmpty(SqStacks);intStackLength(SqStacks);//返回栈的元素个数StatusGetTop(SqStacks,SElemType&e);//返回栈顶元素StatusPush(SqStack&s,SElemTypee);//插入元素为新的栈顶元素StatusPop(SqStack&s,SElemType&e);//取出栈顶元素StatusStackTraverse(SqStacks,Status(*vist)());voidconversion(intx);//十进制转换十六进制intfun(inty);//判断栈内元素//函数实现#includestack.h#includestdio.hStatusInitStack(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;}StatusGetTop(SqStacks,SElemType&e)//读取栈顶元素{if(s.top==s.base)returnERROR;e=*(s.top-1);returnOK;}StatusPush(SqStack&s,SElemTypee)//压栈{if(s.top-s.base=s.stacksize){s.base=(SElemType*)realloc(s.base,(s.stacksize+STACKINCREMENT)*sizeof(SElemType));if(!s.base)exit(OVERFLOW);s.top=s.base+s.stacksize;s.stacksize+=STACKINCREMENT;}*s.top++=e;returnOK;}StatusPop(SqStack&s,SElemType&e)//删除栈顶元素{if(s.top==s.base)returnERROR;e=*--s.top;returnOK;}voidconversion(intx)//进制转换{SqStacks;inte;InitStack(s);while(x){Push(s,x%16);x=x/16;}while(!StackEmpty(s)){Pop(s,e);fun(e);}printf(\n);}intfun(inty){if(y=10&&y=15)printf(%c,55+y);elseprintf(%d,y);return0;}StackEmpty(SqStacks){returns.top==s.base;}//主函数#includestack.h#includestdio.h#includestdlib.h#includemalloc.hintmain(){intn;while(printf(请输入要转换的数字:)!=EOF){scanf(%d,&n);conversion(n);}return0;}2.括号配对#includestdlib.h#includemalloc.h#defineSTACK_INIT_SIZE100#defineSTACKINCREMENT10//常量定义#defineOK1#defineERROR0#defineOVERFLOW-2#defineTrue1#defineFalse0//函数返回值定义typedefintStatus;typedefcharSElemType;typedefstruct{SElemType*base;SElemType*top;intstacksize;}SqStack;StatusInitStack(SqStack&s);//构造一个空栈StatusDestroyStack(SqStack&s);//销毁栈StatusClearStack(SqStack&s);//把s置为空栈StatusStackEmpty(SqStacks);intStackLength(SqStacks);//返回栈的元素个数StatusGetTop(SqStacks,SElemType&e);//返回栈顶元素StatusPush(SqStack&s,SElemTypee);//插入元素为新的栈顶元素StatusPop(SqStack&s,SElemType&e);//取出栈顶元素StatusStackTraverse(SqStacks,Status(*vist)());voidmatching(char*exp);//判断是否配对//函数实现#includematching.h#includestdio.hStatusInitStack(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;}StatusGetTop(SqStacks,SElemType&e){if(s.top==s.base)returnERROR;e=*(s.top-1);returnOK;}StatusPush(SqStack&s,SElemTypee){if(s.top-s.base=s.stacksize){s.base=(SElemType*)realloc(s.base,(s.stacksize+STACKINCREMENT)*sizeof(SElemType));if(!s.base)exit(OVERFLOW);s.top=s.base+s.stacksize;s.stacksize+=STACKINCREMENT;}*s.top++=e;returnOK;}StatusPop(SqStack&s,SElemType&e){if(s.top==s.base)returnERROR;e=*--s.top;returnOK;}StatusStackEmpty(SqStacks){returns.base==s.top;}voidmatching(char*exp){//检验表达式中所含括弧是否正确嵌套，若是，则返回OK，否//则返回ERROR;表达式存放于字符数组exp中intstate=1;//状态变量SqStacks;InitStack(s);//建一个空栈char*p;p=exp;//定义一个指针指向字符数组chare;intn=0,max=0;while(*p!='\0'&&state)//表达式未结束且未判断出不匹配{switch(*p){//依当前字符进行处理case'[':case'(':{Push(s,*p);//左括号压栈n++;//计数变量增加if(nmax)max=n;p++;break;}case']':{if(StackEmpty(s))//如果栈空{state=0;printf(右括号比左括号多!\n);exit(0);}//不匹配else{GetTop(s,e);//读取栈顶元素至eif(e=='('){Pop(s,e);n--;p++;}//左括号出栈else{state=0;printf(括号顺序不对!\n);exit(0);}}break;}case')':{if(StackEmpty(s))//如果栈空{state=0;printf(右括号比左括号多!\n);exit(0);}//不匹配else{GetTop(s,e);//读取栈顶元素至eif(e=='('){Pop(s,e);n--;p++;}//左括号出栈else{state=0;printf(括号顺序不对!\n);exit(0);}}break;}default:p++;}}if(state&&StackEmpty(s)){printf(括号配对!\n);printf(最大嵌套层数为：%d\n,max);}elseprintf(左括号比右括号多!\n);}//主函数#includematching.h#includestdio.h#includestdlib.h#includemalloc.hintmain(){inti=0;charline[100];printf(请输入字符串：);scanf(%s,line);matching(line);return0;}四、程序调试1、进制转换操作结果：2、括号配对操作结果；3、实验过程中遇到的问题：（1）进制转换时不能把大于10的数字转换成字母解决方法：重新写了一个判断函数（2）括号配对时不能结束循环，break的位置加不正确解决方法：认真阅读程序，判断到底要在哪里结束循环五、实验总结通过这次实验，我对栈的理解更加透彻，也学会了进制转换和括号配对的方法。在写进制转换的程序的时候我在调用函数的时候出现了错误，我在主函数中输出最终结果就不可以，然后我把输出写在了被调函数里，运行正确了。在写括号配对的时候一开始只能输出正确配对的情况，然后我改了判断条件就运行正确了。