数据结构实验-表达式括号匹配配对判断问题

实验表达式括号匹配配对判断问题姓名：班级：学号：实验时间：1.问题描述一个算术表达式含圆括号、中括号、花括号,且它们可任意嵌套使用。写一程序，判断任一算术表达式中所含括号是否正确配对。2.数据结构设计匹配判别发生在右括号出现时，且被匹配的左括号应是距离右括号最近被输入的，二不是最先被输入的括号，即“先入后匹配”。因此用栈来解决。#definestacksize100//定义栈的空间大小structstack{//定义栈的结构体charstrstack[stacksize];//定义栈的存储格式为字符型inttop;//定义栈的栈顶变量};voidInitStack(stack&s){//定义一个新栈s，初始化栈顶为-1s.top=-1;}3.算法设计（1）入栈的算法charPush(stack&s,chara){//入栈操作，将字符a入栈sif(s.top==stacksize-1)//当栈顶为栈的空间大小-1，栈满return0;s.top++;//入栈操作一次，栈顶+1s.strstack[s.top]=a;//此时，栈顶元素为字符areturna;}（2）出栈的算法设计charPop(stack&s){//出栈操作if(s.top==-1)//当栈顶为-1时，栈空return0;chara=s.strstack[s.top];//将栈顶元素赋予字符a，并返回字符a，完成出栈操作s.top--;returna;}（3）判断栈是否为空的函数intEmpty(stack&s,intre){//定义判断栈是否为空的函数if(s.top==-1)return1;//栈为空时返回值为1elsereturn0;//栈不为空时返回值为0}（4）判断是否匹配的算法。如果右括号，进栈，取下个字符；如果是左括号，出栈，取下个字符；最后判断栈是否为空。intCheck(char*str){//检验括号是否匹配的函数stacks;InitStack(s);intstrn=strlen(str);//定义字符串长度为strnfor(inti=0;istrn;i++){chara=str[i];intre=0;switch(a){//对输入的字符a进行判断case'(':case'{':case'[':Push(s,a);//若是左括号，则进行入栈操作break;//若是右括号，则进行出栈操作，若出栈元素不是与输入相对应的左括号，则字符串括号中不匹配，返回case')':if(Pop(s)!='(')return0;break;case'}':if(Pop(s)!='{')return0;break;case']':if(Pop(s)!='[')return0;break;}}intre=0;//定义并初始化判空函数的返回值re=Empty(s,re);//返回判空函数的返回值if(re==1)return1;//栈为空elsereturn0;//栈不为空，有左括号，存在'('或'['或'{'未匹配}4.运行与测试①输入1+(2+3)②输入1+(2+3))③输入1+（（2+3）④输入1+2+3+4⑤输入1+[2+(4-2])*25.调试记录及收获在运行程序时，当输入1+((2+3)时，因为错把’(’写成’（’，也就是输入法的中英文没有切换，所以得到的结果是错的。这就说明输入时要注意中英文。通过本次实验，我对栈的使用更加熟练，入栈出栈的顺序也有了更一步的了解。附：源代码#includestdafx.h#includeiostream#includestdio.h#includestring.husingnamespacestd;#definestacksize100//定义栈的空间大小structstack{//定义栈的结构体charstrstack[stacksize];//定义栈的存储格式为字符型inttop;//定义栈的栈顶变量};voidInitStack(stack&s){//定义一个新栈s，初始化栈顶为-1s.top=-1;}charPush(stack&s,chara){//入栈操作，将字符a入栈sif(s.top==stacksize-1)//当栈顶为栈的空间大小-1，栈满return0;s.top++;//入栈操作一次，栈顶+1s.strstack[s.top]=a;//此时，栈顶元素为字符areturna;}charPop(stack&s){//出栈操作if(s.top==-1)//当栈顶为-1时，栈空return0;chara=s.strstack[s.top];//将栈顶元素赋予字符a，并返回字符a，完成出栈操作s.top--;returna;}intEmpty(stack&s,intre){//定义判断栈是否为空的函数if(s.top==-1)return1;//栈为空时返回值为1elsereturn0;//栈不为空时返回值为0}intCheck(char*str){//检验括号是否匹配的函数stacks;InitStack(s);intstrn=strlen(str);//定义字符串长度为strnfor(inti=0;istrn;i++){chara=str[i];intre=0;switch(a){//对输入的字符a进行判断case'(':case'{':case'[':Push(s,a);//若是左括号，则进行入栈操作break;//若是右括号，则进行出栈操作，若出栈元素不是与输入相对应的左括号，则字符串括号中不匹配，返回case')':if(Pop(s)!='(')return0;break;case'}':if(Pop(s)!='{')return0;break;case']':if(Pop(s)!='[')return0;break;/*case')':if(Empty(s,re)||Pop(s)!='(')return0;Pop(s);break;case']':if(Empty(s,re)||Pop(s)!='[')return0;Pop(s);break;case'}':if(Empty(s,re)||Pop(s)!='{')return0;Pop(s);break;*/}}intre=0;//定义并初始化判空函数的返回值re=Empty(s,re);//返回判空函数的返回值if(re==1)return1;//栈为空elsereturn0;//栈不为空，有左括号，即存在'('或'['或'{'未匹配}voidmain()//主函数{charstr[100];//定义一个单字符型数组以储存键盘输入的字符串。cout请输入一个长度小于100的字符串：endl;cinstr;//从键盘输入字符存储到字符数组中，有输入则继续。intre=Check(str);if(re==1)cout匹配！endl;elseif(re==0)cout不匹配！！endl;}