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

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