《数据结构表达式的值课程设计.doc》由会员分享，可在线阅读，更多相关《数据结构表达式的值课程设计.doc（18页珍藏版）》请在三一办公上搜索。
1、河北科技大学数据结构课程设计报告学生姓名： 学 号： 专业班级： 课程名称： 数据结构（c语言版 学年学期： 2 014 2 0 15 学年第 二 学期 指导教师： 白云飞 2 0 15 年 7 月课程设计成绩评定表学生姓名学 号成绩专业班级软件121起止时间2015.6-2015.7设计题目表达式的值验收内容课程设计小组验收结果：硬件设计：优秀良好中等及格需努力程序设计：优秀良好中等及格需努力实验结果：优秀良好中等及格需努力课程设计个人验收结果：操作能力：优秀良好中等及格需努力软件理解：优秀良好中等及格需努力硬件理解：优秀良好中等及格需努力指导教师： 年 月 日目 录1、 题目的内容与要求
2、42、 需求分析 43、 概要设计 44、 详细设计 55、 源代码 76、 运行结果与分析 167、 收获与体会 161、 题目的内容即要求从文件读取表达式，判断表达式是否合理，将表达式转换成后缀形式，按后缀表达式求值；题目涉及加减乘除，带括弧的混合运算；随时可以退出。2、 需求分析程序先从文本文件中读取表达式，然后利用栈设计一个程序，该程序能够用于表达式求值，程序将读入的中缀表达式转换为后缀表达式，然后按后缀表达式进行计算，输出结果。本程序具有检测表达式语法是否正确的功能，如果表达式出现错误的时候，程序会提示操作人员执行的表达式不合理，语法是不能执行的。语法正常的情况下，程序可以实现了加、
3、减、乘、除以及带括号的基本运算。程序在执行表达式的时候，先检查表达式是否合理，不合理则输出表达式不符合要求，合理则将中缀表达式转化为后缀表达式，然后则对表达式求值，输出结果。3、 概要设计 本程序选用的是线性表数据结构。它按照后进先出的原则存储数据，先进的数据被压入栈最后的数据在栈顶，需要读数据的时候才栈顶开始探出数据。 程序采用的是顺序存储结构，可以将逻辑上相邻的数据元素放在物理上相邻的存储单元里，节电之间的关系由存储单元相邻的关系来决定。 选择线性表结构是因为程序是用栈来设计的，可以将优先运算的送至栈顶，低级别的运算则最后根据先后进栈的顺序来执行。选择顺序存储结构是因为顺序存储结构存取数据
4、数度快，占用的存储空间小。系统的功能模块划分：1、Translate()的功能是将中缀表达式转换为后缀表达式 2、Disp()的功能是输出后缀表达式3、Process()的功能是将原表达式进行预处理，检查符号是否匹配，转化为中缀式。4、endright的功能是先对表示式的运算符进行处理，考虑其计算的优先级。5、FindSymbol（）的功能是对表达式的括号进行优先处理。6、FindError（）的功能是检查表达式是否有语法错误。操作之间的调用关系：各个函数是通过主函数main()来调用的，当程序接受一段表达式的时候，先通过Process()对整个表达式做一个运算的预处理，转化为中缀式。Find
5、Error（）检查表达式是否出现可以执行，然后送入FindSymbol（）进行处理，带括号的运算优先处理，之后endright函数检查表达式的优先级，高级的运算先进行处理。接着Translate()函数把表达式转换为后缀式。 Disp()的功能是输出后缀表达式。计算表达式。最后主函数输出计算结果。 4、 详细设计 在计算机中，算数表达式的计算通常是通过使用栈来实现的。所以表达式求值程序最主要的数据结构就是栈。可以使用栈来存储输入表达式的操作符和操作数。输入的表达式是由操作数和操作符以及改变运算次序的括号连接而成的。（1） 本程序通过Disp()的功能是输出后缀表达式。 将中缀式转化为后缀式，要
6、将遇到的运算对象直接放入后缀式的存储区。将刚读入的字符送至操作数栈，如果遇到运算符则送入运算符栈。通过栈的先后进栈的顺序来将操作数和操作符进行出栈，然后输出后缀表达式。void Disp() int i; printf( 后缀表达式:); for (i=0;i二元运算符不正确n); return -1; else if (Kind(h)=BINARYOP | Kind(h)=RIGHTPAREN) PutToken(h); else printf(二元运算符不正确n); return -1; if (k=Kind(h)=LEFTPAREN) parencount+; else if (k=RI
7、GHTPAREN) if (-parencount不正确的标识符n); return -1; int FindNumber(char str,int pos) if (Leading()=0) printf(常量位置不正确n); return -1; else lexicon+tokencount.kind=OPERAND; lexicontokencount.info.val=atof(&strpos); strcpy(lexicontokencount.name,number); PutToken(tokencount); for (;isdigit(strpos) | strpos=.;
8、pos+); return pos; 5、 源代码/*该程序从文本文档读取表达式，并转换为后缀表达式，再求值 工程文件需附带一文本文档*/#include #include #include #include #include #include#define MAXNAME 7 #define MAXPRIORITY 6 #define MAXTOKEN 100 #define MAXSTACK 100 #define MAXSTRING 101 #define HASHSIZE 101 #define LASTOPERAND 17 typedef double Value_type;type
9、def enum kind_tag UNARYOP,BINARYOP,OPERAND,LEFTPAREN,RIGHTPAREN,ENDEXPR Kind_type;typedef struct char nameMAXNAME; Kind_type kind; union int pri; Value_type val; info; Token_type;Token_type lexiconMAXTOKEN= #,ENDEXPR, (,LEFTPAREN, ),RIGHTPAREN, ,UNARYOP,6, abs,UNARYOP,6, sqrt,UNARYOP,6, exp,UNARYOP,
10、6, ln,UNARYOP,6, log10,UNARYOP,6, sin,UNARYOP,6, cos,UNARYOP,6, tanh,UNARYOP,6, +,BINARYOP,4, -,BINARYOP,4, *,BINARYOP,5, /,BINARYOP,5, %,BINARYOP,5, ,BINARYOP,6; int hashtableMAXTOKEN;int infixMAXTOKEN; int postfixMAXTOKEN; int inlength; int postlength; int parencount; int tokencount; int Hash(char
11、 *name) int h=name0 % HASHSIZE; while (1) if (hashtableh=-1) break; else if (strcmp(lexiconhashtableh.name,name)=0) break; else if (name1=0) h+=31; else h+=name1; h%=HASHSIZE; return abs(h); void MakeHashTable() int i; for (i=0;iHASHSIZE;i+) hashtablei=-1; for (i=1;i=LASTOPERAND;i+) hashtableHash(le
12、xiconi.name)=i; Kind_type Kind(int h) return(lexiconh.kind); int Priority(int h) return(lexiconh.info.pri); int Leading() int k; if (inlength不正确的标识符n); return -1; int FindNumber(char str,int pos) if (Leading()=0) printf(常量位置不正确n); return -1; else lexicon+tokencount.kind=OPERAND; lexicontokencount.in
13、fo.val=atof(&strpos); strcpy(lexicontokencount.name,number); PutToken(tokencount); for (;isdigit(strpos) | strpos=.;pos+); return pos; int FindSymbol(char str,int pos) int h,k; char wordMAXTOKEN; word0=strpos; word1=0; pos+; if (h=hashtableHash(word)=-1) printf(表达式中存在不能识别的符号n); return -1; else if (L
14、eading()=1) if (Kind(h)=RIGHTPAREN) printf(不应为右括号n); return -1; else if (Kind(h)!=BINARYOP) PutToken(h); else if (strcmp(word,+)=0); else if (strcmp(word,-)=0) PutToken(hashtableHash(); else printf( 二元运算符不正确n); return -1; else if (Kind(h)=BINARYOP | Kind(h)=RIGHTPAREN) PutToken(h); else printf(二元运算符
15、不正确n); return -1; if (k=Kind(h)=LEFTPAREN) parencount+; else if (k=RIGHTPAREN) if (-parencount-1 & Kind(h)!=LEFTPAREN) PutToken1(h); h=Sttop;top-; break; case UNARYOP: case BINARYOP: endright=0; do if (top=-1) endright=1; else if (Kind(Sttop)=LEFTPAREN) endright=1; else if (Priority(Sttop)-1) h=Stto
16、p;top-; PutToken1(h); break; while (type!=ENDEXPR); PutToken1(0); int Process(char *instring) int len,pos; inlength=-1; parencount=0; tokencount=LASTOPERAND; len=strlen(instring); instringlen=0; for (pos=0;poslen;) if (instringpos= ) pos+; else if (isalpha(instringpos) pos=FindError(instring,pos); e
17、lse if (isdigit(instringpos) | instringpos=.) pos=FindNumber(instring,pos); else pos=FindSymbol(instring,pos); if (pos=-1) return 0; if (parencount!=0) printf(左右括号不匹配n); PutToken(0); return 1; void Disp() int i; printf( 后缀表达式:n); for (i=0;i除零错误n); break; case 16: if (y!=(Value_type)0) return(fmod(x,
18、y); else printf( 除零错误n); break; case 17: return(pow(x,y); default: printf( %d是无效的二元运算符n,h); break; Value_type DoUnary(int h,Value_type x) switch(h) case 3: return(-x); case 4:return(abs(x); case 5: if (x=0) return(sqrt(x); else printf( 负数不能开平方n); break; case 6: return(exp(x); case 7: if (x0) return(
19、log(x); else printf( 负数不能求lnn); break; case 8: if (x0) return(log10(x); elseprintf( 负数不能求log10n); break; case 9: return(sin(x); case 10: return(cos(x); case 11: return(tanh(x); Value_type GetValue(int h) if (Kind(h)!=OPERAND) printf( 不是一个操作数n); else return(lexiconh.info.val);Value_type EvaluatePostf
20、ix() Kind_type type; int h; Value_type x,y; double StMAXSTACK; int top=-1; postlength=-1; do GetToken1(h); switch(type=Kind(h) case OPERAND: top+; Sttop=GetValue(h); break; case UNARYOP: x=Sttop; top-;top+; Sttop=DoUnary(h,x);break; case BINARYOP: y=Sttop;top-; x=Sttop;top-; top+; Sttop=DoBinary(h,x
21、,y);break; case ENDEXPR: x=Sttop;top-; if (top-1) printf( 不正确的表达式n); break; while (type!=ENDEXPR); return(x); ;void main() char instringMAXSTRING; MakeHashTable(); printf(n);FILE *fp;char *pchBuf;int NLen;fp=fopen(data.txt,r);fseek(fp,0,SEEK_END);NLen=ftell(fp);rewind(fp);pchBuf=(char*)malloc(sizeof
22、(char)*NLen+1);if(!pchBuf)perror(内存不够!n);exit(0);NLen=fread(pchBuf,sizeof(char),NLen,fp);fclose(fp);pchBufNLen=0;printf(从文本读出的字符串：n);printf(%sn,pchBuf);strcpy(instring,pchBuf);printf(表达式：%s转换为后缀表达式n,instring); while (strlen(instring)!=0) if (Process(instring) Translate(); Disp(); printf( nn运算结果:%gnn
23、,EvaluatePostfix(); break; getch(); printf(n);6、 运行结果及分析当从文本中读取的表达式是合理的时候，程序会给出原表达式和转化后的后缀式，并计算出结果。当读取的表达式存在问题时，程序则会提出相应的提示：表示表达式中存在括号不对称；则表示表达式存在不能辨别的符号，等等。7、 收获与体会 在做此次课程设计的时候，我先按给出的要求，把它分成了四个部分： 1、读取表达式 2、检查表达式是否合理3、将中缀表达式转化为后缀表达式4、按后缀表达式求值。按照这个顺序每次只做其中的一个，因为比起整体设计，考虑其中的一部分要相对容易得多。每一部分所涉及到的知识相对单一
24、，遇到问题可以查阅相关书籍和从网络上寻找解决的办法。我所遇到的真正的难题，是在进行整体设计时，各个部分之间的衔接，因为每个部分之间都存在着差异，例如，从文档中读取的表达式是以字符串的形式表示的，而将表达式从中缀式转换为后缀式过程是对表达式的元素逐个进行的，这就需要将字符串复制给一个字符数组，最先时候是将读文本的程序做成了一个字程序，后来由于衔接时总是出错，便索性将该部分搬到了主程序中，省去了麻烦。从很早的时间就在构思这个，但是到最后才算勉强做出来这个不算完美甚至是存在很多问题的程序，其中遇到的种种问题，让我感觉到，完成一件事请，需要一直的坚持和耐心。当然，从本次课程设计中，也收获颇丰，首先是对专业知识的掌握又加深了一层，不但提高了自己处理问题的能力，还更加熟练地掌握了运用互联网寻求帮助的方法，毕竟,团队的力量才是最大的。
