数据结构实验表达式括号匹配配对判断问题解析.docx

《数据结构实验表达式括号匹配配对判断问题解析.docx》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、实验表达式括号匹配配对判断问题姓名：班级：学号：实验时间：1.问题描述一个算术表达式含圆括号、中括号、花括号，且它们可任意嵌套使用。写一程序，判断任一算术表达式中所含括号是否正确配对。2.数据结构设计匹配判别发生在右括号出现时，且被匹配的左括号应是距离右括号最近被输入的，二不是最先被输入的括号,即“先入后匹配”。因此用栈来解决。#definestacksize100〃定义栈的空间大小structstack{//定义栈的结构体charstrstack[stacksize];//定义栈的存储格式为字符型inttop;//定义栈的栈顶变量}；void

2、InitStack(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;ch

3、ara=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

4、);intstrn=strlen(str);〃定义字符串长度为strnfor(inti=0;i

5、ak;case']':if(Pop(s)!='[')return0;break;}}intre=0;//定义并初始化判空函数的返回值re=Empty(s,re);〃返回判空函数的返回值if(re==1)return1;//栈为空elsereturn0;//栈不为空，有左括号，存在‘('或'['或'{'未匹配}4.运行与测试①输入1+(2+3)C:Windowssystem32cmd,exe:小于工豳的字符串;1+(2+3>-配，请按任意键继续...②输入1+(2+3))39C:Windowssysteinn32cmd.exe:小于1

6、皿的字符串;不匹配！！清按任意键继续..kin③输入1+((2+3)④输入1+2+3+4C:Windowssysteinn32cmd.exe请输入一个长度小于i照的字符串;1*2+3*4匚酎」请按任意键继续...次狗拼音输入法半：⑤输入1+[2+(4-2])*2意腱继续搜狗拼音输入法C:Windowssystem32cmd.exe5.调试记录及收获在运行程序时，当输入1+((2+3)时，因为错把‘(‘写成‘(‘，也就是输入法的中英文没有切换，所以得到的结果是错的。这就说明输入时要注意中英文。通过本次实验，我对栈的使用更加熟练，入栈出

7、栈的顺序也有了更步的了解。附：源代码#include"stdafx.h"#include#include#includeusingnamespacestd;定义栈的空间大小#definestacksize100//structstack{//定义栈的结构体charstrstack[stacksize];//定义栈的存储格式为字符型inttop;//定义栈的栈顶变量}；voidInitStack(stack&s){//定义一个新栈s,初始化栈顶为-14.top=-1;}charPush(s

8、tack&s,chara){//入栈操作，将字符a入栈sif(s.top==stacksize-1)//当栈顶为栈的空间大小-1,栈满return0;