下载文档原格式
《数据结构》课程设计报告书题目: 表达式求值系别：计算机科学与信息系学号：学生姓名：指导教师:完成日期:目录➢1.前言➢2.概要设计2。
1 数据结构设计2.2 算法设计2.3 ADT描述2。
4 功能模块分析➢3。
详细设计3.1 数据存储结构设计3.2主要算法流程图（或算法代码）➢4.软件测试➢5。
总结➢附录1．前言在计算机中，算术表达式由常量、变量、运算符和括号组成。
由于不同的运算符具有不同的优先级，又要考虑括号，因此，算术表达式的求值不可能严格地从左到右进行.因而在程序设计时，借助栈实现。
算法输入：一个算术表达式,由常量、变量、运算符和括号组成（以字符串形式输入）。
为简化，规定操作数只能为正整数，操作符为+、-*、/，用#表示结束。
算法输出：表达式运算结果。
算法要点：设置运算符栈和运算数栈辅助分析算符优先关系。
在读入表达式的字符序列的同时,完成运算符和运算数的识别处理，以及相应运算。
2．概要设计2.1 数据结构设计任何一个表达式都是由操作符,运算符和界限符组成的。
我们分别用顺序栈来寄存表达式的操作数和运算符.栈是限定于紧仅在表尾进行插入或删除操作的线性表。
顺序栈的存储结构是利用一组连续的存储单元依次存放自栈底到栈顶的数据元素，同时附设指针top指示栈顶元素在顺序栈中的位置，base为栈底指针，在顺序栈中，它始终指向栈底，即top=base可作为栈空的标记，每当插入新的栈顶元素时，指针top增1，删除栈顶元素时,指针top减1。
2.2 算法设计为了实现算符优先算法。
可以使用两个工作栈。
一个称为OPTR ，用以寄存运算符，另一个称做OPND ，用以寄存操作数或运算结果。
1。
首先置操作数栈为空栈，表达式起始符”＃"为运算符栈的栈底元素；2.依次读入表达式，若是操作符即进OPND 栈，若是运算符则和OPTR 栈的栈顶运算符比较优先权后作相应的操作，直至整个表达式求值完毕（即OPTR 栈的栈顶元素和当前读入的字符均为"#")。
竭诚为您提供优质文档/双击可除数据结构表达式求值实验报告篇一：数据结构实验二——算术表达式求值实验报告《数据结构与数据库》实验报告实验题目算术表达式求值学院：化学与材料科学学院专业班级：09级材料科学与工程系pb0920603姓学邮名：李维谷号：pb09206285箱：指导教师：贾伯琪实验时间：20XX年10月10日一、需要分析问题描述：表达式计算是实现程序设计语言的基本问题之一，它的实现是栈的应用的一个典型例子。
设计一个程序，演示通过将数学表达式字符串转化为后缀表达式，并通过后缀表达式结合栈的应用实现对算术表达式进行四则混合运算。
问题分析：在计算机中，算术表达式由常量、变量、运算符和括号组成。
由于不同的运算符具有不同的优先级，又要考虑括号，因此，算术表达式的求值不可能严格地从左到右进行。
因而在程序设计时，借助栈实现。
设置运算符栈（字符型）和运算数栈（浮点型）辅助分析算符优先关系。
在读入表达式的字符序列的同时完成运算符和运算数的识别处理，然后进行运算数的数值转换在进行四则运算。
在运算之后输出正确运算结果，输入表达式后演示在求值中运算数栈内的栈顶数据变化过程，最后得到运算结果。
算法规定：输入形式：一个(:数据结构表达式求值实验报告)算术表达式，由常量、变量、运算符和括号组成（以字符串形式输入）。
为使实验更完善，允许操作数为实数，操作符为（、）、.（表示小数点）、+、-、*、/、^（表示乘方），用#表示结束。
输出形式：演示表达式运算的中间结果和整个表达式的最终结果，以浮点型输出。
程序功能：对实数内的加减乘除乘方运算能正确的运算出结果，并能正确对错误输入和无定义的运算报错，能连续测试多组数据。
测试数据：正确输入：12*（3.6/3+4^2-1）#输出结果：194.4无定义运算：12*（3.6/（2^2-4）+1）#输出结果：表达式出错，除数为0，无意义错误输入：12+s#输出结果：eRRoR！二、概要设计拟采用两种类型的展分别对操作数和操作符进行操作。
(一) 需求分析1、输入的形式和输入值的范围：根据题目要求与提示，先选择你要使用的表达式形式（中缀用1，后缀用0），在输入一个中缀表达式，输入数的范围为int型，此时，程序将计算出表达式的结果。
2、输出的形式：当按照程序要求选择了1或0之后，再输入表达式；如果选择的是1，则程序将自动运算出表达式结果；如果之前选择的是0，则程序将现将中缀表达式转化为后缀表达式并计算出结果。
3、程序所能达到的功能：本程序能计算出含+、-、*、/、（、）等运算符的简单运算。
4、测试数据：输入一个表达式，如果你之前选择的是“中缀表达式”，那么输入5*(4-2)#,那么输出结果是10；如果之前选择的是“后缀表达式”，那么输入5*（4-2）#，那么他将先转换成后缀表达式5 4 2 - * #，再输出结果10。
如果输入表达式没有结束标示符#，如5*（4-2），那将不会输出任何结果，或出现错误结果。
(二) 概要设计为了实现上述操作，应以栈为存储结构。
1．基本操作：（1）. int GetTop(SqStack *s)初始条件：栈存在；操作结果：若栈为空，则返回s的栈顶元素；否则返回ERROR。
（2）.void Push(SqStack *s,int e)初始条件：栈存在；操作结果：插入e为新的栈顶元素。
（3）.int Pop(SqStack *s)初始条件：栈存在；操作结果：若栈不空，则删除之，并返回其值；否则返回REEOR。
（4）.void InitStack(SqStack *s)初始条件：栈存在；操作结果：置栈为空。
（5）.int Empty(SqStack *s)初始条件：栈存在；操作结果：判定s是否为空栈。
（6）.int Operate(int a,char theta, int b)初始条件：操作数a和b存在，且theta是+、-、*、/四则运算；操作结果：返回a与b间theta运算的结果。
（7）.int In(char s,char* TestOp)初始条件：s为待判断字符，TestOp为已知的算符集合；操作结果：s为算符集合中的元素则返回1，否则返回0.（8）.int ReturnOpOrd(char op,char* TestOp)初始条件：op为待确定运算符，TestOp为已知的算符集合；操作结果：确定运算符类型。
数据结构表达式求值实验报告数据结构表达式求值实验报告第一章引言数据结构是计算机科学中重要的基础知识之一，它研究的是数据在计算机中的存储和组织方式，以及基于这些方式进行操作和运算的算法。
表达式求值是数据结构中一个重要的应用场景，它涉及到从一个给定的表达式中计算出最终结果的过程。
本实验旨在通过实际编程实践，掌握表达式求值的算法和数据结构的应用。
第二章实验目的1.理解表达式的概念。
2.熟悉常见表达式求值算法。
3.掌握栈的基本操作。
4.实现一个表达式求值的程序。
第三章实验内容1.表达式的定义：________表达式是由运算符和运算数组成的字符串，它代表了一种计算规则。
2.表达式的分类：________根据运算符的位置和计算顺序，表达式可以分为前缀表达式、中缀表达式和后缀表达式。
3.表达式求值的算法：________1. 前缀表达式求值算法：________1) 创建一个空栈。
2) 从右往左遍历前缀表达式。
3) 如果当前字符是运算符，则将栈顶的两个元素出栈，进行相应的运算，将结果入栈。
4) 如果当前字符是运算数，则将其转化为整数形式，并入栈。
5) 最终栈内只剩下一个元素，即为表达式的求值结果。
2. 中缀表达式求值算法：________1) 将中缀表达式转化为后缀表达式。
2) 创建一个空栈。
3) 从左往右遍历后缀表达式。
4) 如果当前字符是运算符，则将栈顶的两个元素出栈，进行相应的运算，将结果入栈。
5) 如果当前字符是运算数，则将其转化为整数形式，并入栈。
6) 最终栈内只剩下一个元素，即为表达式的求值结果。
3. 后缀表达式求值算法：________1) 创建一个空栈。
2) 从左往右遍历后缀表达式。
3) 如果当前字符是运算符，则将栈顶的两个元素出栈，进行相应的运算，将结果入栈。
4) 如果当前字符是运算数，则将其转化为整数形式，并入栈。
5) 最终栈内只剩下一个元素，即为表达式的求值结果。
4.实验代码实现：________根据算法描述，使用编程语言实现一个表达式求值的程序。
ＸＸXＸXX大学《数据结构》课程设计报告班级：学号：姓名：指导老师:目录一算术表达式求值一、需求分析二、程序得主要功能三、程序运行平台四、数据结构五、算法及时间复杂度六、测试用例七、程序源代码二感想体会与总结算术表达式求值一、需求分析一个算术表达式就是由操作数(oｐeranｄ）、运算符(operator）与界限符（deｌimiter)组成得。
假设操作数就是正整数，运算符只含加减乘除等四种运算符,界限符有左右括号与表达式起始、结束符“#”，如：＃(7+15）*（2３—２8/４）#。
引入表达式起始、结束符就是为了方便.编程利用“算符优先法”求算术表达式得值.二、程序得主要功能（1）从键盘读入一个合法得算术表达式，输出正确得结果。
(2）显示输入序列与栈得变化过程。
三、程序运行平台Ｖｉsｕaｌ C＋+6、0版本四、数据结构本程序得数据结构为栈。
（1）运算符栈部分：struct SqStaｃk ／/定义栈{char *base； //栈底指针ｃｈａr *toｐ; ／/栈顶指针inｔstacｋsiｚe； //栈得长度};inｔInitSｔack (SqＳｔack &ｓ) //建立一个空栈S{ｉf （!(s、ｂａse= (char ＊）ｍalloc(5０＊ｓizeof（chａr）)）)exｉt（0）；ｓ、ｔop=s、bａse;s、staｃksiｚｅ=５0；retuｒn OK；}ｃhar GeｔTop（SqStack s,char &e) /／运算符取栈顶元素｛iｆ (s、ｔop==s、ｂase) //栈为空得时候返回EＲROR｛ﻩ prｉntf(＂运算符栈为空！＼n")；ﻩ reｔurn ERＲＯR;｝elsee＝*（s、ｔoｐ-1); //栈不为空得时候用ｅ做返回值，返回S得栈顶元素，并返回OK returnＯＫ;｝ｉnt Push(SqStacｋ＆s，cｈａr ｅ） //运算符入栈｛if （s、tｏp—s、baｓe >= ｓ、ｓtacksｉzｅ）ﻩ{ｐriｎtf（＂运算符栈满!＼n"）;ﻩs、basｅ=（cｈaｒ*）reａlloｃ(s、bａｓe，(s、sｔackｓｉze+5)*ｓizeoｆ(cｈar））；//栈满得时候,追加5个存储空间ｉf(！s、basｅ)exｉt （OVERＦＬOW）；s、top=s、ｂａsｅ+s、ｓｔacｋsize;s、ｓtaｃksiｚｅ+=５;}ﻩ＊(s、ｔop）＋＋=e；／/把e入栈ﻩｒeturn OK;}ｉnｔ Pop(SqStaｃk &ｓ，char ＆ｅ） /／运算符出栈｛ｉｆ (s、toｐ==s、base) ／/栈为空栈得时候，返回ERＲOＲ｛ｐrintf（＂运算符栈为空!\n”）;ﻩ return ERROＲ;}else｛ﻩﻩe=＊-—ｓ、tｏp；/／栈不为空得时候用e做返回值，删除S得栈顶元素，并返回ＯK return OK；}}iｎt StackTｒaｖerse（ＳqStacｋ&ｓ)／/运算符栈得遍历｛ﻩchar ＊t；ﻩt=s、ｂａｓｅ；ﻩif (s、top＝=s、baｓe）｛ﻩ printｆ（”运算符栈为空！\ｎ”)； //栈为空栈得时候返回ＥＲRORｒeturn ERＲOＲ;}ｗhile（t！＝s、tｏp)｛ﻩﻩｐrｉｎｔf（" %c",＊t)； //栈不为空得时候依次取出栈内元素t++;ﻩ}ｒeturｎ EＲRＯR；｝（2）数字栈部分：strｕｃt SqSｔackn//定义数栈｛ｉnt *bａse; //栈底指针ｉnt＊tｏp； //栈顶指针ｉnｔ sｔacksｉze； //栈得长度｝;inｔIｎｉtStackｎ (SqSｔackn &s) //建立一个空栈Ｓ{s、base=（int＊）malｌoc（50*sｉzeof(int）);if(！ｓ、ｂase）eｘiｔ（OVEＲFLＯW）；//存储分配失败s、top=s、base；s、stacksizｅ=5０;reｔuｒn OK；｝ｉｎt GｅtToｐn(ＳqＳtａcｋn s,inｔ＆e) //数栈取栈顶元素{if（s、ｔop=＝s、base）{prinｔｆ(＂运算数栈为空!\ｎ＂);//栈为空得时候返回ERRORﻩ rｅturｎ ERROR;}eｌseﻩe＝＊（s、toｐ-1);／/栈不为空得时候，用e作返回值，返回S得栈顶元素，并返回OＫreturｎＯK；｝int Pｕshn（SｑStａckn ＆s，int ｅ) //数栈入栈｛if（s、tｏp—s、ｂasｅ＞＝s、stacksiｚe)｛ﻩﻩprｉｎｔf（"运算数栈满!\ｎ"）；／/栈满得时候,追加5个存储空间ﻩs、base=(int＊）realloc (s、baｓe,(s、stａcksize＋5)＊sｉzｅof（ｉnt));ｉf（!s、base) ｅxit (ＯＶERFLOW)；ﻩs、top=ｓ、bａsｅ＋ｓ、stacｋsize;//插入元素e为新得栈顶元素s、stacksｉｚe+=5；}*（s、top）++=e; /／栈顶指针变化returｎOK;}ｉｎt Popｎ(ＳｑSｔacｋn ＆s，iｎt &e)//数栈出栈｛ﻩif （s、top=＝ｓ、base）｛ﻩ pｒiｎtｆ（"运算符栈为空！\n＂);//栈为空栈得视时候，返回ERRＯＲﻩ retｕrn ERROR；ﻩ｝ｅlse｛ﻩﻩe=＊—-ｓ、tｏp；／/栈不空得时候，则删除S得栈顶元素,用e返回其值，并返回OK ﻩreturｎOK；｝}ｉnt StacｋＴraveｒsｅn（SqStackn &s)/／数栈遍历{ﻩiｎｔ＊t;ﻩｔ=s、basｅ ;ﻩif（s、top==s、basｅ）ﻩ｛pｒinｔf(＂运算数栈为空！\n”）；//栈为空栈得时候返回ERRORﻩ rｅｔｕrn ERＲＯＲ；ﻩ｝ﻩwｈile（t！=ｓ、ｔop)ﻩ{priｎtf(” ％d”，*ｔ); /／栈不为空得时候依次输出t＋＋;｝return ERRＯR；｝五、算法及时间复杂度１、算法:建立两个不同类型得空栈,先把一个‘＃’压入运算符栈。
数据结构表达式求值（中缀）实验报告题目名称表达式求值学号姓名指导教师日期一1. 问题描述：在计算机中，算术表达式由常量、变量、运算符和括号组成。
由于不同的运算符具有不同的优先级，又要考虑括号，因此，算术表达式的求值不可能严格地从左到右进行，在程序设计时，借助栈实现。
2. 表达式求值这个程序，主要利用栈和数组，把运算的先后步骤进行分析并实现简单的运算，以字符列的形式从终端输入语法的正确的、不含变量的整数表达式。
利用已知的算符优先关系，实现对算术四则运算的求值，在求值中运用栈、运算栈、输入字符和主要操作的变化过程。
该程序相当于一个简单的计算机计算程序，只进行简单的加减乘除和带括号的四则运算。
1、基本思想（中缀表达式求值）要把一个表达式翻译成正确求值的一个机器指令序列，或者直接对表达式求值，首先要能够正确解释表达式，要了解算术四则运算的规则即：（1）先乘除后加减；（2）从左到右计算；（3）先括号内，后括号外。
下表定义的运算符之间的关系:b + - * / （） # a+ > > < < < > > _ > > < < < > > * > > > > < > > / > > > > < > > ( < < < < < = ) > > > > > > # < < < < < =为了实现运算符有限算法，在程序中使用了两个工作栈。
分别是：运算符栈OPTR,操作数栈OPND.基本思想：（1）首先置操作数栈为空栈，表达式起始符“#”为运算符栈的栈底元素；（2）依次读入表达式中每个字符，若是操作数则进OPND栈，若是运算符则和OPTR栈得栈顶运算符比较优先级后作相应操作。
数据结构课程设计实验报告起止时间：2015.12.28-2015.12.311、输入：tan452、输出：13、执行结果：：设计过程中遇到的问题及解决办法：问题：算数表达式以字符串输入，操作数和操作符的提取；解决办法：两两操作符之间如有数字将中间的数字提取强制转换成double型；参考文献：（在设计中参考的书籍、网站等资料）1. 朱振元，《数据结构——C++语言描述》，清华大学出版社，2008年，页码：2. /detail/gszhouyi/738777指导老师评议：成绩评定：指导教师签名：附件：（程序源代码）#include<stdio.h>#include<stdlib.h>#include<string.h>#include<math.h>#define N 100#define pai 3.1415926typedef struct yxj{char operat;int rank;}yxj;typedef struct str{char data[N];}zs;void sjhs(void){char s[10],a[10];double y,x;printf("请输入(sin cos tan 角度制)表达式：\n");scanf("%s",s);if(strstr(s,"sin")!=0){int i=0,j=0;while(s[i]!='\0'){if(s[i]>='0'&&s[i]<='9')s[j++]=s[i];i++;}s[j]='\0';x=atof(s);y=sin(x*pai/180);}else if(strstr(s,"cos")!=0){int i=0,j=0;while(s[i]!='\0'){if(s[i]>='0'&&s[i]<='9')s[j++]=s[i];i++;}s[j]='\0';x=atof(s);y=cos(x*pai/180);}else if(strstr(s,"tan")!=0){int i=0,j=0;while(s[i]!='\0'){if(s[i]>='0'&&s[i]<='9')s[j++]=s[i];i++;}s[j]='\0';x=atof(s);y=tan(x*pai/180);}else{printf("格式错误\n");return;}printf("%lf\n",y);printf("*****1、继续*****\n");printf("*****0、返回上一层*****\n");scanf("%s",a);if(strcmp(a,"0")==0)return;else if(strcmp(a,"1")==0)sjhs();elseprintf("没有该选项\n");}void szys(yxj mark[]){yxj os[N];char a[10];char ch;double ns[N];zs zhan[20];int numb[N];int Len,p=0,q=1,i,o=1,n=0;char data[N];os[0]=mark[0];ns[0]=0;printf("请输入算术（+ - * / ^）表达式（以= 结束）：\n");scanf("%s",data);if(strcmp(data,"+")==0||strcmp(data,"-")==0||strcmp(data,"*")==0||strcmp(data,"/")==0 ||strcmp(data,"^")==0||strcmp(data,"=")==0){printf("格式错误\n");return;}Len=strlen(data);numb[0]=0;for(i=0;i<20;i++)zhan[i].data[0]='\0';for(i=0;i<Len;i++){int t=0;if((data[i]=='^'||data[i]=='+'||data[i]=='-'||data[i]=='*'||data[i]=='/'||data[i]=='('||data[i]==')'||data[i]=='=')) {int j,k=0;if((data[i]=='='||data[i]=='^'||data[i]=='+'||data[i]=='-'||data[i]=='*'||data[i]=='/')&&(data[i-1]=='^'||data[i-1]=='+'||data[i-1]=='-'||data[i-1]=='*'||data[i-1]=='/')){printf("格式错误\n");return;}numb[q++]=i;while(zhan[(p+k)/2].data[0]!='\0'){k++;}for(j=numb[q-2];j<numb[q-1];j++)if(data[j]>='0'&&data[j]<='9'||data[j]=='.')zhan[(p+k)/2].data[t++]=data[j];zhan[(p+k)/2].data[t]='\0';if(zhan[(p+k)/2].data[0]!='\0')ns[n++]=atof(zhan[(p+k)/2].data);p++;for(j=0;j<8;j++)if(mark[j].operat==data[i])break;while(1){.if(mark[j].operat=='('){os[o++]=mark[j];break;}else if(mark[j].rank>os[o-1].rank&&mark[j].operat!='(') {os[o++]=mark[j];break;}else{double numb1,numb2,numb;switch(ch=os[--o].operat){case '+':{numb1=ns[--n];numb2=ns[--n];numb=numb1+numb2;ns[n++]=numb;break;}case '-':{numb1=ns[--n];numb2=ns[--n];numb=numb2-numb1;ns[n++]=numb;break;}case '*':{numb1=ns[--n];numb2=ns[--n];numb=numb2*numb1;ns[n++]=numb;break;}case '/':{numb1=ns[--n];numb2=ns[--n];if(numb1==0){printf("无效操作\n");return;}else{numb=numb2/numb1;ns[n++]=numb;}break;}case '^':{numb1=ns[--n];numb2=ns[--n];numb=pow(numb2,numb1);ns[n++]=numb;break;}}}}}else if(data[i]>='0'&&data[i]<='9');else if(data[i]=='.');else{printf("格式错误，请重新输入：\n");szys(mark);break;}}printf("%lf\n",ns[0]);printf("*****1、继续*****\n");printf("*****0、返回上一层*****\n");scanf("%s",&a);if(strcmp(a,"0")==0)return;else if(strcmp(a,"1")==0)szys(mark);elseprintf("没有该选项\n");}int main (){yxj mark[9];mark[0].operat='#';mark[0].rank=-1;mark[1].operat='+';mark[1].rank=1;mark[2].operat='-';mark[2].rank=1;mark[3].operat='*';mark[3].rank=2;mark[4].operat='/';mark[4].rank=2;mark[5].operat='(';mark[5].rank=-1;mark[6].operat=')';mark[6].rank=-1;mark[7].operat='=';mark[7].rank=0;mark[8].operat='^';mark[8].rank=3;while(1){char i[10];printf("*****1、四则运算计算器*****\n");printf("*****2、三角函数计算器*****\n");printf("*****0、退出*****\n");scanf("%s",&i);if(strcmp(i,"0")==0)break;else if(strcmp(i,"1")==0)szys(mark);else if(strcmp(i,"2")==0)sjhs();elseprintf("没有该选项\n");}}。
数据结构表达式求值实验报告数据结构表达式求值实验报告⒈引言本实验旨在研究和实现数据结构中表达式求值的算法。
表达式求值是计算机科学中常见的问题，对于计算机程序的正确性和性能具有重要影响。
本报告将详细介绍实验设计、实验步骤、实验结果及分析，并对实验过程中遇到的问题进行讨论。
⒉实验设计⑴实验目的本实验的目的是实现一个可以对常见的算术表达式进行求值的算法，包括支持基本的加减乘除运算符和括号。
⑵实验环境●操作系统：Windows 10●开发语言：C++●开发工具：Visual Studio 2019⑶数据结构设计为了实现表达式求值的算法，我们需要设计适当的数据结构来存储和处理表达式。
本实验中，我们选择使用栈来实现表达式求值。
●表达式栈：用于存储操作数和运算符。
●运算符栈：用于存储运算符。
⑷算法设计表达式求值的算法可以分为以下几个步骤：●遍历表达式，逐个处理操作数和运算符：●如果是操作数，入表达式栈。
●如果是运算符，与运算符栈栈顶元素进行比较，根据优先级决定如何处理。
●当表达式遍历完成后，依次处理剩余的运算符。
●最终表达式栈中的元素即为求值结果。
⒊实验步骤⑴数据结构实现根据设计，我们首先实现表达式栈和运算符栈的数据结构，包括入栈、出栈等操作。
⑵表达式输入与预处理用户输入待求值的表达式，进行预处理，去除空格、验证表达式的合法性等。
⑶表达式求值算法实现根据前述的算法设计，实现表达式求值的算法，利用表达式栈和运算符栈来处理表达式。
⑷测试与结果分析对于不同的测试用例，进行表达式求值的测试，并分析结果的正确性和性能。
⒋实验结果与分析经过实验测试，我们得到了表达式求值的结果。
结果显示，我们的算法能够正确地求得表达式的值，而且性能良好。
⒌讨论与总结在实验过程中，我们遇到了一些问题，并进行了讨论和解决。
通过这个实验，我们更加深入地理解了表达式求值的算法，并对数据结构的应用有了更清晰的认识。
附件：无法律名词及注释：●无。
实验课程名称专业班级学生姓名学号指导教师20 至 20 学年第学期第至周算术表达式求值演示一、概述数据结构课程设计，要求学生在数据结构的逻辑特性和物理表示、数据结构的选择和应用、算法的设计及其实现等方面，加深对课程基本容的理解。
同时，在程序设计方法以及上机操作等基本技能和科学作风方面受到比较系统和严格的训练。
在这次的课程设计中我选择的题目是算术表达式求值演示。
表达式计算是实现程序设计语言的基本问题之一，也是栈的应用的一个典型例子。
设计一个程序，演示用算符优先法对算术表达式求值的过程。
深入了解栈和队列的特性，以便在解决实际问题中灵活运用它们，同时加深对这种结构的理解和认识。
二、系统分析1．以字符列的形式从终端输入语确的、不含变量的整数表达式。
利用已知的算符优先关系，实现对算术四则混合运算表达式的求值，并仿照教科书的例子在求值中运算符栈、运算数栈、输入字符和主要操作的变化过程。
2．一般来说，计算机解决一个具体问题时，需要经过几个步骤：首先要从具体问题抽象出一个适当的数学模型，然后设计一个解决此数学模型的算法，最后编出程序，进行测试，调试直至得到想要的答案。
对于算术表达式这个程序，主要利用栈，把运算的先后步骤进行分析并实现简单的运算！为实现算符优先算法，可以使用两个栈，一个用以寄存运算符，另一个用以寄存操作数和运算结果。
3．演示程序是以用户于计算机的对话方式执行，这需要一个模块来完成使用者与计算机语言的转化。
4．程序执行时的命令：本程序为了使用具体，采用菜单式的方式来完成程序的演示，几乎不用输入什么特殊的命令，只需按提示输入表达式即可。
（要注意输入时格式，否者可能会引起一些错误）5. 测试数据。
三、概要设计一个算术表达式中除了括号、界限符外，还包括运算数据和运算符。
由于运算符有优先级别之差，所以一个表达式的运算不可能总是从左至右的循序执行。
每次操作的数据或运算符都是最近输入的，这与栈的特性相吻合，故本课程设计借助栈来实现按运算符的优先级完成表达式的求值计算。
算法设计程序包含三个模块(1) 主程序模块，其中主函数为void main{输入表达式；根据要求进行转换并求值；输出结果；}(2) 表达式求值模块——实现具体求值。
(3) 表达式转换模块——实现转换。
各个函数之间的调用关系栈的抽象数据类型定义ADT SqStack{数据对象：D={a i| a i∈ElemSet,i=1,2,3……，n,n≥0}数据关系：R1={<a i-1,a i>| a i-1,a i∈D,i=1,2,3,……，n}约定其中a i端为栈底，a n端为栈顶。
操作集合：(1)void InitStack1(SqStack1 &S1);//声明栈建立函数(2)void InitStack2(SqStack2 &S2);//声明栈建立函数(3)void evaluate(SqStack1 &S1,SqStack2 &S2);//确定如何入栈函数(4)void Push1(SqStack1 &S1,char e);//声明入栈函数(5)void Push2(SqStack2 &S2,float e);//声明入压栈函数(6)char GetTop1(SqStack1 &S1);//声明取栈顶元素函数(7)float GetTop2(SqStack2 &S2);//声明取栈顶元素函数(8)char Pop1(SqStack1 &S1);//声明出栈函数(9)float Pop2(SqStack2 &S2);//声明出栈函数(10)char Compare(char m,char n);//声明比较函数(11)float Operate(float a,char rheta,float b);//声明运算函数(12)void DispStack1(SqStack1 &S1);//从栈底到栈顶依次输出各元素(13)void DispStack2(SqStack2 &S2);//从栈底到栈顶依次输出各元素}ADT SqStack结构分析:栈中的数据节点是通过数组来存储的。
因为在C语言中数组是用下标从零开始的，因此我们在调用他们的数据是要特别注意。
指针变量的值要么为空(NULL)，不指向任何结点；要么其值为非空，即它的值是一个结点的存储地址。
注意，当P为空值时，则它不指向任何结点，此时不能通过P来访问结点，否则会引起程序错误。
如果输入的数字不符合题目要求，则会产生错误结果。
算法的时空分析：时间和空间性能分析：时间上，对于含n个字符的表达式，无论是对其进行合法性检测还是对其进行入栈出栈操作n次，因此其时间复杂度为O(n)。
空间上，由于是用数组来存储输入的表达式，用栈来存储运算中的数据和运算符，而栈的本质也用到的数组，数组在定义时必须确定其大小。
在不知表达式长度的情况下确定数组的长度确非易事，此时极易造成空间的浪费，因此空间性能不是很好。
四、详细设计源程序#include<iostream>using namespace std;#define STACK_INIT_SIZE 100#define STACKINCREMENT 10typedef struct //运算符栈{char *base;char *top;int stacksize;}SqStack1;typedef struct //运算数栈{float *base;float *top;int stacksize;}SqStack2;void InitStack1(SqStack1 &S1);//声明栈建立函数void InitStack2(SqStack2 &S2);//声明栈建立函数void evaluate(SqStack1 &S1,SqStack2 &S2);//确定如何入栈函数void Push1(SqStack1 &S1,char e);//声明入栈函数void Push2(SqStack2 &S2,float e);//声明入压栈函数char GetTop1(SqStack1 &S1);//声明取栈顶元素函数float GetTop2(SqStack2 &S2);//声明取栈顶元素函数char Pop1(SqStack1 &S1);//声明出栈函数float Pop2(SqStack2 &S2);//声明出栈函数char Compare(char m,char n);//声明比较函数float Operate(float a,char rheta,float b);//声明运算函数void DispStack1(SqStack1 &S1);//从栈底到栈顶依次输出各元素void DispStack2(SqStack2 &S2);//从栈底到栈顶依次输出各元素/*主函数*/void main(){SqStack1 S1;//定义运算符栈SqStack2 S2;//定义运算数栈//freopen("data1.in","r",stdin);//freopen("data1.out","w",stdout);InitStack1(S1);//调用栈建立函数InitStack2(S2);//调用栈建立函数evaluate(S1,S2);//调用确定如何入栈函数cout<<"按任意键结束!"<<endl;}/*运算符栈函数*/void InitStack1(SqStack1 &S1)//构造一个空栈S1{S1.base=(char *)malloc(STACK_INIT_SIZE *sizeof(char));if(!S1.base)cout<<"存储分配失败！";//存储分配失败S1.top=S1.base;S1.stacksize=STACK_INIT_SIZE;}void Push1(SqStack1 &S1,char e)//入栈{if(S1.top-S1.base>=S1.stacksize)//如果栈满，追加存储空间{S1.base=(char *)realloc(S1.base,(S1.stacksize+STACKINCREMENT)*sizeof(char));if(!S1.base) cout<<"存储分配失败！";else{S1.top=S1.base+S1.stacksize;S1.stacksize=S1.stacksize+STACKINCREMENT;}}*S1.top=e;S1.top=S1.top+1;//将元素压入栈中，指针上移}char GetTop1(SqStack1 &S1)//取栈顶元素{char e;if(S1.top==S1.base)cout<<"\n\t\t\t运算符栈已空!\n";else e=*(S1.top-1);return e;}void DispStack1(SqStack1 &S1)//从栈底到栈顶依次输出各元素{char e,*p;if(S1.top==S1.base)cout<<" ";else{p=S1.base;while(p<S1.top){e=*p;p++;cout<<e;}}}char Pop1(SqStack1 &S1)//出栈{char e;if(S1.top==S1.base)cout<<"\n\t\t\t运算符栈已空!\n";e=*(--S1.top);return e;}/*运算数栈函数*/void InitStack2(SqStack2 &S2)//构造一个空栈S2{S2.base=(float *)malloc(STACK_INIT_SIZE *sizeof(float));if(!S2.base)cout<<"存储分配失败！";//存储分配失败S2.top=S2.base;S2.stacksize=STACK_INIT_SIZE;}void Push2(SqStack2 &S2,float e)//入栈{if(S2.top-S2.base>=S2.stacksize)//栈满，追加存储空间{S2.base=(float *)realloc(S2.base,(S2.stacksize+STACKINCREMENT)*sizeof(float));if(!S2.base)cout<<"存储分配失败！";else{S2.top=S2.base+S2.stacksize;S2.stacksize=S2.stacksize+STACKINCREMENT;}}*S2.top=e;S2.top=S2.top+1;//将元素e入栈，指针上移}void DispStack2(SqStack2 &S2)//从栈底到栈顶依次输出各元素{float e,*p;if(S2.top==S2.base)cout<<" ";else{p=S2.base;while(p<S2.top){e=*p;p++;cout<<e;}}}float GetTop2(SqStack2 &S2)//取栈顶元素{float e;if(S2.top==S2.base) cout<<"\n\t\t运算数栈已空!";else e=*(S2.top-1);return e;}float Pop2(SqStack2 &S2)//出栈{float e;if(S2.top==S2.base)cout<<"\n\t\t运算数栈已空!";e=*(--S2.top);return e;}/*确定如何入栈函数*/void evaluate(SqStack1 &S1,SqStack2 &S2){char c;float t,e;int n=0,i=1,j=0,k=0,l=0;char ch[STACK_INIT_SIZE];int s=1;int flag=0,flag2=0;float p1,p2;char ch1;Push1(S1,'#');//将'#'入栈，作为低级运算符cout<<"●请输入不含变量的表达式（以#结束!）：\n ";cin>>ch;c=ch[0];cout<<"\n●对表达式求值的操作过程如下："<<"\n______________________________________________________________________________ __\n"<<"步骤\t运算符栈S1\t运算数栈S2\t输入字符\t\t主要操作";while(c!='#'||GetTop1(S1)!='#'){cout<<"\n__________________________________________________________________________ ______\n";cout<<i++<<"\t";DispStack1(S1);cout<<"\t\t";DispStack2(S2);cout<<"\t\t";if(flag==1){k--;flag=0;}if(flag2){k+=flag2;flag2=0;}for(l=0;l<k;l++)cout<<' ';for(j=k;ch[j]!='\0';j++)cout<<ch[j];if(ch[k]!='#'&&flag!=1) {k++;flag=0;}as:if(!(c=='+'||c=='-'||c=='*'||c=='/'||c=='('||c==')'||c=='#')){//输入的字符如果不是运算符号，则继续输入直到输入的是运算符为止，将非运算符转换成浮点数if(!(c=='.')&&n>=0){e=float(c-48);n++;if(n==1)t=e;else if(n>1)t=t*10+e;c=ch[s++];}if(n==-1){e=float(c-48);t=t+e/10;c=ch[s++];}if(c=='.'){n=-1;c=ch[s++];}if((c>='0'&&c<='9')||c=='.'){flag2++;goto as;}if(c<'0'||c>'9'){Push2(S2,t);}cout<<"\t\tPush2(S2,"<<t<<")";}else//输入的是运算符{n=0;//非运算型数据计数器清零switch(Compare(GetTop1(S1),c))//比较运算符的优先级{case '<'://栈顶元素优先级低，则入栈且继续输入Push1(S1,c);cout<<"\t\tPush1(S1,"<<c<<")";c=ch[s++];break;case '='://栈顶元素优先级相等，脱括号并接收下一字符Pop1(S1);cout<<"\t\tPop1(S1)";c=ch[s++];break;case '>'://栈顶元素优先级高，则退栈并将运算结果入栈p1=Pop2(S2);p2=Pop2(S2);ch1=Pop1(S1);Push2(S2,Operate(p2,ch1,p1));cout<<"\t\tOperate("<<p2<<','<<ch1<<','<<p1<<')';flag=1;break;}}}cout<<"\n__________________________________________________________________________ ______\n";cout<<i<<'\t'<<'#'<<"\t\t"<<GetTop2(S2)<<"\t\t";for(j=0;j<k;j++) cout<<' ';cout<<"#"<<"\t\t"<<"RETURN(GETTOP(S2))";cout<<"\n__________________________________________________________________________ ______\n";if(S2.top-1==S2.base)//显示表达式最终结果cout<<"\n●表达式的结果为："<<GetTop2(S2)<<endl;else cout<<"\n表达式出错!\n";}char Compare(char m,char n)//运算符的优先级比较{if(n=='+'||n=='-')//输入符号为"+"、"-"{if(m=='('||m=='#')return '<';//栈顶元素为"("、"#",此时栈顶符号优先级低，返回"<"else return '>';//否则，栈顶符号优先级高,返回">"}else if(n=='*'||n=='/')//输入的符号为"*"、"/"{if(m==')'||m=='*'||m=='/')return '>';//栈顶元素为")"、"*"、"/",此时栈顶符号优先级高，返回">"else return '<';//否则，栈顶符号优先级低,返回"<"}else if(n=='(')return'<';//输入的符号为"(",则直接返回"<"else if(n==')')//输入的符号为")"{if(m=='(')return'=';//栈顶元素为"(",此时优先级同，返回"="else return '>';//否则，栈顶符号优先级高,返回">"}else //输入符号为其他{if(m=='#')return'=';//栈顶元素为"#",此时优先级同，返回"="else return '>';//否则，栈顶符号优先级高,返回">"}}float Operate(float a,char theta,float b)//运算函数{float tmp=0;if (theta=='+')tmp=a+b;//从运算符栈取出的符号为"+"，则运算数栈的两元素相加，并返回else if(theta=='-')tmp=a-b;//从运算符栈取出的符号为"-"，则运算数栈的两元素相减，并返回else if(theta=='*')tmp=a*b;//从运算符栈取出的符号为"*"，则运算数栈的两元素相乘，并返回else if(theta=='/') //从运算符栈取出的符号为"/"，则运算数栈的两元素相除，并返回{if(b==0) cout<<"\n表达式出错!除数不能为0!\n";else tmp=a/b;}return tmp;}五、运行与测试第六章总结与心得数据结构的研究不仅涉及到计算机硬件的研究，而且和计算机软件的研究有着更密切的关系，无论是编译程序还是操作系统，都涉及到数据元素在存储器中的分配问题。
