实验二___栈与队列的一个应用.docVIP

中国计量学院实验报告 实验课程：《算法与数据结构》 实验名称：栈与队列的一个应用 班 级： 14计算机1 实验日期： 实验角色 Document Writer Programmer Tester 学号 1400303107 1400303105 140303111 姓名 张峰 朱沈辉 李佳骏 实验成绩 实验目的及要求： 一、 实验目的 1、了解栈和队列的特性 2.?掌握栈和队列的顺序表示及实现 3.?掌握栈和队列的链式表示及实现 4、学会利用栈或队列去求解实际问题 二、 实验要求 从键盘输入包括任意三种括号（即，圆括号()、方括号[]和花括号{}）的四则运算（+、-、*、/）表达式，编程判断该表达式的括号是否匹配。若匹配则计算出表达式的值；若不匹配，则输出“此表达式括号不匹配”。 实验中，假设: (1) 除括号不匹配外，不存在其它非法表达式的情况 (2) 表达式中只出现数值常量，不出现变量或符号常量 三、实验角色 1、Document Writer: ADT设计及实验所涉资料的整理、录入及排版 2、Programmer: 算法设计及实现 3、Tester: 确定测试用例并负责程序测试，测试用例不少于15种 数据结构及关键算法说明 这一部分描述解决问题所用到的数据结构及关键算法，可用伪代码、代码或框图表示，目的是让读者在短时间内清楚地理解作者解决问题的整体思路。因此，表达方式必须比源代码更通俗易懂。 typedef struct SqStack //栈的顺序存储结构 { SElemType *base; SElemType *top; int stacksize; }SqStack; char Precede(char a1 ,char a2)//判定运算符的优先级。 { char r; switch(a2) { case+: //此处由于加减几乎优先级一样，故放在一起 case-: if(a1==(||a1==[||a1=={||a1==#) r=; else r=; break; case(: if(a1==)) { cout括号匹配错误!endl; exit(-1); } else r=; break; }//这里只列举加减，左括号。其他类似。 bool In(char d)//判断c是否为十一种运算符之一 { switch(d) { case+: case-: return true; default: return false; } } SElemType EvaluateExpression() //算符表达式的优先算法。设OPTR和OPND分别为运算符栈和运算数栈 { while(c!=#||e!=#)//栈顶不是#号且输入不是#号 { if(In(c))//是符号则进栈 { switch(Precede(e,c)) { case: //栈顶元素优先级低 Push(OPTR,c); c=getchar(); break; case=: //脱括号并接受下一字符 Pop(OPTR,e); c=getchar(); break; case: //退栈并将运算结果入栈 Pop(OPTR,e); Pop(OPND,b); Pop(OPND,a); Push(OPND,Operate(a,e,b)); break; } } 测试用例表 紧扣实验要求，设计（并填写）一张测试用例表。每个测试用例一般应包括下列内容： 测试输入：设计一组输入数据； 测试目的：设计该输入的目的在于测试程序在哪方面可能存在漏洞； 预期输出：若程序正确，应该输出的结果； 实际输出：程序运行后，实际得到的输出结果； 错误原因：如果实际输出与预期输出不符，给出产生错误的可能原因； 当前状态： “通过” 或者“待修改” 两种状态之一。 【注意】测试时，不是提供简单的几组数据让程序容易通过，从而宣称该程序是正确的，而是精心设计“刁难”的数据，尽可能让程序暴露问题，这样才能真正帮助程序员完成正确的程序。 测试输入 预期输出 实际输出 错误原因 当前状态 (1+2*[1-2)/4]# error!括号匹配错误 error!括号匹配错误 通过 1+{2