《数据结构》课程设计报告-实现对算术四则溷合运算表达式的求值以及大整数计算

江汉大学文理学院课程设计报告课程名称：设计题目：系别：专业：组别：学生姓名:起止日期:年月日~年月日指导教师:承诺书本人郑重声明：本人所呈交的学术论文，是本人在导师指导下独立进行研究工作所取得的成果。除文中已经注明引用的内容外，本论文不包括任何其他个人或集体已经发表或撰写过的作品成果。对本文的研究作出重要贡献的个人和集体，均已在文中以明确的方式标明。本人完全意识到本声明的法律结果由本人承担。学生（签名）：年月日《数据结构》课程设计报告题目：实现对算术四则混合运算表达式的求值以及大整数计算一．设计目的数据结构是计算机专业的核心课程，是一门实践性很强的课程。课程设计是加强学生实践能力的一个强有力手段，要求学生掌握数据结构的应用、算法的编写、类C语言的算法转换成C程序并上机调试的基本方法，还要求学生在完成程序设计的同时能够写出比较规范的设计报告。严格实施课程设计这一环节，对于学生基本程序设计素养的培养和软件工作者工作作风的训练，将起到显著的促进作用。二．问题描述(一)当用户输入一个合法的算术表达式后，能够返回正确的结果。能够计算的运算符包括：加、减、乘、除、括号；能够计算的操作数要求在实数范围内；对于异常表达式能给出错误提示。(二)求两个不超过200位的非负整数的和，积和商。三．调试与操作说明（一）需求分析本程序所做的工作为：能直接求出四则表达式的值，并输出；可以解决因数值位数太大unsigned类型都无法表示的大数之间的运算。本程序可用于小学教师对学生作业的快速批改以及对数值位数要求较大的科学运算。此程序规定：1.程序的主要功能包括两部分：表达式求解和大整数的运算。2.表达式求解中输入的必需为一个正确的四则表达式，可以是整型也可以为浮点型，比如：3*(7-2)+5和3.154*(12+18)-23。大整数的运算中根据提示要输入两行数据位数不能大于200位。3.程序的输出：表达式求解中为一浮点型数据，大整数运算中输出的即为运算之后的结果，结果里不能有多余的前导0。（二）概要设计1.ADTLinkStack{数据元素：此链栈中的所有元素类型为字符型的数字字符数据关系：栈中数据元素之间是线性关系。基本操作:（1）InitStack(LinkStack&head)操作结果：构造一个空栈head（2）IsEmpty(LinkStackhead)初始条件：栈head已存在操作结果：若栈为空栈，则返回TRUE,否则FALSE（3）Push(LinkStack&head,ElementTypeelement)初始条件：栈head已存在操作结果：插入元素element为新的栈顶元素（4）Pop(LinkStack&head,ElementType&element)初始条件：栈head已存在且非空操作结果：删除head的栈顶元素，并用e返回其值（5）GetTop(LinkStackhead,ElementType&element)初始条件：栈head已存在并且非空操作结果：用e返回head的栈顶元素（6）DestroyStack(LinkStack&head)初始条件：栈head已存在操作结果：栈head被销毁}ADTLinkStack2．ADTLinkCharStack{数据对象D：元素类型为字符型的符号字符数据关系R：基本操作：栈中数据元素之间是线性关系。（1）CInitStack(LinkCharStack&head)（2）CIsEmpty(LinkCharStackhead)（3）CPush(LinkCharStack&head,ElementTypeelement)（4）CPop(LinkCharStack&head,ElementType&element)（5）CGetTop(LinkCharStackhead,ElementType&element)（6）CDestroyStack(LinkCharStack&head)}ADTLinkCharStack系统中子程序及功能要求：（1）add():计算两个不大于200位的大整数的和，此文件包含于头文件calculator.h中。（2）multiply()：实现两个大整数的积的运算，此文件也包含于头证件calculator.h中。（3）Comop(charch)：判断输入的字符是否为运算符（4）charPrecede(charch,charc)：比较两个运算符的优先级，ch是栈顶字符，c是表达式字符。（5）ElementTypeOperate(ElementTypea,charch,ElementTypeb)：解析表达式中的双目运算，其返回的结果即为双目运算表达式的值。（6）interror(char*str)：错误提示函数，实现对多种非法四则表达式的判断，并给出提示，让用户更正自己的输入错误。（7）voidMenuPrint()：主菜单打印函数。（8）voidsubmenu()：大整数运算功能模块的子菜单。（9）voidClear()：清屏函数。（10）ElementTypeEvaluateExpression(char*exp)：这是此程序的核心函数，可以综合其它子函数，实现最终的表达式求解。各程序模块之间的调用关系（子程序编号见上）：主函数可调用子程序1，2，7，8，9，10。子程序10可调用子程序3，4，5，6。3．详细设计表达式计算核心算法的思想及伪代码：此算法的基本思想：首先置操作数栈OPND为空栈，表达式起始符“#”为运算符的栈底元素；依次读入表达式中每个字符，若是操作数则进栈，若是运算符则和OPTR栈的栈顶运算符比较优先权作相应操作，直至整个表达式求值完毕（即OPTR栈的栈顶元素和当前读入的字符均为“#”）此算法的伪代码：ElementTypeEvaluateExpression(char*exp){定义两个字符变量c和ch,c代表输入表达式中的字符，ch代表栈顶运算符;定义字符指针*p,*q,*temp;temp指向运算符后面的一个字符doublei=0,a=0,b=0;将传入的实参赋给p,q;定义一个运算符栈OPTR;定义一个操作数栈OPND;调用函数InitStack()初始化栈OPND;调用函数InitCharStack()初始化栈OPNR;调用函数CPush(OPTR,'#')将#压入运算符栈;c=*p;temp=p;p++;if(第一个字符就为‘-’){c=*p;temp=p;p++;}while(栈不为空或表达式没有结束){//进入最外层循环if(不是运算符)//则解析数字字符串然后进操作数栈{整数部分m=0;小数部分n=0;while(没有遇到小数点并且为数字字符){解析整数部分m}if(遇到小数点){解析小数部分c=*p;将p指针移到第一个出现的字符;将q指针指向小数的最后一位;while(p指针不指向’.’){将p指向的字符转为小数np--;}p=q;p++;}if(运算符为‘-’并且运算符前一个为‘（’或者为表达式的开始)调用Push(OPND,-(m+n))将m+n的相反数入栈;else调用Push(OPND,m+n)将m+n入栈;}数字进栈结束else//是运算符时则进栈OPTR{if(运算符为‘-’&&运算符前一个为‘（’){c=*p;temp=p;p++;}else{调用函数CGetTop(OPTR,ch)得到OPTR的栈顶元素;switch(调用函数Precede(ch,c)判断栈顶元素与接收的字符的优生级别){case栈顶运算符优先权低:调用函数CPush(OPTR,c)将c入运算符栈;接收下一个字符;case栈顶运算符优先权高：运算符出栈得到ch;数字栈连续出栈两次得到a,b;调用Operate(a,ch,b)并将结果入栈到数字栈;break;case优生权相等：脱括号并接收下一个字符;调用CPop(OPTR,ch)脱括号;接收下一个字符;default:接收下一个字符;}退出switch循环}//else1}//else2}//退出最外层while循环调用函数GetTop(OPND,i)得到栈顶元素i;将两个栈消毁;返回I;}EvaluateExpression函数结束实现大整数相加的add()函数的伪代码：voidadd(){输入两个要运算的大整数分别存在长度为MAX_LEN+10的字符串数组szline1和szline2中;循环计数变量i,j;调用库函数memeset()将地址an1开始的sizeof(an1)字节内容置成0;调用库函数memeset()将地址an2开始的sizeof(an2)字节内容置成0;将szline1中存储的字符串形式的整数转换到an1中去将szline1中存储的字符串形式的整数转换到an1中去for(i=0;i最大的长度;i++){an1[i]+=an2[i];如果(得到结果大于10){原位an1[i]-=10;高位an1[i+1]++即进位;}}//下面是无前导0地输出计算的结果;for(i=最大长度;i=0;i--){如果没有标记第一次出现过了0那么输出an1[i];否则如果an1[i]为0则输出an1[i];标记已经出现过0;}}实现大整数相加的add()函数的伪代码：voidmultiply(){输入两个要运算的大整数分别存在长度为MAX_LEN+10的字符串数组szline1和szline2中;循环计数变量i,j;调用库函数memeset()将地址an1开始的sizeof(an1)字节内容置成0;调用库函数memeset()将地址an2开始的sizeof(an2)字节内容置成0;调用库函数memeset()将地址aresult开始的sizeof(aresult)字节内容置成0。将szline1中存储的字符串形式的整数转换到an1中去将szline1中存储的字符串形式的整数转换到an1中去for(i=0;inlen2;i++){每一都用an1的一位，去和an2各位相乘//从an1的个位开始for(j=0;jnlen1;j++)用选定的an1的那一位，去乘an2的各位aresult[i+j]+=an2[i]*an1[j];两数第i,j位相乘，累加到结果的第i+j位}下面的循环统一处理进位问题for(i=0;iMAX_LEN*2;i++){if(aresult[i]=10){aresult[i+1]+=aresult[i]/10;aresult[i]%=10;}}输出结果和上一函数一样}4．测试分析按照附录中的测试数据，得出如下测试、分析结果：（1）表达式求解功能当我们输入表格中两个正确的四则表达式时程序能准确地求得其值：完全支持浮点数，正负数的运算;而当我们输入第三组错误的表达式时，程序能做出正确判断，提醒用给用户输入一个正确的表达式。其数据测试的情况见截图：表达式一运算结果由表一知结果正确。表达式二运算结果由表一知结果正确。表达式三运算出错情况（2）大整数加法功能输入两组不大于200位的大整数，能准确计算出结果其截图如下图所示：选择功能b（3）大整数乘法功能其测试截图如：第二组数据结果正确。5．使用说明1．运行程序，首先出现主菜单。主菜单包括四个选项：选项a：表达式求解，选择该项可进行四则表达式的求解；选项b：大整数运算，选择该项可进行不大于200位的大整数的加法和乘法运算（目前只支持加，乘）；选项c：清屏；选项d：退出程序，选择该项将退出程序。2．大整数运算界面包括4个选项：选项1：两个大整数相加；选项2：两个大整数相乘；选项3：返回上一级菜单，可返回主界面。选项4：直接退出本程序。6．附录（一）：测试数据组别表达式正确值112+（9-8）*7-（-6*5）4923.14*（67.305-65.305）+3.149.42312-（3-6*7）8-4无（表一）加法乘法整数11212121212121212121212121212121212121212121212121212121212121212121212121212整数111111111111111111