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

1、汪汉丈禽夂理禽浣课程设计扌艮告课程名称：设计题目：系另u： 专 业：组 别：学生姓名:起止日期：年 月 日年 月 日 指导教师：承诺书本人郑重声明：本人所呈交的学术论文，是本人在导师指导下独立进行研究工作所取得的成果。除文中已经注明引用的内容外，本论文不包括任何其他个人或集体已经发表或撰写过的作品成果o对本文的研究作出重要贡献的个人和集体，均已在文中以明确的方式标明。本人完全意识到本声明的法律结果由本人承担。学生（签名）:数据结构课程设计报告题目：实现对算术四则混合运算表达式的求值以及大整数计算一.设计目的数据结构是计算机专业的核心课程，是一门实践性很强的课程。课程设计是加强学生实践 能力的一

2、个强有力手段，要求学生掌握数据结构的应用、算法的编写、类c语言的算法转换 成c程序并上机调试的慕本方法，还要求学生在完成程序设计的同时能够写出比较规范的设 计报告。严格实施课程设计这一环节，对于学生基本程序设计素养的培养和软件工作者工作 作风的训练，将起到显箸的促进作用。二问题描述（一）当用八输入一个合法的算术表达式后，能够返回正确的结果。能够计算的运算 符包括：力口、减、乘、除、括号；能够计算的操作数要求在实数范围内；对于 异常表达式能给出错课提示。（二）求两个不超过200位的非负整数的和，积和商。三.调试与操作说明（一）需求分析本程序所做的工作为：能总接求出四则表达式的值，并输出；可以解决

3、因数值位数 太大unsigned类型都无法表示的大数z间的运算。本程序可用于小学教师对学生作业 的快速批改以及对数值位数要求较人的科学运算。此程序规定：1. 程序的主耍功能包括两部分：表达式求解和大整数的运算。2. 表达式求解中输入的必需为一个正确的四则表达式，可以是整型也可以为浮点型, 比如：3*（7-2） +5和3. 154*（12+18）-23。大整数的运算中根据提示要输入两行数 据位数不能人于200位。3. 程序的输出：表达式求解中为一浮点型数据，大整数运算中输出的即为运算z后 的结果，结果里不能有多余的前导0。（-）概要设计1. adt linkstack数据元素：此链栈中的所有元素

4、类型为字符型的数字字符 数据关系：栈中数据元素之间是线性关系。基本操作：(1) initstack(linkstack &head)操作结果：构造一个空栈head(2) isempty(linkstack head)初始条件：栈head已存在操作结果：若栈为空栈，则返冋true,否则false(3) push(linkstack &head, elementtype element)初始条件：栈head已存在操作结果：插入元素element为新的栈顶元素(4) pop(linkstack &head, elementtype &element)初始条件：栈hea

5、d已存在且非空操作结果：删除heed的栈顶元素，并用o返回其值(5) gettop(linkstack head, elementtype &element)初始条件：栈heod已存在并且非空操作结果：用e返回head的栈顶元素(6) destroystack(linkstack &head)初始条件：栈head已存在操作结杲：栈hoad被销毁adt linkstack2. adt linkcharstack数据对彖d：元素类型为字符型的符号字符数据关系r：基本操作：栈屮数据元素z间是线性关系。(1) cinitstack(linkcharstack &head)(2)

6、 cisempty(linkcharstack head)(3) cpush(linkcharstack &head, elementtype element)(4) cpop(linkcharstack &head, elementtype &element)(5) cgettop(linkcharstack head, elementtype &clcmont)(6) cdcstroystack(linkcharstack &head)adt linkcharstack系统中子程序及功能要求：(1) add():计算两个不大于200位的大整数的和，此

7、文件包含于头文件 calculator, h 屮。(2) multiplyo :实现两个大整数的积的运算，此文件也包含于头证件 calculator, h 中。(3)(4) 符,(5)comop (char ch)：判断输入的字符是否为运算符char precede (char ch, char c):比较两个运算符的优先级，ch是栈顶字 c是表达式字符。elementtype operate (elementtype a, char ch, elementtype b):解析表达式中的双目运算，其返冋的结果即为双日运算表达式的值。(6)int error (char *str):错误提示函数

8、，实现对多种非法四则表达式的判断,并给出提示,让用户更正自己的输入错误。(7)(8)(9)(10)void menuprint ():主菜单打印函数。void submenu ():大整数运算功能模块的子菜单。void clear 0 :清屏函数。elementtype evaluateexpression (char *exp)：这是此程序的核心函数,可以综合其它了函数，实现最终的表达式求解。 各程序模块之间的调用关系(子程序编号见上): 主函数可调用子程序1, 2, 7, 8, 9, 10o 子程序10可调用子程序3, 4, 5, 6o3.详细设计表达式计算核心算法的思想及伪代码：此算法的

9、基木思想：首先置操作数栈opnd为空栈，表达式起始符“常为运算符的栈底元素；依次读 入表达式屮每个字符，若是操作数则进栈，若是运算符则和optr栈的栈顶运算符比 较优先权作相应操作，直至整个表达式求值完毕(即optr栈的栈顶元索和当前读入 的字符均为“常) 此算法的伪代码：elomcnttypc evaluatoexpression(char *cxp)定义两个字符变量c和ch, c代表输入表达式中的字符，ch代表栈顶运算符；定义字符指针*p, *q, *temp; temp指向运算符后面的一个字符double i=0, a=0, b=0;将传入的实参赋给p,q；定义一个运算符栈optr;定义

10、一个操作数栈opnd;调用函数initstacko初始化栈opnd;调用函数initcharstacko初始化栈opnr ;调用函数cpush(optr,' #')将#压入运算符栈；c=*p;temp二p;p+;if(第一个字符就为)c=*p;temp=p;p+;while （栈不为空或表达式没有结朿）进入最外层循环if （不是运算符）则解析数字字符串然后进操作数栈整数部分沪0;小数部分n二0;wh订e （没冇遇到小数点并且为数字字符）解析整数部分hi if（遇到小数点）解析小数部分c=*p;将p指针移到第一个岀现的字符；将q指针指向小数的最后一位；while（p指针不指向二9

11、将p指向的字符转为小数np_；p=q;p卄；if（运算符为'-'并且运算符前一个为'（'或者为表达式的开始）调用push （opnd, - （m+n）将m+n的相反数入栈；else调用push （opnd, m+n）将m+n入栈；数字进栈结束else/是运算符时则进栈0ptrif（运算符为运算符前一个为'（）c 二*p;temp=p;p卄；else调用函数cgettop （optr, ch）得到0ptr的栈顶元素；switch （调用函数precede （ch, c）判断栈顶元素与接收的字符的优牛级别） case栈顶运算符优先权低：调用函数cpush （

12、optr, c）将c入运算符栈;接收下一个字符；case栈顶运算符优先权高：运算符出栈得到ch;数字栈连续出栈两次得到a,b ;调用operate (a, ch, b)并将结果入栈到数字栈;break; case优生权相等：脱括号并接收下一个字符；调用cpop(optr, ch)脱括号； 接收下一个字符；default:接收下一个字符；退岀switch循环/elsel/else2 /退出最外层wh il e循环调用函数get top (opnd, i)得到栈顶元素i;将两个栈消毁；返回i； eval uateexpression 函数纟吉朿 实现大整数相加的add()函数的伪代码：void a

13、dd()输入两个要运算的大整数分别存在长度为max_len+10的 字符串数组szlinel和szline2中;循环计数变量i,j;调用库函数memesei ()将地址an 1开始的sizeof (an 1)字节内容置成0; 调用库函数memeset ()将地址or)2开始的sizeof (an2)字节内容置成0; 将szlinel屮存储的字符串形式的整数转换到屮去 将szlinel中存储的字符串形式的整数转换到anl中去 for (i=0; i<最大的长度；i+)anli+=an2i;如果(得到结果大于10)原位 anl i-二 10;高位anl i+l+即进位；)/下面是无前导0地输

14、出计算的结果；for (i二最大长度;i>=0; i)如果 没有标记第一次出现过了0那么输岀anli;否则如果anli为0贝ij输出anli;标记已经出现过0;实现大整数相加的add()函数的伪代码: void multiply()输入两个要运算的大整数分别存在长度为max.len+10的字符串数组szlinel和szline2中；循环计数变量1, j；调用库函数memeset ()将地址an 1)|：始的sizcof (an 1)字节内容置成0; 调用库函数memeset ()将地址an2开始的sizeof (an2)字节内容置成0; 调用库函数memeset ()将地址aresult

15、开始的sizeof (aresult)字节内容置 成0。将szlinel中存储的字符串形式的整数转换到anl中去将szlinel中存储的字符串形式的整数转换到anl中去 for(i=0;i<nlen2;i+) 每一都用anl的一位，去和an2各位相乘/从anl的个位开始for (j=0; j<nlenl; j+)用选定的anl的那一位，去乘an2的各位 aresulti+j+=an2i*anlj;两数第i, j位相乘,累加到结果的 第i+j位下面的循环统一处理进位问题for(i=0;i<max_len*2;i+)if(aresulti>=10)aresulti+l+=a

16、resulti/10;aresulti%=10;输出结果和上一函数一样4. 测试分析按照附录中的测试数据，得岀如下测试、分析结果：(1) 表达式求解功能当我们输入表格中两个匸确的四则表达式吋程序能准确地求得其值：完全支持浮点数，止负数的运算；而当我们输入第三组错误的表达式时，程序能做出正确判断，提醒用给用户输入一个 正确的表达式。其数据测试的情况见截图:器譬 1运 芟数 能达整屏出功表多a>b>c>d> < < < <通输入你衆进行的操作“输入妾计算的表达瓷，以艸结東计算结杲为：49.000000時聂回车犍继续表达式一运算结果由表一知结果正确。d

17、ocumentswisual studio器®t i迈 能达整屏岀功表多a>b>c>d> (r" 你魚.1 入以*3 输，5>.00熏30200- 磁65.# 慕一 9怅5算.30九犍 计67葦 要*<结回 入14橐 输3.苴頂衣达式二运算结果rh表一知结果正确。器譬:数 能达整屏出功表多a>b>c>d> zk (输入要计算的表达事输 艦馨仃的探作丄 c" c". - tn v a* aa應输入的表送式有误！请按回车键继续表达式三运算出错悄况（2）人整数加法功能输入两组不大于200位的大整数，能

18、准确计算出结果其截图如下图所示:选择功能b加乘 snshi 数数！ 整整髯 大大上本 个个回岀 两两返退 12 3 4请选扌务1请输入两个要运算的大靈数=121212121212121212121212121212121212121212121212121212121212121212121212454545454545454545454545454545454545454545454545454545454545454545454545计算的结杲为：57575757575757575757575757575757575757575757575757575757575757575?5?5?5?

19、请按回车键继续（3）人整数乘法功能英测试截图如：c、d:my documentswisual studio 2008projects达式求解debug达式求解.exe1）两个大整数柏加2；两个大整数相乘3.）返回上级筆單4）退岀本程岸请选扌务2请输入两个要运算的大靈数=11111111111111111111111111111111111111111111111111111111111111111111111111112222222222222222222222222222222222222222222222222222222222222222222222222222计算的结杲为：246913

20、5802469135802469135802469135802469135802469135802469135802469135802468641975308641975308641975308641975308641975308641975308641975308641975308642 请按回车 键继续笫二纽数据结果正确。5. 使用说明1. 运行程序，首先出现主菜单。主菜单包括四个选项：选项"表达式求解，选 择该项可进行四则表达式的求解；选项b：大整数运算，选择该项对进行不大于200位 的人整数的加法和乘法运算（目前只支持加，乘）；选项c：清屏；选项d：退出程序， 选择该项将退出

21、程序。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无（表一）加法乘法整数1整数112121212121212121212121212121212121212111111111111111111111111111111111111111121212121212121212121212121212121212

22、12111111111111111111111111111111111111111整数2整数245454545454545454545454545454545454545222222222222222222222222222222222222224545454545454545454545454545454545454522222222222222222222222222222222222222结果结果5757575757575757575757575757575757575724691358024691358024691358024691358024575757575757575757575

23、7575757575757575769135802469135802469135802469135802468641975308641975308641975308641975308641975308641975308641975308641975308642（表二）7.附录（二）：c语言实现（源代码） 源程序文件名清单：linkstack.h/链栈的实现 数7栈linkcharstack.h/链栈的实现符号栈calculator.h/主要实现人整数的加，乘运算calculator.cpp 主程序linkstack. h 头文件/这个栈是用來存储数字符的#include<stdlib.

24、h>define error 0#dcfinc ok 1#def ine true 1sdefine false 0typedcf double elementtype;typedef int status;typedef struct nodeelementtype data;struct node *next;stacknode, *linkstack;void initstack(linkstack &head)head=(linkstack)malloc(sizeof(stacknode); head->next二null;status isempty(linkst

25、ack head)if(head-next二二null)return true;else return error;status push (l in kstack & head, el cine nttypc clement) /入栈linkstack p;p=(linkstack)malloc(sizeof(stacknode);if(p= null) return false;p->data=element;p->ncxt=hcad->next;head->next二p;return ok;status pop (linkstack & head,

26、 el emen ttype & eleme nt)/；li 栈 if(isempty(head)return false;linkstack temp二head->next;elenient=temp->data;head->next二temp->next;free(temp);return ok;ini gettop(linkstack head, elementtype &element)if(head-next二二null)return error;element 二head->next->data;return ok;status

27、destroystack(linkstack &head)linkstack q;while(head)q二head-next;free (head);head二q;return true;linkstack_char. h 头文件 el这个栈是用來存储符号字符的#ineludestdlib. h>define true 1ttdefine false 0define null 0typedef char elemtype;typedef int status;typedef struct nodelelemtype data;struct nodel *next;stackch

28、arnode, *linkcharstack;void cinitcharstack(linkcharstack &head)hcad= (linkcharstack)mal1oc(sizoof(stackcharnodc);head-next二null;int cisempty(linkcharstack head) return (hcad->next=nljll) ?true: false;ini cpush(linkcharstack &head, elemtype element) linkcharstack temp二(linkcharstack)malloc

29、(sizeof(stackcharnode); if (!temp)return error;temp->data=element;temp->next二head->next;head-next二temp; return true;int cpop(linkcharstack &head, elemtype &el ernent) if(cisempty(head)return false; stackcharnode *temp二head-next; element=temp->data;head-next二temp->next;free(tem

30、p); return true;int cgettop(linkcharstack head, elemtype &element) if(head-next!=null)element二he0d->next-data; return true;element二'#' return false;status cdestroystack(linkcharstack &head) linkcharstack q;while(head)q二head->next;free (head);head二q; return true;calculator, h 头文

31、件 jk jk mm mw w w w w m m m w abc jk ml ml mk mbl w /calculator, h头文件*/#include<stdio.h>#include<string. h>define max_len 200unsigned int anlmax_len+10;unsigned int an2max len+10;unsigned int aresultmax_len*2+10;char szlinelmaxlen+10;char szline2max_len+10;void add ()printfc请输入两个要运算的人整数:

32、n);seanf("%s", szlinel);scanf("%s", szline2);int i,j;memset (an 1, 0, sizeof (an 1) ; /库函数 meme set 将地址 an 1 开始的 si zeo(an 1)字节 内容置成memset(an2, 0, sizeof(an2);/下而将szlinel中存储的字符串形式的整数转换到anl中去/anl 0对应于个位int nlenl二strlen(szlinel);j=0;for (i二nlenlt ; i>=0; i)anlj+二szlineli-' o

33、'int nlen2=strlen(szline2);j=0;for (i二nlen2t ; i>=0; i)an2j+二szline2i-' o'for(i=0;i<max_len;i+)anli+=an2i;if(anli>=10)/看是否耍进位anli-=10;anl i+l+;/进位printfc计算的结果为:no;bool bstartoutput=false;for(i=max_len;i>=0;i)if(bstartoutput)printf("%d", anli);else if(anli)printf(&qu

34、ot;%d", anli);bstartoutput二true;void multiply()printfc请输入两个要运算的大整数:n)；scanfszlinel);seanfszline2);int i, j;memset (anl, 0, sizeof (anl) ;/库函数memeset将地址anl开始的sizeof (an 1)字节 内容置成memset(an2, 0, sizeof(an2);memsct(arcsuit, 0, sizeof(aresult);/下面将szlinel中存储的字符串形式的整数转换到anl中去/anl 0对应于个位int nlenl=strl

35、en(szlinel);j=0;for(i=nlenl-l;i>=0;i)anlj+二szlineli-' 0,;int nlen2=strlen(szline2);j=0;for(i=nlen2-l;i>=0;i)an2 j+二szline2i-' o'/以下为进行计算for (i=0; i<nlen2; i+) /每一都用&nl的一位，去和an2各位相乘/从anl的个位开始for (j=0; j<nlenl: j+) /用选定的an 1的那一位,去乘an2的各位 aresulti+j4-=an2i*anl j;两数第i, j位相乘,累

36、加到结果的第i+j 位下面的循环统一处理进位问题for(i=0;i<max len*2;i卄)if(aresulti>=10)aresulti+1+=aresulti/10;aresulti%=10;printfc计算的结果为:nz，);bool bstartoutput二false;for(i=max len*2;i>=0;i) if(bstartoutput)printf("%d", aresulti);else if(aresultij) printf ("%d, aresulti);bstartoutput二true;calculator

37、, cpp njvnnnjbcnnnnij*. >». wwwwmmm m w c c include <stdio.h>#inelude <stdlib h># inelude# inelude# include"linkstack. h"linkcharstack. h" calculator. h# define stack_init_size 30# define stackincreament 10# define number 30/判断ch是否为运算符 int comop (char ch)switch(ch)

38、case ' +':case ' -':case ' *':case ' /':case ' c :case ':case ':return 1; default:return 0;/comop/比较两个运算符的优先级char precede (char ch, char c)/ch是栈顶字符,c是表达式字符switch (ch)case ' +':case ' -': if (c=，+'| | c=，| | c=' y c=- #，) return，; if

39、(c= *'| | c=，r i i c=' (') return ' ；case ' *':case ':if (c=，+'| | c 二二'-，| | c=，*，h c 二二'/，| | c二二'y c 二二,#，) return，; if (c=，(j) return ' ；case '(':if (c=，+'| | c=，_'| | c=' *，| | c=，/'| c=，(，) retur n，；if (c二二')')retu

40、rn '二'；if (c=，#') return ''case ' v :include <string.h> if （c=，+'| | c=，| c=' *，| | c=，/'| c=，），） retur n，；if （c二二'（'）return ''if （c二二'#'） return ' >'case ' #':if （c=，+'| | c=，_' | | c=' *，| | c=，/，| | c

41、=，（，） retur n，； if （c=，）'）return ''if （c=，#'） return '二'；default:return '$'/precede/运算函数elementtype operate（elementtype a, char ch,elementtype b）switch（ch）case '+' :return a+b;case '-' :return ab;case ' *' :return a*b;case ' /':if（b=o）r

42、eturn -32767;return a/b;default:return -32767;/operate/错误提示函数int error (char *str)/在用的过程屮可以不断扩充错误的类型int i二0,err二0;while (str i != #') /主要通过判断所有输入的字符数组str 30if(err=l /err是为有些字符并不满足其它函数而设的一个鉛误点11(stri=，+t 1st 讥 i二二'-| |stri二二'*'| |st ri=- /，| | s t 讥 i二二'.) &&/其它函数只要一声明err=

43、l也就说明输入有误(stri+l=')11(st ri=，+'| | st ri=，*' | | stri=，/'| | st ri=，.')&&(stri-l=(') ll(stri= ll(stri= /|(stri=('i i(stri二二')'&&&&&&&&&&stri+l=，.') stri+l=(') stri+l=，(') stri+l=')') stri+l>=，o

44、' &&stri+l<=, 9*)i | (str i >二'o' &&str i<二'9 && str i+1二二'(')| | (stro='+'| |stro='*'| |st 讥 0='/' | |stro=')')ik(stri=，+'| | stri=，_'| | stri=，*，| | str i二二,/'| | str i=，.，)&&(stri+l=，+'

45、;| | str i+1二二'-'| | str i+1二二'*' | | str i+1二二'/，| | stri+l=，.') )i (int(stri)>57)i | (stri=，/' && stri+l='o')| (int(stri)>31 && int (stri)<38)return 1;else if(stri=，)return 0;i+;/whilereturn 0;/错误提示函数表达式计算elementtype evaluateexpression(c

46、har *exp) char c, ch;/c代表输入表达式中的字符，ch代表栈顶运算符char *p, *q, *temp;/temp指向运算符后而的一个字符 double i=0, a=0, b=0;p二q二exp;linkcharstack optr;/运算符栈linkstack opnd;/操作数栈ctnitcharstack(optr);cpush(optr,' initstack(opnd);c二*p;temp二p;p+;if (c二二'-)c=*p;temp二p;p+;wh订e(c!二'#t | !cisempty(optr)/栈不为空或表达式没有结束if

47、(! comop (c) 不是运算符则解析数字字符串然厉进操作数栈double m二0, n二0;while(c!= .' &&c二'o' &&c= 9')/解析整数部分 m=n)*10+(c-48);c=*p;p+；if (c=，')/解析小数部分c=*p;wh订e(c二'o' &&c二'9') p+；c=*p；q二p；p； while (*p!='.') n=n/104-(*p-48)/10. 0; p_；p=q；p+；辻(*(t emp-2) =，('&&*(t emp-l)='-i |t empt 二二 exp)push (opnd, - (m+n);elsepush (opni), m+n);/*数字进栈结朿*else/是运算符时则进栈optrif (c=，-' &&* (p-2)=，(')c=*p;temp=p;p+；else/elsel cgettop(optr, ch); switch(precede(ch, c) case：/栈顶运算符优先权低