《数据结构--表达式求值》由会员分享，可在线阅读，更多相关《数据结构--表达式求值（6页珍藏版）》请在金锄头文库上搜索。
1、数据结构实验报告班级: 姓名: 学号:E-mail: 日期:1、 实验题目: 表达式求值实验目的：使用键盘输入表达式，计算表达式的值并输出；将表达式转化成后缀表达式输出，利用后缀表达式求表达式的值并输出。实验内容：用栈来处理表达式，先将表达式转换成后缀表达式，在求值。1、需求分析程序设计的任务是将键盘输入的表达式转换成后缀表达式，再对其求值。1、输入的形式为“#表达式#”，表达式为一般的四则混合运算表达式；2、输出的形式如：后缀表达式：* 表达式的值：*；3、程序所能达到的功能有将输入的字符串转化为后缀表达式，再对其求值；4、程序执行的命令包括：（1）输入字符串（表达式） （2）将表达式转化为
2、后缀表达式（3）将表达式中的数字字符转化为数字（4）比较运算符的优先级（5）对表达式求值（6）输出后缀表达式（7）输出表达式的值（8）结束。5、测试数据：输入表达式：2+3*(8-2)/2+5后缀表达式：2382-2/*5+表达式的值=16 二 概要设计基本操作：1.void InitStack_char(SqStack_char *S)/创建一个 char 型栈2.void InitStack_int(SqStack_int *S)/创建一个 int 型栈3.void Push_char(SqStack_char *S,SElemType1 e)/向栈中输入 cahr 元素4.void Pu
3、sh_int(SqStack_int *S,SElemType2 e)/向栈中输入 int 元素5.char Pop_char(SqStack_char *S )/从栈顶取出一 char 个元素6.int Pop_int(SqStack_int *S )/从栈顶取出一 int 个元素7.char Precede(SqStack_char *OPTR, char c1)/比较两个运算符的优先级8.int Get_numeral(char *p)/计算字符数组中的数值9.int count(int a,int b,char c)/计算数值10.void Posture_Count(char *p,
4、SqStack_char *OPTR,SqStack_int *OPND) /表达式的求值11.void Scanf(char *p)/表达式的输入12.void suffix(char *c,SqStack_char* O1,SqStack_char* O2)/求后缀表达式模块调用图主程序模块创建栈表达式的输入求后缀表达式比较运算符的优先级求运算符的值比较运算符的优先级计算求值输出三 详细设计数据结构：typedef struct /char 栈的数据结构SElemType1 *base;SElemType1 *top;int stscksize;SqStack_char;typedef s
5、truct /int 栈的数据结构SElemType2 *base;SElemType2 *top;int stscksize;SqStack_int;每一个模块主函数int main()SqStack_char OPTR,Q;SqStack_int OPND;char cN; /表达式字符数组int i;printf(输入表达式n);Scanf(c);/输入表达式InitStack_char(&OPTR);/用于求后缀表达式的 stackInitStack_char(&Q);/用于求后缀表达式的 stacksuffix(c,&OPTR,&Q);/求后缀表达式InitStack_char(&O
6、PTR);/用于表达式求值的 char stack InitStack_int(&OPND);/用于表达式求值的 int stackPosture_Count(c,&OPTR,&OPND);/表达式求值i=Pop_int(&OPND);/结果的输出printf(表达式的值=%dn,i);return 0;创建一个栈void InitStack_char(SqStack_char *S) /创建一个 char 型栈S-base=(SElemType1 *)malloc(STACK_INIT_SIZE*sizeof(SElemType1);if(!S-base) exit(ERROR);S-top
7、=S-base;S-stscksize=STACK_INIT_SIZE;向栈中输入元素void Push_char(SqStack_char *S,SElemType1 e) /向栈中输入 cahr 元素if(S-top-S-baseS-stscksize) /栈满 重新申请空间S-base=(SElemType1 *)realloc( S-base,(S-stscksize+STACKINCREMENT)*sizeof(SqStack_char);if(!S-base) exit(ERROR);S-top=S-base+S-stscksize;S-stscksize+=STACKINCREM
8、ENT;*(S-top+)=e; 从栈顶取出个元素char Pop_char(SqStack_char *S ) /从栈顶取出一 char 个元素SElemType1 p;if(S-top=S-base) exit(ERROR) ;/如果栈空 出错elsep=*(-S-top);return p;比较两个运算符的优先级char Precede(SqStack_char *OPTR, char c1)/比较两个运算符的优先级char c,c2;c2=*(OPTR-top-1);if (c1=+)if(c2=+|c2=-|c2=)|c2=(|c2=#)c=;if(c2=*|c2=/)c=0;i-)
9、 /计算字符数组中的数的大小for (j=i-1;j0;j-)s*=10; T+=(*(p+k)-48)*s;/用码计算数的大小s=1;k+;return T;计算数值int count(int a,int b,char c) /计算数值if(c=+) a+=b;if(c=-) a-=b;if(c=*) a*=b;if(c=/) a/=b;return a;表达式的求值void Posture_Count(char *p,SqStack_char *OPTR,SqStack_int *OPND)/表达式的求值char c,c1;int k,num1,num2;c=*p;while (c!=0)
10、if (0=c&c=9) k=Get_numeral(p); /找出数值的大小Push_int(OPND,k);while(0=*p&*p=9)/将指针移到运算符处p+;c=*p;.求后缀表达式void suffix(char *c,SqStack_char* O1,SqStack_char* O2)/求后缀表达式char *p,c1;p=c;Push_char(O2,*p);p+;while(*p!=0)if(0=*p&*p=9) /将数字直接压入栈 O1Push_char(O1,*p);p+; .表达式的输入void Scanf(char *p)/表达式的输入char c;*(p)=#;/
11、开始时的#c=getchar();while (c!=n)*(+p)=c;c=getchar();*(+p)=#;/结束时的#*(+p)=0;四 使用说明、测试分析及结果运行界面 Microsoft Visual C+测试结果编写程序的过程：1.设计抽象数据结构2.设计栈的基本操作的算法3.设计求后缀表达式的算法4.设计求表达式的值的算法5.上机编程6.调试程序本次试验在上机的时候写了很多函数，但是很多都没有注释，导致在调试的花了很多时间去读程序，这是一个不好的做法，在今后的试验中会严格要求自己，一定吧注释加上。还有在调试的时候，会发现在做算法的时候，有些东西没有考虑完全，导致结果和预期的不一样。5、实验总结在这个程序中，没有在写程序的时候把注释一起写上，给后面加注释和调试程序带来了很大的困难。所以在今后的试验中，一定要在写程序的时候顺便吧注释加上。其次，在算法方面，有些懂在写的时候没有考虑进去，有些细节的东西都是在调试的时候才发现的。最后，C 语句在一些地方值得提高，有一些语句可能没有得到优化。C 还得加强。教师评语：实验成绩：指导教师签名： 批阅日期：
