数据结构算术表达式求值实验报告

1、 .软件技术基础实验报告实验名称： 表达式计算器 系 别： 通信工程 年 级： 班 级： 学生学号： 学生： 数据结构课程设计报告 题目 简易计算表达式的演示题目要求要求：实现基本表达式计算的功能输入：数学表达式，表达式由整数和“+”、 “-”、“×”、“/”、“（”、“）”组成输出：表达式的值基本操作：键入表达式，开始计算，计算过程和结果记录在文档中难点：括号的处理、乘除的优先级高于加减1前言在计算机中，算术表达式由常量、变量、运算符和括号组成。由于不同的运算符具有不同的优先级，又要考虑括号，因此，算术表达式的求值不可能严格地从左到右进行。因而在程序设计时，借助栈实现。算法输入：一

2、个算术表达式，由常量、变量、运算符和括号组成（以字符串形式输入）。为简化，规定操作数只能为正整数，操作符为+、-*、/、=，用#表示结束。算法输出：表达式运算结果。算法要点：设置运算符栈和运算数栈辅助分析算符优先关系。在读入表达式的字符序列的同时，完成运算符和运算数的识别处理，以与相应运算。2概要设计2.1 数据结构设计任何一个表达式都是由操作符，运算符和界限符组成的。我们分别用顺序栈来寄存表达式的操作数和运算符。栈是限定于紧仅在表尾进行插入或删除操作的线性表。顺序栈的存储结构是利用一组连续的存储单元依次存放自栈底到栈顶的数据元素，同时附设指针top指示栈顶元素在顺序栈中的位置，base为栈底

3、指针，在顺序栈中，它始终指向栈底，即top=base可作为栈空的标记，每当插入新的栈顶元素时，指针top增1，删除栈顶元素时，指针top减1。2.2 算法设计为了实现算符优先算法。可以使用两个工作栈。一个称为OPTR，用以寄存运算符，另一个称做OPND，用以寄存操作数或运算结果。1.首先置操作数栈为空栈，表达式起始符”#”为运算符栈的栈底元素；2.依次读入表达式，若是操作符即进OPND栈，若是运算符则和OPTR栈的栈顶运算符比较优先权后作相应的操作，直至整个表达式求值完毕（即OPTR栈的栈顶元素和当前读入的字符均为”#”）。2.3 ADT描述ADT Stack数据对象：D= |ElemSet,

4、i=1,2,，n, n0数据对象：R1=<>|,i=2,，n约定端为栈顶，端为栈底。基本操作： InitStack(&S) 操作结果：构造一个空栈S。 GetTop(S) 初始条件：栈S已存在。 操作结果：用P返回S的栈顶元素。 Push(&S，ch) 初始条件：栈S已存在。 操作结果：插入元素ch为新的栈顶元素。 Pop(&S) 初始条件：栈S已存在。 操作结果：删除S的栈顶元素。In(ch)操作结果：判断字符是否是运算符，运算符即返回1。 Precede(c1, c2) 初始条件：c1,c2为运算符。操作结果：判断运算符优先权，返回优先权高的。Opera

5、te(a,op,b)初始条件：a,b为整数，op为运算符。操作结果：a与b进行运算，op为运算符，返回其值。num(n)操作结果：返回操作数的长度。EvalExpr()初始条件：输入表达式合法。操作结果：返回表达式的最终结果。ADT Stack2.4 功能模块分析1.栈的基本功能。InitStack(Stack *s) 和InitStack2(Stack2 *s)分别构造运算符栈与构造操作数栈，Push(Stack *s,char ch) 运算符栈插入ch为新的栈顶元素，Push2(Stack2 *s,int ch) 操作数栈插入ch为新的栈顶元素，Pop(Stack *s) 删除运算符栈s的

6、栈顶元素，用p返回其值，Pop2(Stack2 *s)删除操作数栈s的栈顶元素，用p返回其值，GetTop(Stack s)用p返回运算符栈s的栈顶元素，GetTop2(Stack2 s) 用p返回操作数栈s的栈顶元素。2.其它功能分析。 (1)In(char ch) 判断字符是否是运算符功能，运算符即返回1，该功能只需简单的一条语句即可实现，return(ch='+'|ch='-'|ch='*'|ch='/'|ch='('|ch=')'|ch='#')。 (2) Precede(c

7、har c1,char c2) 判断运算符优先权功能，该函数判断运算符c1,c2的优先权，具体优先关系参照表1。 (3) Operate(int a,char op,int b)操作数用对应的运算符进行运算功能。运算结果直接返回。(4) num(int n) 求操作数的长度功能，需要用itoa函数把int型转换成字符串型，strlen函数可求字符长度。(5) EvalExpr()主要操作函数运算功能。分析详细见“3.详细设计3.2”。3详细设计3.1 数据存储结构设计 因为表达式是由操作符，运算符和界限符组成的。如果只用一个char类型栈，不能满足2位以上的整数，所以还需要定义一个int类型的

8、栈用来寄存操作数。/* 定义字符类型栈 */struct stacklifei1 /数字栈的定义double *base;double *top;s1;/struct stacklifei2 /运算符栈的定义char *base;char *top;s2;3.2 计算功能的实现void jisuan() / 该函数对数字栈的前两个栈顶 /元素与符号栈的栈顶元素完成一次运算操作double a,b;b=*(s1.top-1); s1.top-;if(s1.top=s1.base)error=1;return ; a=*(s1.top-1); switch(*(s2.top-1)case '

9、;+':a=a+b;break;case '-':a=a-b;break;case '*':a=a*b;break;case '/':if(b=0)error=2;s2.top=s2.base;return ;/除数不为0else a=a/b;break;default :error=1;fprintf(file,"%lf %c %lf= %lfn",*(s1.top-1),*(s2.top-1),b,a);*(s1.top-1)=a; /将运算结果入栈s2.top-; return ;3.3函数表达式求值功能的实现v

10、oid qiuzhi(char *cr) 该函数完成对表达式的处理int i=0,k,h,flag,fuhao=0;double sum,j;s1.base=s1.top=shuzhi;s2.base=s2.top=fuha; *(s2.top)='#' s2.top+;while(s2.top!=s2.base)sum=0;flag=0;k=10;j=1;h=1;while(cri>='0'&&cri<='9'|cri='.')/若当前的字符是数字，就将char型的数据转换为double型if(cri

11、='.')if(cri-1<'0'|cri-1>'9'|i=0|cri+1<'0'|cri+1>'9')error=1;break;elsek=1;h=10;elseflag=1;j=j*h;sum=sum*k+(cri-48)/j; i+;3.4对函数表达式每个字符的操作switch(cri)case '-':if(cri-1='('|i=0)fuhao=1;i+;break;/判断是不是负号，若不是则进行与加号一样的操作/当'-'出现在表达

12、式第一位或是'('后第一位,则应将其判为负号case '+': /加、减号的优先级只比'('和'='高，若栈顶元素为这两者之一/就将其入栈，否则执行运算操作if(*(s2.top-1)='('|*(s2.top-1)='#')*(s2.top)=cri;s2.top+;i+;else jisuan();break;case '*':case '/':/乘、除号的优先级只比'*'、'/'和''低，若栈顶元素为这三者之一/就

13、执行运算操作，否则将其入栈if(*(s2.top-1)='*'|*(s2.top-1)='/')jisuan(); else *(s2.top)=cri;s2.top+;i+;break;case '(': *(s2.top)=cri; s2.top+;i+;break;/未入栈时'('的优先级最高，所以它一定要入栈/但一入栈其优先级就应降为最低case ')':/注意：由于'()'运算优先级最高故我直接进行运算，/直到栈顶元素为'('后将'('出栈，故符号栈中一定没

14、有')'，/这也是我进行以上优先级判断的前提if(*(s2.top-1)='(')s2.top-;i+;else jisuan();break;case '=':/表达式结束，若符号栈栈顶元素不为'#'，进行运算/否则退栈，结束if(*(s2.top-1)='#')s2.top-;else jisuan();break;default :i+; /清除空格与未定义符号3.5主菜单页面的实现void main()char cr60;char c='a'file=fopen(outfile,"

15、w+");/使用提示printf("*n");printf("*斐计算器*n");printf("四则简易计算器nn");printf("输入表达式例如 2+4= nn");printf("最后按 # 键 则会退出保存nn");printf("使用nn");printf("-n");printf("*n");/循环输入表达式，按'#'键退出while(c!='#')error=0;printf(

16、"输入表达式:n");gets(cr);fprintf(file,"表达式：%sn",cr);qiuzhi(cr);printf("任意键继续，按 # 键退出:n");c=getch();fclose(file);附加一 算符间的优先关系如下：+-*/()=#+><<<<>>>->><<<>>>*>>>><>>>/>>>><>>>(<<

17、;<<<=>>)>>>>=>>>=<<<<<<=<#<<<<<<>=4软件测试1.运行成功后界面。2.输入正确的表达式后。3.更改表达式，带括号输出 5心得体会这次课程设计让我再一次加了解大一学到的C和这个学期学到的数据结构。课设题目要求不仅要求对课本知识有较深刻的了解，同时要求程序设计者有较强的思维和动手能力和更加了解编程思想和编程技巧。这次课程设计让我有一个深刻的体会，那就是细节决定成败，编程最需要的是严谨，如何的严谨都不过分，往往检查

18、了半天发现错误发生在某个括号，分号，引号，或者数据类型上。就一点小小的错误也耽误了我几十分钟，所以说细节很重要。 程序设计时，也不要怕遇到错误，在实际操作过程中犯的一些错误还会有意外的收获，感觉课程设计很有意思。在具体操作中这学期所学的数据结构的理论知识得到巩固，达到课程设计的基本目的，也发现自己的不足之出，在以后的上机中应更加注意，同时体会到C语言具有的语句简洁，使用灵活，执行效率高等特点。发现上机的重要作用，特别算术表达式有了深刻的理解。 最后，感老师在这门数据结构课程的悉心指导，祝老师和助教身体健康，万事如意！参考文献1.数据结构(C语言版) 严蔚敏 清华大学2.C程序设计 谭浩强 清华

19、大学附 录程序源代码：#include<stdio.h>#include<stdlib.h>#include<math.h>#include<conio.h> struct stacklifei1 /数字栈的定义double *base;double *top;s1;struct stacklifei2 /运算符栈的定义char *base;char *top;s2;double shuzhi40; /数字栈char fuha40; /符号栈int error; /出错标识符FILE *file;char outfile30="life

20、ijisuanqi.txt"void jisuan() / 该函数对数字栈的前两个栈顶 /元素与符号栈的栈顶元素完成一次运算操作double a,b;b=*(s1.top-1); /取数字栈栈顶元素s1.top-;if(s1.top=s1.base)error=1;return ; /若栈空，出错a=*(s1.top-1); /取数字栈栈顶元素switch(*(s2.top-1)case '+':a=a+b;break;case '-':a=a-b;break;case '*':a=a*b;break;case '/':

21、if(b=0)error=2;s2.top=s2.base;return ;/除数不为0else a=a/b;break;default :error=1;fprintf(file,"%lf %c %lf= %lfn",*(s1.top-1),*(s2.top-1),b,a);*(s1.top-1)=a; /将运算结果入栈s2.top-; /运算符退栈return ;void qiuzhi(char *cr)/qiuzhi()；该函数完成对表达式的处理int i=0,k,h,flag,fuhao=0;double sum,j;s1.base=s1.top=shuzhi;s2

22、.base=s2.top=fuha; /数字栈与符号栈初始化*(s2.top)='#' /将'#'入栈，方便循环s2.top+;while(s2.top!=s2.base)sum=0;flag=0;k=10;j=1;h=1;while(cri>='0'&&cri<='9'|cri='.')/若当前的字符是数字，就将char型的数据转换为double型if(cri='.')if(cri-1<'0'|cri-1>'9'|i=0|cr

23、i+1<'0'|cri+1>'9')/判断小数点是否出错error=1;break;elsek=1;h=10;elseflag=1;j=j*h;sum=sum*k+(cri-48)/j; i+;if(flag) /flag不为0表明有数据需要入栈if(fuhao)sum=-sum;fuhao=0;/fuhao是个标志记号，值不为0表明刚才转换的值为负数*(s1.top)=sum;s1.top+;else switch(cri)case '-':if(cri-1='('|i=0)fuhao=1;i+;break;/判断是

24、不是负号，若不是则进行与加号一样的操作/当'-'出现在表达式第一位或是'('后第一位,则应将其判为负号case '+': /加、减号的优先级只比'('和'='高，若栈顶元素为这两者之一/就将其入栈，否则执行运算操作if(*(s2.top-1)='('|*(s2.top-1)='#')*(s2.top)=cri;s2.top+;i+;else jisuan();break;case '*':case '/':/乘、除号的优先级只比'*'、

25、'/'和''低，若栈顶元素为这三者之一/就执行运算操作，否则将其入栈if(*(s2.top-1)='*'|*(s2.top-1)='/')jisuan(); else *(s2.top)=cri;s2.top+;i+;break;case '(': *(s2.top)=cri; s2.top+;i+;break;/未入栈时'('的优先级最高，所以它一定要入栈/但一入栈其优先级就应降为最低case ')':/注意：由于'()'运算优先级最高故我直接进行运算，/直到栈顶元

26、素为'('后将'('出栈，故符号栈中一定没有')'，/这也是我进行以上优先级判断的前提if(*(s2.top-1)='(')s2.top-;i+;else jisuan();break;case '=':/表达式结束，若符号栈栈顶元素不为'#'，进行运算/否则退栈，结束if(*(s2.top-1)='#')s2.top-;else jisuan();break;default :i+; /清除空格与未定义符号if(error)break;if(error|s1.top-1!=s1.base)/若运行出错或是数字栈中的元素不是一个，就进行出错提醒if(error=2)printf("除数不能为0！n");fprintf(file,"%sn","除数不能为0！");else printf("表达式错误！n");fprintf(file,"%sn","表达式错误！");else /结果输出，输出小数点后六位，fprintf(file,"结束n");printf("%.6lfn",*(s1.ba