数据结构实验-栈的基本运算

*******************************实验题目：栈的基本运算实验者信息：班级13007102，姓名庞文正，学号1300710226实验完成的时间3：00******************************一、实验目的1，掌握栈的各种存储结构及基本运算的实现。2，掌握堆栈后进先出的运算原则在解决实际问题中的应用。3，复习c语言中相关语句及函数的用法。二、实验内容括号配对检查。试设计一个程序对任意输入的语句或数学表达式，判断其括号是否匹配。若匹配，则返回1，否则返回0。调试程序并对相应的输出作出分析；修改输入数据，预期输出并验证输出的结果。加深对算法的理解。三、算法设计与编码1.本实验用到的理论知识总结本实验用到的理论知识，实现理论与实践相结合。总结尽量简明扼要，并与本次实验密切相关，最好能加上自己的解释。2.算法概要设计给出实验的数据结构描述，程序模块、功能及调用关系首先建立一个栈结构，且初始化栈为空。然后由键盘上随即输入一个带括号的语句或带括号的数学表达式，同时将它们保存在一个字符型数组exps[]中。扫描表达式exps,当遇到“(”、“[”、“{”时，将其入栈。遇到“）”、“]”、“}”时，判断栈顶是否有相匹配的括号。若没有，则退出扫描过程，返回0，否则直到exps扫描完毕为止。若top为0，则返回1。#includestdio.h#defineMAXSIZE100#defineTRUE1#defineFALSE0typedefintdatatype;typedefstruct//顺序栈的结构体定义{datatypestack[MAXSIZE];inttop;}seqstack;voidsetnull(seqstack*s)//置空栈-由于c语言的数组下标是从0开始的，所以置{s-top=-1;}//{s-top=-1;}空栈操作时将栈顶指针放在下标为0之前，即-1处。intempty(seqstack*s)/*判断当前栈是否为空栈*/{if(s-top0)returnTRUE;elsereturnFALSE;}intpush(seqstack*s,datatypex)/*把元素x压入栈s中*/{if(s-top=MAXSIZE-1){printf(stackoverflow!\n);/*发生上溢*/returnFALSE;}else{s-stack[++s-top]=x;/*栈顶指针上移，数据元素入栈*/returnTRUE;}}datatypepop(seqstack*s)/*弹出当前栈s的栈顶元素*/{if(s-top0){printf(stackempty!\n);/*栈空，返回空值*/return-1;}else{s-top--;return(s-stack[s-top+1]);}//由于return语句的特点，必须先使top减1，然后再执行return语句。而此}//时栈顶元素的表示应该为s-top+1.intjudge(seqstack*s)//括号匹配检查算法。--遇到(、[、{时,{//将其压栈s中。datatypesymb,ch,store;push(s,'#');symb=getchar();/*从键盘接受字符*/while(symb!='#'){switch(symb){case'(':case'[':case'{':push(s,symb);break;case')':ch=pop(s);if(ch!='(')returnFALSE;break;case']':ch=pop(s);if(ch!='[')returnFALSE;break;case'}':ch=pop(s);if(ch!='{')returnFALSE;break;default:;}symb=getchar();}if(pop(s)=='#')returnTRUE;elsereturnFALSE;}intjinzhishuchu(seqstack*s){intx,symb;scanf(%d,&symb);/*从键盘接受字符*/while(symb!=0){push(s,symb%8);symb=symb/8;}while(!empty(s)){x=pop(s);//出栈操作printf(%d,x);//依次输出出栈结果}printf(\n);}main(){seqstackq;setnull(&q);printf(pleaseinputanexpressendwithsymbol'#':\n);if(judge(&q))printf(yes\n);/*括号匹配，则输出yes*/elseprintf(no\n);/*括号不匹配，则输出no*/jinzhishuchu(&q);}四、运行与测试（1）在调试程序的过程中遇到什么问题，是如何解决的？答：遇到很多括号不匹配（2）设计了那些测试数据？测试结果是什么？（3）程序运行的结果如何？成功运行！1、预习思考题调试好上述程序后，试着完成以下拓展内容：（1）假定表达式不是通过getchar()函数一个个传送的，而是存放在一个字符数组A[n]中，程序需要做哪些改变？将while改为for（i=0;i=strlen(A[n]);i++）{switch(A[i]){case'(':case'[':case'{':push(s,symb);break;case')':ch=pop(s);if(ch!='(')returnFALSE;break;case']':ch=pop(s);if(ch!='[')returnFALSE;break;case'}':ch=pop(s);if(ch!='{')returnFALSE;break;default:;}}（2）在judge()函数中，如果不用switch()函数，你会怎么处理？用if替代if(symb=='('||symb=='{'||symb=='['){push(s,symb);}if(symb==')'){ch=pop(s);if(ch!='(')returnFALSE;}if(symb=='}'){ch=pop(s);if(ch!='{')returnFALSE;}if(symb==']'){ch=pop(s);if(ch!='[')returnFALSE;}2、分析讨论题：数制转换问题是栈应用的一个典型实例。将十进制数转换成其它进制的数有一种简单的方法：例：十进制转换成八进制：(66)10=(102)866/8=8余28/8=1余01/8=0余1结果为余数的逆序:102。如果用栈的算法来实现，怎样实现？其基本原理是什么？intjinzhishuchu(seqstack*s)//括号匹配检查算法。--遇到(、[、{时,{intx,symb;scanf(%d,&symb);/*从键盘接受字符*/while(symb!=0){push(s,symb%8);symb=symb/8;}while(!empty(s)){x=pop(s);//出栈操作printf(%d,x);//依次输出出栈结果}printf(\n);}五、总结和心得实验完成后的总结和思考。此次实验很顺利！