数据结构表达式的值课程设计

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; .val=atof(&strpos); strcpy(,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(,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、)=i; Kind_type Kind(int h) return(lexiconh.kind); int Priority(int h) return(.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(,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(.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(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