




已阅读5页,还剩14页未读, 继续免费阅读
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
课程设计实验报告实验名称:表达式类型的实现编译环境:硬件:PC软件:VS2010问题描述 一个表达式和一棵二叉树之间,存在着自然的对应关系。写一个程序,实现基于二叉树表示的算术表达式Expression的操作。基本要求假设算术表达式Expression可以含有变量(az)、常量(09)和二元运算符(+,-,*,/,(乘幂)。实现以下操作。(1) ReadExpr(E)以字符序列的形式输入语法正确的前缀表示式并构造表达式E。(2) WriteExpr(E)用带括弧的前缀表示式输出表达式E。(3) Assign(V,c)实现对变量V的赋值(V=c),变量的初值为0。(4) Value(E)对算术表达式E求值。(5) CompoundExpr(P,E1,E2)构造一个新的复合表达式(E1)P(E2)。选作内容:(1) 增加常数合并操作MergeConst(E)-合并表达式中E的所有常数运算。例如:表达式E=2+2*1-A进行合并常数的操作后,求得E=4-A (2)以表达式的原书写形式输入需求分析1以字符序列的形式输入语法正确的中缀表示式并构造表达式E。即要根据正确的前缀式建立一棵二叉树T。 2用带括弧的前缀表达式输出表达式E。即要求在前缀遍历二叉树的时候考虑运算符的优先级,在适当的位置输出括弧。3实现对变量V的赋值(Vc),变量的初值为0。那就在中缀遍历二叉树的过程中比较结点的值是否为V,找到V以后将c赋给V。4对算术表达式E求值。如果表达式中有变量的话,首先提示用户表达式中变量,建议先执行操作3(实现对变量V赋值),执行完后再回来执行表达式求值这一步骤。表达式求值利用递归,如果某个结点的值为运算符并且它的左右孩子结点的值为数据,那么就把(左孩子)(运算符)(右孩子)的结果赋给该结点。一层一层往上,最后只剩下一个根结点。此时根结点的值就是表达式E的值。5构造一个新的复合表达式(E1)P(E2)。只要先构造表达式E1的二叉树和E2的二叉树,然后利用P把这两棵二叉树连接起来构成一棵新的二叉树。6合并表达式E中所有常数运算。此原理类似于对表达式E求值,不同之处只在于该功能只对常数合并。概要设计1. 树的抽象数据类型定义:ADT Tree数据对象 D: D是具有相同特性的数据元素的集合。数据关系 R: 若D为空集,则称为空树;若D仅含一个数据元素,则R为空集,否则R=H,H是如下二元关系:(1) 在D中存在唯一的称为根的数据元素root,它在关系H下无前驱;(2) 若D-root,则存在D-root的一个划分D1,D2,Dm(m0),对任意jk(1=j,k=m)有DjDk = ,且对任意的i(1im),唯一存在数据元素XiDi,有H;(3) 对应于D-root的划分,H - 有唯一的一个划分H1,H2Hm(m0),对任意jk(1=j,k=m)有DjDk = ,且对任意的i(1im),Hi是Di上的二元关系,(Di,Hi)是一棵符合本定义的树,称为根的root的子树。基本操作: Double Expression (char *exp);功能: 算术表达式求值 double calculate (double opnd1,char op,double opnd2 ); 功能: 操作数四则运算 void push( char , char, double , ExpressionCalculateStack *); 功能:入栈 double pop ( char , ExpressionCalculateStack *); 功能:出栈 void GetNextNotation ( char *notation,char *exp); 功能:读下一个运算符或操作数 char GetTypeOfNotation( char *notation ); 功能:判定是运算符或是操作数int CompareOpPrior(char op2, char op1); 功能:运算符优先级别比较 BTNode *ReadExpr(char s,int i,int j)功能:读入表达式void WriteExpr(BTNode *b) 功能:/把输入的表达式转换为相应的二叉树,并以前缀表达式的形式输出char Seek(char s,int k)功能:判断是否有字母输入void CompoundExpr(char E1,char E2,char p)功能:复合表达式void Assign(char s,char i,char j)功能:对变量进行复制流程图:Mian函数对算术表达式求值查找式中的变量Seek以中缀方式输入表达式ReadExpr以前缀方式输出表达式WriteExpr对式中的变量进行复制Assign3菜单65412复合表达式对变量赋值,即执行步骤3NY是否有变量 常数合并程序清单:头文件(MyExpression.h)#include#include#include#include#include#define MaxSize 100typedef char ElemType;typedef struct node ElemType data; struct node *lchild; struct node *rchild;BTNode;#define MAX_EXP_LEN 128 /* 表达式最大长度 */#define MAX_NOTATION_NUM 32 /* 一个表达式中的最大算符个数 */#define MAX_NOTATION_LEN 20 /* 表达式中一个算符的最大字串长度 */#define NULL 0typedef struct stack /* 表达式计算堆栈 */ double OpdStackMAX_NOTATION_NUM; /* 操作数堆栈 */ char OpStackMAX_NOTATION_NUM; /* 运算符堆栈 */ int OpdStackTop, /* 操作数堆栈顶指针 */ OpStackTop; /* 运算符堆栈顶指针 */ ExpressionCalculateStack;#define OPND D /* 操作数类型标志 */#define OPTR R /* 运算符类型标志 */#define CONTINUE_READ_NEXT_NOTATION C /* 表达式扫描标志,继续扫描 */#define STOP_READ_NEXT_NOTATION S /* 表达式扫描标志,暂停扫描 */* 部分子函数声明如下 (主要是表达式求值函数)*/double Expression(char *exp); /* 算术表达式求值 */double calculate (double opnd1,char op,double opnd2 ); /* 操作数四则运算 */void push( char , char, double , ExpressionCalculateStack *); /* 入栈 */double pop ( char , ExpressionCalculateStack *); /* 出栈 */void GetNextNotation ( char *notation,char *exp); /* 读下一个运算符或操作数 */char GetTypeOfNotation( char *notation ); /* 判定是运算符或是操作数 */int CompareOpPrior(char op2, char op1); /* 运算符优先级别比较 */源代码文件(MyExpression.c)#includeMyExpression.h#includestdlib.hextern double Expression(char *oldexp) ;extern int CompareOpPrior(char op2, char op1);extern char GetTypeOfNotation( char *notation ) ;extern void GetNextNotation (char *notation,char *exp);extern double calculate(double opnd1,char op,double opnd2 );extern double pop(char type,ExpressionCalculateStack *s);extern void push(char type, char op,double opnd,ExpressionCalculateStack *s);BTNode *ReadExpr(char s,int i,int j) BTNode *p; int k,plus=0,posi; if(i=j) p=(BTNode *)malloc(sizeof(BTNode); p-data=si; p-lchild=NULL; p-rchild=NULL; return p; /以下是i!=j的情况if(i!=j) for(k=i;k=j;k+) if(sk=+|sk=-) plus+; posi=k; if(plus=0) for(k=i;kdata=sposi; p-lchild=ReadExpr(s,i,posi-1); p-rchild=ReadExpr(s,posi+1,j); return p;/ void WriteExpr(BTNode *b) /把输入的表达式转换为相应的二叉树,并以前缀表达式的形式输出if(b!=NULL) printf(%c,b-data);if(b-lchild!=NULL|b-rchild!=NULL) printf(); WriteExpr(b-lchild ); if(b-rchild!=NULL) printf(,); WriteExpr(b-rchild); printf();char Seek(char s,int k)/判断是否有字母输入 char a1=0; int i; for(i=0;i=A&si=a&si=z) return a0=1;void Assign(char s,char i,char j) for(int p=0;p=strlen(s)-1;p+) if(sp=i) sp=j;void CompoundExpr(char E1,char E2,char p)/复合表达式char NewEMaxSize,q1; int k=0,i; BTNode *bt1,*bt2,*T; if(p=+|p=-)/复合函数为+或-是应怎样复合 for( i=0;istrlen(E1);i+)NewEi=E1i;NewEstrlen(E1)=p;for( k=0;k=0&sk-1=0&sk+1=9) /判断是否为数字 /*FX=sk-1*sk+1; sk-1=FX;*/ sk-1=(sk-1-48)*(sk+1-48)+48; for(int i=k;i=0&sk-1=0&sk+1=9) sk-1=(sk-1-48)/(sk+1-48)+48; for(int i=k;i=0&sk-1=0&sk+1=9) sk-1=(sk-1-48)+(sk+1-48)+48; for(int i=k;i=0&sk-1=0&sk+1=9) sk-1=(sk-1-48)-(sk+1-48)+48; for(int i=k;istrlen(s);i+) si=si+2; printf(常数合并后为:%s,s);void MergeConst(char s)/常数合并 int i,j,n; for(i=0;istrlen(s);i+) if(si=*|si=/) Conbination(s,i); for(j=0;jstrlen(s);j+) if(sj=+|sj=-) Conbination(s,j); void main()double fx=0; BTNode *b; int i=0,j=0; char sMaxSize, yesORno,value,getvalue,GetDigitl=NULL,p,E17,E23,e1,e2; printf( nn 表达式类型实现的使用说明:nn); printf( 表达式暂时还不能进行括号操作,请不要输入括号,nn); printf( 数字的输入只能是一位数(0-9),字母的输入a-z或A-Znn); printf( 表达式输入时请按以下形式输入:A-S+Dnn); printf(*nn); printf( 1.输入表达式 2.输出表达式nn); printf( 3.对变量赋值 4.对表达式求值nn); printf( 5.复合表达式 6.常数合并nn); printf( 7.返回nn); printf(*nn); printf(请输入选择(1-7)); while(GetDigitl=getchar()!=7) switch(GetDigitl) case 1: printf(nn请以中缀表达式形式输入表达式,例如a+b*c/dnn); printf(你的输入);getchar(); gets(s); /以中缀表达式形式输入表达式 printf(n); printf(你输入的表达式为:%sn,s); b=ReadExpr(s,0,strlen(s)-1);printf(n请输入选择(1-7)n); break; case 2: printf(n对应的二叉树:);WriteExpr(b);printf(nn);printf(n请输入选择(1-7)n); break; case 3: while(yesORno=Seek(s,strlen(s)-1)=1)printf(表示式中有变量!n);getchar(); printf(需要赋值的变量:); value=getchar(); getchar(); printf(变量值:); getvalue=getchar(); Assign(s,value,getvalue); b=ReadExpr(s,0,strlen(s)-1); printf(n对应的二叉树:); WriteExpr(b);printf(n请输入选择(1-7)n); break; case 4: yesORno=Seek(s,strlen(s)-1); if(yesORno=1) printf(表达式中有未知变量,请选择3进行变量赋值n); else fx=Expression(s); /* 表达式求值 */ printf(n表达式的运算结果为: %f n,fx); printf(n请输入选择(1-7)n); break; case 5: printf(请从(+、-、*、/)中选择一个作为复合符号n);printf(你的选择是:);getchar();p=getchar();printf(n);printf(请输入要复合的第一个表达式:);getchar();gets(E1);printf(n);printf(请输入要复合的第二个表达式:);gets(E2);printf(n);CompoundExpr(E1,E2,p); printf(n请输入选择(1-7)n);break; case 6: MergeConst(s); printf(n请输入选择(1-7)n); break; /一下是表达式求值函数#includeMyExpression.hdouble Expression(char *oldexp) /表达式计算函数,输入的是表达式字符串 char notationMAX_NOTATION_LEN, / 存放当前符号扫描读入的符号 op1,op2, expMAX_EXP_LEN; / 存放当前操作表达式 char flag=CONTINUE_READ_NEXT_NOTATION; /判别是否继续扫描下去 int prior; /存放算符优先级别比较结果: op2op1 : 1 /op2=op1 : 0 double opnd1,opnd2; / 存放当前用于计算的2个操作数 ExpressionCalculateStack s; /定义堆栈s s.OpdStackTop=s.OpStackTop=0; strcpy(exp,oldexp); /把原表达式复制给当前操作表达式 strcat(exp,#); /把#接到exp后面,原exp最后面的0被取消 push(OPTR,#,0.0,&s); / 初始化表达式计算堆栈 while(1) if( flag=CONTINUE_READ_NEXT_NOTATION ) GetNextNotation (notation,exp); else /* 有运算结果进操作数栈后 */ flag=CONTINUE_READ_NEXT_NOTATION; if ( GetTypeOfNotation( notation )=OPND ) opnd2 = atof(notation); push(OPND,NULL,opnd2,&s); /操作数处理 else / 运算符处理 op2 = notation 0; op1 = (char) pop(OPTR,&s); / 运算符出栈 prior = CompareOpPrior(op2,op1); if ( prior 0 ) /op2 0 ) /op2 op2 opnd2 = pop(OPND,&s) ; opnd1 = pop(OPND,&s); opnd2 = calculate(opnd1,op1,opnd2 ); push( OPND, NULL,opnd2,&s); flag=STOP_READ_NEXT_NOTATION; /暂停读入下一个表达式符号 /使当前运算符与栈顶运算符再作一次比较 if(prior=0) /op2 = op1 的情况处理 if( op2=#)return pop(OPND,&s) ;/结束运算,将运算结果从堆栈中弹出 void push(char type, char op,double opnd,ExpressionCalculateStack *s) if(type=OPND) s-OpdStacks-OpdStackTop+= opnd; else s-OpStacks-OpStackTop+ = op;double pop(char type,ExpressionCalculateStack *s) if(type=OPND) / 是操作数栈 return s-OpdStack-s-OpdStackTop; else / 是运算符栈 return (double) (s-OpStack-s-OpStackTop);double calculate(double opnd1,char op,double opnd2 ) switch(op) case +: return opnd1+opnd2; case -: return opnd1-opnd2; case *: return opnd1*opnd2; case /: if( opnd2!=0.0) return opnd1/opnd2; else return 0.0; return 0.0;void GetNextNotation (char *notation,char *exp) / 读入下一个完整的符号:操作数或运算符 / 把一个完整的操作数或运算符保存到notation static int i=0; / 变量i为表达式扫描的当前位置,注意其类型 int j; char type,lasttype = GetTypeOfNotation( exp+i ); for( j=0; expi!=0 ; j+,i+ ) if( expi= )continue; notationj=expi; type=GetTypeOfNotation( notation+j ); if( type=OPTR & lasttype=OPTR ) i+, j+; break; /第一次读到的就是/运算符 if( type=OPTR & lasttype=OPND ) break; /由读到的不是运算符转为读到的是运算符 lasttype=type; notationj=NULL; if( notation0=#) i=0; /表达式扫描完毕 char GetTypeOfNotation( char *notation ) /判断一个字符是不是运算符 char opstr=+-*/()#; /运算符集 int i; if( notation0=0 ) return NULL; for (i=0; opstri!=0;i+) if( notation0=opstri) return OPTR; /R 即是运算符 return OPND; / D 即是操作数或小数点或其它如空格等 int CompareOpPrior(char op2, char op1) /2个先后出现的运算符优先级别比较:按P53表3.1/定 char opstr=+-*/()#; int i,j; int priortable77= / + - * / ( ) # 1, 1, -1, -1, -1, 1, 1, 1, 1, -1, -1, -1, 1, 1, 1, 1, 1, 1, -1, 1, 1, 1, 1, 1, 1, -1, 1, 1, -1, -1, -1, -1, -1, 0, I, 1, 1, 1, 1, I, 1, 1, -1, -1, -1, -1, -1, I, 0, ; for( i=0; opstri!=0; i+ ) if( op1=opstri ) break; for( j=0; opstrj!=0; j+ ) if( op2=opstrj ) break; return priortableij;测试分析与用户使用步骤:出初始界面如下数据测试,测试结果如下:选择操作1,操作结果如下,输入你想呀输入的表达式:输入表达式后,继续选择你要执行的操作选择2操作,此操作是将以中缀形式输入的表达式,构造成一棵树,然后以二叉树的先序遍历的形式输入其结果,其结果如下:执行完操作2后,继续选择你要的操作选择3操作是将表达式中的变量进行赋值,直到表达式中的所有变量都赋上确切的值位置为止,并以所对应的二叉树的先序遍历的形式输出其结果,其执行结果如下:执行完操作3后,即可执行4的操作,对表达式求值。若表达式中有变量,没有经过执行操作3而是直接执行操作4的话,程序会提醒用户先去执行操作3后,
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 2025企业融资租赁合同样本
- 高数上册考试题及答案
- 高级翻译自考试题及答案
- 钢结构形考试题及答案
- 妇幼健康考试题及答案解析
- 2025年家庭成员间共同购房合同
- 法律类考试题卷子及答案
- 短语分类考试题型及答案
- 中国褐煤蜡项目经营分析报告
- 电影摄影考试题目及答案
- 2025年武汉车谷体育场馆运营投资发展有限公司招聘3人笔试题库历年考点版附带答案详解
- 中医药政策知识培训课件
- 物业维修安全培训课件
- 2025年国企中层干部竞聘笔试题+答案
- 胎盘早剥处理课件
- 城市亮化工程项目监理规划与实施方案研究
- 2025江西新余市北诚建设投资有限公司招聘合同制工作人员2人笔试参考题库附答案解析
- 2025年6月25日生效的欧盟REACH法规250项SVHC高度关注物质清单
- 云南省2025云南楚雄州南华县农业农村局紧缺人才公开招聘(1人)笔试历年参考题库附带答案详解
- 2025年教师招聘之《幼儿教师招聘》题库高频难、易错点100题模拟试题及参考答案详解(考试直接用)
- 电池厂生产安全管理制度
评论
0/150
提交评论