逆波兰表达式实验报告.docx

数据结构实验报告HUNAN UNIVERSITY课程实习报告题目 长浮点型逆波兰表达式求值学生姓名 毛宇锋 吴淑珍 王小玉学生学号 16 20 22专业班级 信息安全一班指导老师 夏艳 刘炜完 成 日 期 2014.4.8 6 一、 需求分析读入一个后缀表达式，利用堆栈来计算该表达式的值，同时要效验后缀表达式是否正确。二、概要设计抽象数据类型为实现上述程序的功能，应以数据元素为长浮点型的栈来存储用户的输入，以及计算出的结果。算法的基本思想由于读入屏幕的字符，所以第一步是区分字符代表数值还是运算符，此外，还应该对字符是否为小数点做一个特别的判断。当确定系统读入的是数值时，应以double型将数值压入栈中，当确定读入的是运算符时，首先判断当前栈中的数值是否够运算（即至少有两个元素在栈中），满足该条件后分别弹出栈顶的两个元素，然后对其进行系统要求的运算，重新压入栈中。程序的流程程序由三个模块组成：（1） 输入模块：循环输入字符，当遇到#号时结束（2） 计算模块：将输入的字符转化为相应的长浮点型数字并输出（3） 输出模块：显示最终计算结果三、详细设计物理数据类型设计的关键在于读取字符型并转化为长浮点型算法的具体步骤循环输入字符串1.判断当前的输入是否为数字，当结果为真时，执行字符串转换为长浮点型数的函数；2.判断是否为操作符，并给定每一个操作符返回相应的计算结果。算法的时空分析由于在循环内的操作都为时间复杂度为(1)的，故算法的时间复杂度取决于输入字符的多少，令输入的字符为n时，算法的时间复杂度应该为(n)。空间复杂度：给定栈的大小为10，即允许最多压入十个元素而不进行任何运算，由于逆波兰表达式通常最多输入两个元素即进行一次运算，所以栈的大小至少为2，这里给定10在空间的开销也很小。输入和输出的格式输入：在字符界面上输入一个后缀表达式，其中两相邻操作数之间利用空格隔开。以“#”表示结束。输出：如果该后缀表达式正确，那么在字符界面上输出其结果，计算结果小数点后面保留两位有效数字，如果不正确，请在字符界面上输出表达式错误提示。五、测试结果为了验证测试具有普遍性，分别用个位整数、个位小数、多位整数、多位小数进行运算，如输入：4 0.2 + 10 * 3.6 3 /即计算(4+0.2)*10-3.6)/3结果应该等于12.8下图为程序运行结果：六、用户使用说明1、本程序的运行环境为DOS操作系统，3（2）.cpp 2、运行程序时输入的数字应以空格隔开，以#号结束输入七、实验心得为了实现浮点型逆波兰表达式的运算，先后思考了很多种方法，最后发现令输入为字符串并将其通过一个函数更改为double型数字是比较好的一个思路，通过实验也对string操作进行了复习，但是程序也有一定的限制，比如不能输入超过16位的数据。七、附录主程序及注释：#include#include#include#includeusing namespace std;templateclass stackprivate:int maxSize;int top;E *listArray;public:stack(int size = 10)maxSize = size ;top = 0;listArray = new Esize;stack()delete listArray;void push(const E& it)assert(top !=maxSize,Stack is full); listArraytop+= it;E pop()assert(top !=0,Stack is empty);return listArray-top;const E& topValue() constassert(top!=0);return listArraytop-1;int length() constreturn top;bool isNum(char c) /判断该字符是否为数字if (c=0 & c=9)return true;elsereturn false;bool isOperator(char c) /判断该字符是否为运算符if (c=+|-|*|/)return true;else return false;double operation(double num1,double num2,char c) /对于给定的运算符将他变成相应的数字switch(c) case +:return num1+num2; case -:return num2-num1;case *:return num2*num1;case /:return num2/num1;double switchNum(char c) /将输入的数字串变成对应的数字int size=strlen(c);char* ptr=strchr(c,.);double num=0,n=0;int i=0;if(ptr) for(i=0;iptr-c;i+) num=num*10+ci-48; for(i=ptr-c+1;isize;i+) n=n*10+ci-48; num+=n*pow(10,-(size-(ptr-c)+1); else for(i=0;isize;i+) num=num*10+ci-48; return num;void main()stack a;char c16;double num,num1,num2;while(cinc)if(c0=#)break; /遇到#时结束程序if(isNum(c0)num=switchNum(c);a.push(num);num=0;else if(isOperator(c0) /当判定操作