• / 33
  • 下载费用:10 金币  

数据结构实验二——算术表达式求值实验报告.doc

关 键 词:
数据结构实验二——算术表达式求值实验报告.doc
资源描述:
3e52ca69dce03fe5bc15556a14d1b663.pdf第 1 页 共 33 页《数据结构与数据库》实验报告实验题目算术表达式求值学 院:化学与材料科学学院专业班级:09 级材料科学与工程系 PB0920603姓 名:李维谷学 号:PB09206285 邮 箱:liwg@mail.ustc.edu.cn指导教师:贾伯琪实验时间:2010 年 10 月 10 日一、 需要分析问题描述:3e52ca69dce03fe5bc15556a14d1b663.pdf第 2 页 共 33 页表达式计算是实现程序设计语言的基本问题之一,它的实现是栈的应用的一个典型例子。设计一个程序,演示通过将数学表达式字符串转化为后缀表达式,并通过后缀表达式结合栈的应用实现对算术表达式进行四则混合运算。问题分析:在计算机中,算术表达式由常量、变量、运算符和括号组成。由于不同的运算符具有不同的优先级,又要考虑括号,因此,算术表达式的求值不可能严格地从左到右进行。因而在程序设计时,借助栈实现。设置运算符栈(字符型)和运算数栈(浮点型)辅助分析算符优先关系。在读入表达式的字符序列的同时完成运算符和运算数的识别处理,然后进行运算数的数值转换在进行四则运算。在运算之后输出正确运算结果,输入表达式后演示在求值中运算数栈内的栈顶数据变化过程,最后得到运算结果。算法规定:输入形式:一个算术表达式,由常量、变量、运算符和括号组成(以字符串形式输入) 。为使实验更完善,允许操作数为实数,操作符为(、 ) 、.(表示小数点) 、+、-、*、/、^(表示乘方) ,用#表示结束。输出形式:演示表达式运算的中间结果和整个表达式的最终结果,以浮点型输出。程序功能:对实数内的加减乘除乘方运算能正确的运算出结果,并能正确对错误输入和无定义的运算报错,能连续测试多组数据。测试数据:正确输入:12*(3.6/3+4^2-1)# 输出结果:194.43e52ca69dce03fe5bc15556a14d1b663.pdf第 3 页 共 33 页无定义运算:12*(3.6/(2^2-4)+1)#输出结果:表达式出错,除数为 0,无意义错误输入:12+s#输出结果:ERROR!二、 概要设计拟采用两种类型的展分别对操作数和操作符进行操作。程序中将涉及下列两个抽象数据类型:1、设定“操作数”的栈的抽象数据类型定义:ADT SqStack_f{数据对象:D={ ia},NiR数据关系:R1={| , ,i=2,…,n}1,iiDai约定 端为栈顶, 端为栈底。ni基本操作:InitStack_f( //存储实型数据元素的一位数组float *top; //栈顶指针int stacksize; //栈数组容量}SqStack_f; //有序存储实型的顺序表类型typedef struct{char *base; //存储字符数据元素的一位数组char *top; //栈顶指针int stacksize; //栈数组容量}SqStack_c; //有序存储字符型的顺序表类型void InitStack_f(SqStack_f *s)void InitStack_f(SqStack_f *s)//构造一个存储实型(字符型)的空栈,预设空间为 100,分配失败就退出void GetTop_f(SqStack_f *s,float *e)void GetTop_c(SqStack_c *s,char *e)//若栈 s 不空,则以 e 带值返栈顶元素,否则显示错误 “ERROR”,并退出程序void Push_f(SqStack_f *s,float e)void Push_c(SqStack_c *s,char e)//在 s 的栈顶插入新的栈顶元素 e,若栈的当前空间已满,则追加存储空间void Pop_f(SqStack_f *s,float *e)3e52ca69dce03fe5bc15556a14d1b663.pdf第 7 页 共 33 页void Pop_c(SqStack_c *s,char *e)//若栈 s 不空,则删除栈 s 的栈顶元素,用 e 带值返回,否则退出程序其中部分操作的伪码算法(由于比较类似,以浮点型的栈为例)void InitStack_f(SqStack_f *s){//构造一个存储实型的空栈,预设空间为 100,分配失败就退出s-base=(float *)malloc(TTACK_INIT_SIZE*sizeof(float));if(!s-base)exit(1);s-top=s-base;s-stacksize=TTACK_INIT_SIZE;}void GetTop_f(SqStack_f *s,float *e){//若栈 s 不空,则以 e 带值返栈顶元素,否则显示错误“ERROR”,并退出程序if(s-top==s-base){printf(“ERROR!\n“);exit(1);}*e=*(s-top-1);}3e52ca69dce03fe5bc15556a14d1b663.pdf第 8 页 共 33 页void Push_f(SqStack_f *s,float e){//在 s 的栈顶插入新的栈顶元素 e,若栈的当前空间已满,则追加存储空间if(s-top-s-base=s-stacksize){s-base=(float *)realloc(s-base,(s-stacksize+STACKINCREMENT)*sizeof(float));if(!s-base){printf(“OVERFLOW!\n“);exit(1);}s-top=s-base+s-stacksize;s-stacksize+=STACKINCREMENT;}*s-top++=e;}void Pop_f(SqStack_f *s,float *e){//若栈 s 不空,则删除栈 s 的栈顶元素,用 e 带值返回,否则退出程序if(s-top==s-base)exit(1);*e=*--s-top;}3e52ca69dce03fe5bc15556a14d1b663.pdf第 9 页 共 33 页3、判断运算符优先级的算法:算符间的优先关系如下:+ - * / ( ) #+ = - = * = / = ( # =pre[1]) //栈顶元素优先级高返回 1return 1;elsereturn 0; //否则返回 0}4、中缀表达式转换为后缀表达式的算法:算法过程描述:1) 首先将左括号“(”压进栈,作为栈底元素;2) 从左而右对算数表达式进行扫描,每次读入一个字符 s1[i];3) 若遇到数字或小数点,则立即写入 s2[i],若遇算数运算符,将“ ”(空格)写入 s2[i];4) 遇到左括号“(”则压栈;5) 若遇算术运算符,如果它们的优先级比栈顶元素高,则直接进栈,否则3e52ca69dce03fe5bc15556a14d1b663.pdf第 11 页 共 33 页弹出栈顶元素输出到 s2[i],直到新栈顶元素的优先级比它低,然后将它压栈;6) 若遇到右括号“) ”,则将栈顶元素输出到 s2[i],直到栈顶元素为“(” ,然后相互抵消;7) 当扫描到“#”符号,表明表达式串已全部输入,将栈中的运算符全部输出到 s2[i],并删除栈顶元素。伪码算法:void Translate(char *s1){ //中缀表达式转换为后缀表达式char s2[80];SqStack_c Optr;int i=0,j=0;char t;InitStack_c(//初始化一个存储字符型的空栈,便于存储运算符Push_c(// 首先将左括号“(”压进栈,作为栈底元素while(s1[i]!='#') //当扫描到的不是“#” ,即表达式串没结束时{if(s1[i]='0' }elseswitch(s1[i]) //扫描到的是运算符 {case'(':Push_c(break;// 遇到左括号“(”则压栈case')':Pop_c( //若遇到右括号“) ”,则将栈顶元素输出到 s2[i]while(t!='(') //直到栈顶元素为 “(” ,然后相互抵消{s2[j++]=t;Pop_c(}break;default:while(GetTop_c(//栈顶元素优先级高,则弹出到 s2[i]s2[j++]=t;}Push_c(//栈顶元素优先级低,直接压栈}i++;3e52ca69dce03fe5bc15556a14d1b663.pdf第 13 页 共 33 页}Pop_c(while(t!='(') //表达式串已结束,栈中的运算符全部输出到 s2[i],并删除栈顶元素{s2[j++]=t;Pop_c(}for(i=0;i='0' j--;}}i++;Push_f(s,m);GetTop_f(s,printf(“The result is:%g\n“,m);}else //读入的为运算符{Pop_f(s,//弹出栈顶元素Pop_f(s,//弹出次顶元素3e52ca69dce03fe5bc15556a14d1b663.pdf第 16 页 共 33 页switch(s2[i]){//让栈顶和次顶元素与次运算符进行相应的运算,运算结果打印并进栈case '+':z=y+x;printf(“The result is:%g\n“,z);break;case '-':z=y-x;printf(“The result is:%g\n“,z);break;case '*':z=y*x;printf(“The result is:%g\n“,z);break;case '/':if(x==0){//报错功能printf(“表达式出错,除数为 ‘0’,无意义\n“);exit(1);}else{z=y/x;printf(“The result is:%g\n“,z);break;}case '^':z=1;for(j=1;j#include#include#define TTACK_INIT_SIZE 100#define STACKINCREMENT 10typedef struct{float *base;float *top;int stacksize;}SqStack_f;typedef struct{char *base;3e52ca69dce03fe5bc15556a14d1b663.pdf第 23 页 共 33 页char *top;int stacksize;}SqStack_c;void InitStack_f(SqStack_f *s){s-base=(float *)malloc(TTACK_INIT_SIZE*sizeof(float));if(!s-base)exit(1);s-top=s-base;s-stacksize=TTACK_INIT_SIZE;}void InitStack_c(SqStack_c *s){s-base=(char *)malloc(TTACK_INIT_SIZE*sizeof(char));if(!s-base)exit(1);s-top=s-base;s-stacksize=TTACK_INIT_SIZE;}void GetTop_f(SqStack_f *s,float *e){if(s-top==s-base)3e52ca69dce03fe5bc15556a14d1b663.pdf第 24 页 共 33 页{printf(“ERROR!\n“);exit(1);}*e=*(s-top-1);}void GetTop_c(SqStack_c *s,char *e){if(s-top==s-base){printf(“ERROR!\n“);exit(1);}*e=*(s-top-1);}void Push_f(SqStack_f *s,float e){if(s-top-s-base=s-stacksize){s-base=(float *)realloc(s-base,(s-stacksize+STACKINCREMENT)*sizeof(float));if(!s-base)3e52ca69dce03fe5bc15556a14d1b663.pdf第 25 页 共 33 页{printf(“OVERFLOW!\n“);exit(1);}s-top=s-base+s-stacksize;s-stacksize+=STACKINCREMENT;}*s-top++=e;}void Push_c(SqStack_c *s,char e){if(s-top-s-base=s-stacksize){s-base=(char *)realloc(s-base,(s-stacksize+STACKINCREMENT)*sizeof(char));if(!s-base){printf(“OVERFLOW!\n“);exit(1);}s-top=s-base+s-stacksize;s-stacksize+=STACKINCREMENT;3e52ca69dce03fe5bc15556a14d1b663.pdf第 26 页 共 33 页}*s-top++=e;}void Pop_f(SqStack_f *s,float *e){if(s-top==s-base)exit(1);*e=*--s-top;}void Pop_c(SqStack_c *s,char *e){if(s-top==s-base)exit(1);*e=*--s-top;}int precede(char Top_char,char s1_char){int i,pre[2];char op[2];op[0]=Top_char;op[1]=s1_char;for(i=0;i=pre[1])return 1;elsereturn 0;}void Translate(char *s1){char s2[80];SqStack_c Optr;int i=0,j=0;char t;InitStack_c(Push_c(while(s1[i]!='#'){3e52ca69dce03fe5bc15556a14d1b663.pdf第 28 页 共 33 页if(s1[i]='0' }elseswitch(s1[i]){case'(':Push_c(break;case')':Pop_c(while(t!='('){s2[j++]=t;Pop_c(}break;default:while(GetTop_c(s2[j++]=t;}3e52ca69dce03fe5bc15556a14d1b663.pdf第 29 页 共 33 页Push_c(}i++;}Pop_c(while(t!='('){s2[j++]=t;Pop_c(}for(i=0;i='0' j--;}}i++;Push_f(s,m);GetTop_f(s,printf(“The result is:%g\n“,m);}
展开阅读全文
  微传网所有资源均是用户自行上传分享,仅供网友学习交流,未经上传用户书面授权,请勿作他用。
0条评论

还可以输入200字符

暂无评论,赶快抢占沙发吧。

关于本文
本文标题:数据结构实验二——算术表达式求值实验报告.doc
链接地址:https://www.weizhuannet.com/p-10052000.html
微传网是一个办公文档、学习资料下载的在线文档分享平台!

网站资源均来自网络,如有侵权,请联系客服删除!

 网站客服QQ:80879498  会员QQ群:727456886

copyright@ 2018-2028 微传网络工作室版权所有

     经营许可证编号:冀ICP备18006529号-1 ,公安局备案号:13028102000124

收起
展开