算术表达式.docx
- 文档编号:9476150
- 上传时间:2023-05-19
- 格式:DOCX
- 页数:34
- 大小:146.38KB
算术表达式.docx
《算术表达式.docx》由会员分享,可在线阅读,更多相关《算术表达式.docx(34页珍藏版)》请在冰点文库上搜索。
算术表达式
目录
一、系统开发的背景1
二、程序分析与设计1
(一)程序任务要求1
(二)程序模块结构设计1
三、系统的设计与实现2
(一)输入语法正确的前缀表达式并构造表达式E:
ReadExpre(E)2
(二)用带括弧的中缀表达式输出表达式E:
WriteExpre(E)4
(三)实现对变量V的赋值(V=c):
Assign(V,c)4
(四)、对算术表达式E求值:
Value(E)5
(五)、构造一个新的复合表达式(E1)P(E2):
CompoundExpr(P,E1,E2)5
四、系统测试6
(一)测试voidmain()函数6
(二)、测试其他调用函数(ReadExpre(E)、WriteExpre(E)、Assign(V,c)、Value(E)、CompoundExpr(P,E1,E2)等)6
五、总结9
六、附件(全部代码)9
算术表达式与二叉树
一、系统开发的背景
一个表达式和一棵二叉树之间,存在着自然的对应关系,为了实现基于二叉树表示的算术表达式的操作,因此编写这个程序。
二、程序分析与设计
(一)程序任务要求
假设算术表达式Expression内可以含有变量(a~z)、常量(0~9)和二元运算符(+,-,*,/,^(乘幂))。
实现以下操作:
1)ReadExpre(E)—以字符序列的形式输入语法正确的前缀表达式并构造表达式E。
2)WriteExpre(E)—用带括弧的中缀表达式输出表达式E。
3)Assign(V,c)—实现对变量V的赋值(V=c),变量的初值为0。
4)Value(E)—对算术表达式E求值。
5)CompoundExpr(P,E1,E2)--构造一个新的复合表达式(E1)P(E2)
(二)程序模块结构设计
通过对程序任务功能的分析,算术表达式与二叉树程序功能如图
(1)所示。
图1算术表达式与二叉树程序功能图
通过上图的功能分析,把整个系统划分为4个模块:
1、以字符序列的形式输入语法正确的前缀表达式并构造表达式E,该模块主要实现:
,借助函数ReadExpre(E)来实现;
2、用带括弧的中缀表达式输出表达式E,该模块主要实现:
,借助函数WriteExpre(E)来实现;
3、实现对变量V的赋值(V=c),该模块主要实现:
借助函数Assign(V,c)来实现;
4、对算术表达式E求值,该模块主要实现:
,借助函数Value(E)来实现;
5、构造一个新的复合表达式(E1)P(E2),该模块主要实现:
,借助函数CompoundExpr(P,E1,E2)来实现
三、系统的设计与实现
(一)输入语法正确的前缀表达式并构造表达式E:
ReadExpre(E)
该模块的具体代码如下所示。
/*以正确的前缀表示式并构造表达式E*/
StatusReadExpr(BiTree*E,char*exprstring)
{SqStackS;//定义顺序栈S
inti,len;/*len为表达式的长度*/
BiTreep,q;
(*E)=(BiTree)malloc(sizeof(BiTNode));/*申请二叉树的根结点的空间*/
(*E)->lchild=NULL;
(*E)->rchild=NULL;
len=strlen(exprstring);/*len赋值为表达式的长度*/
if(len==1)/*表达式长度为1时,二叉树只有根结点*/
judge_value(E,exprstring,0);/*将exprstring[0]存入二叉树的结点中*/
else
{judge_value(E,exprstring,0);/*将exprstring[0]存入二叉树的结点中*/
InitStack(&S);/*初始化栈*/
q=(*E);
Push(&S,q);/*入栈*/
Push(&S,q);/*入栈,根结点入栈两次是为判断先序输入的表达式是不是正确的表达式*/
for(i=1;i StackEmpty(S);i++)// {p=(BiTree)malloc(sizeof(BiTNode)); judge_value(&p,exprstring,i);/*将exprstring[i]存入二叉树的结点中*/ p->lchild=NULL; p->rchild=NULL; if(exprstring[i]=='+'||exprstring[i]=='-'||exprstring[i]=='*'||exprstring[i]=='/'||exprstring[i]=='^') {/*为运算符,运算符入栈,左孩子不空,向左孩子走,否则,如果右孩子不空,向右孩子走*/ if(! q->lchild) {q->lchild=p;Push(&S,p);q=p;} else {q->rchild=p;Push(&S,p);q=p;}} else/*不是运算符,运算符出栈*/ {if(! q->lchild) {q->lchild=p;Pop(&S,&q);} else {q->rchild=p;Pop(&S,&q);} } } if(StackEmpty(S)&&i>=len) returnOK;/*栈空且i>=len,说明输入的表达式是正确的*/ else/*输入的表达式是错误的*/ {printf("\n\t输入的表达式有误! "); returnERROR; } } } (二)用带括弧的中缀表达式输出表达式E: WriteExpre(E) /*用带括弧的中缀表达式输出表达式*/ voidWriteExpr(BiTreeE) {if(E)/*树不为空*/ {/*先递归左子树*/ if(E->lchild&&E->lchild->data.tag==CHAR)/*E的左孩子不为空,且左孩子为字符*/ {if(Pri_Compare(E->data.c,E->lchild->data.c))/*E->data.c比E->lchild->data.c优先*/ {printf("("); WriteExpr(E->lchild); printf(")");}/*带括弧输出左子树*/ else WriteExpr(E->lchild);/*否则,不带括弧输出左子树*/ } else WriteExpr(E->lchild);/*否则,输出左子树*/ /*访问输出根结点的值*/ if(E->data.tag==INT) {printf("%d",E->data.num);} else printf("%c",E->data.c); /*后递归右子树*/ if(E->rchild&&E->rchild->data.tag==CHAR)/*E的右孩子不为空,且右孩子为字符*/ {if(Pri_Compare(E->data.c,E->rchild->data.c))/*E->data.c比E->rchild->data.c优先*/ {printf("("); WriteExpr(E->rchild);printf(")");}/*带括弧输出右子树*/ elseWriteExpr(E->rchild);/*否则,不带括弧输出右子树*/ } elseWriteExpr(E->rchild);/*否则,输出右子树*/ } } (三)实现对变量V的赋值(V=c): Assign(V,c) /*实现对表达式中的所有变量V的赋值(V=c),参数flag为表示是否赋值过的标志*/ voidAssign(BiTree*E,charV,intc,int*flag) {if(*E) {if((*E)->data.tag==CHAR&&(*E)->data.c==V)/*如果找到要赋值的变量,赋值*/ {(*E)->data.tag=INT;(*E)->data.num=c;*flag=1;} Assign(&((*E)->lchild),V,c,flag);/*递归左子树*/ Assign(&((*E)->rchild),V,c,flag);/*递归左子树*/ } } /*指数运算函数,底数为x,指数为exp*/ longpower(intx,intexp) { longresult; inti; for(i=1,result=1;i<=exp;i++) result*=x; returnresult;} (四)、对算术表达式E求值: Value(E) /*对算术表达式求值*/ longValue(BiTreeE) {if(E)/*树不为空*/ {if(! E->lchild&&! E->rchild&&E->data.tag==INT) return(E->data.num); /*结点的左孩子和右孩子为空,为叶子结点,返回结点的值*/ returnOperate(Value(E->lchild),E->data.c,Value(E->rchild)); /*运算求值,后根遍历的次序对表达式求值,其中参数递归调用了Value()函数求左子树的值和右子树的值*/ } } (五)、构造一个新的复合表达式(E1)P(E2): CompoundExpr(P,E1,E2) /*构造一个新的复合表达式*/ voidCompoundExpr(charP,BiTree*E1,BiTreeE2) {BiTreeE; E=(BiTree)malloc(sizeof(BiTNode));/*申请一个结点存放运算符P*/ E->data.tag=CHAR; E->data.c=P;/*申请到的结点值为P*/ E->lchild=(*E1);/*结点的左孩子为E1*/ E->rchild=E2;/*结点的右孩子为E2*/ (*E1)=E;/*(*E1)为根结点*/ printf("\n\t表达式E复合成功! 其表达式变为: \n"); WriteExpr(E);/*输出复合好的表达式*/ } 四、系统测试 (一)测试voidmain()函数 测试该函数时可以运行程序,来测试主函数是否运行正常,如图2所示界面: 图2程序主界面图 (二)、测试其他调用函数(ReadExpre(E)、WriteExpre(E)、Assign(V,c)、Value(E)、CompoundExpr(P,E1,E2)等) 测试时全面运行程序,根据测试数据进行测试,如运行无误,则证明程序中函数无误。 如下图3-图9所示。 图3 图4 图5 图6 图7 图8 图9 五、总结 系统完成了基于二叉树表示的算术表达式的操作功能。 系统在运算方面有不足,不能进行三角函数等方面的计算。 程序在运行中界面不够友好等问题。 我的收获是在数据结构中可以将输入输出的语句改为C语言的输入输出语句,写程序就要多动手,在一些瓶颈上可以另辟蹊径,用其他方式编写出来后更改为自己需要的方式。 在整体上就要有一个好的构思,在数据结构学习上要有全面的观念来编写程序。 经过这两周的编译,我感觉对二叉树的掌握更牢固了,整体上我都是用的二叉树处理实现各个功能。 我感觉对于一个题目中处理函数尽量让他可以多功能中使用,这样编程效率会高一些。 六、附件(全部代码) #include #include #include #include #defineTRUE1 #defineFALSE0 #defineOK1 #defineERROR0 #defineOVERFLOW0 typedefintStatus;/*二叉树结点类型*/ typedefenum{INT,CHAR}ElemTag;/*INT为整型数据num,CHAR为字符型数据c*/ typedefstructTElemType {ElemTagtag;/*{INT,CHAR}指示是整型还是字符型*/ union {intnum;/*tag=INT时,为整型*/ charc;/*tag=CHAR时,为字符型*/}; }TElemType; /*二叉树的二叉链表存储表示*/ typedefstructBiTNode {TElemTypedata; structBiTNode*lchild,*rchild;/*左右孩子指针*/ }BiTNode,*BiTree; typedefBiTreeSElemType;/*栈SqStack的元素*/ typedefcharSElemType1;/*栈SqStack1的元素*/ #defineSTACK_INIT_SIZE10/*存储空间初始分配量*/ #defineSTACKINCREMENT2/*存储空间分配增量*/ /*两个顺序栈*/ typedefstructSqStack {SElemType*base;/*在栈构造之前和销毁之后,base的值为NULL*/ SElemType*top;/*栈顶指针*/ intstacksize;/*当前已分配的存储空间,以元素为单位*/ }SqStack;/*顺序栈*/ typedefstructSqStack1 {SElemType1*base;/*在栈构造之前和销毁之后,base的值为NULL*/ SElemType1*top;/*栈顶指针*/ intstacksize;/*当前已分配的存储空间,以元素为单位*/ }SqStack1;/*顺序栈*/ /*顺序栈的基本操作*/ StatusInitStack(SqStack*S) {/*构造一个空栈S*/ (*S).base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType)); if(! (*S).base) exit(OVERFLOW);/*存储分配失败*/ (*S).top=(*S).base; (*S).stacksize=STACK_INIT_SIZE; returnOK;} StatusStackEmpty(SqStackS) {/*若栈S为空栈,则返回TRUE,否则返回FALSE*/ if(S.top==S.base) returnTRUE; else returnFALSE;} StatusPush(SqStack*S,SElemTypee) {/*插入元素e为新的栈顶元素*/ if((*S).top-(*S).base>=(*S).stacksize)/*栈满,追加存储空间*/ { (*S).base=(SElemType*)realloc((*S).base,((*S).stacksize+STACKINCREMENT)*sizeof(SElemType)); if(! (*S).base) exit(OVERFLOW);/*存储分配失败*/ (*S).top=(*S).base+(*S).stacksize; (*S).stacksize+=STACKINCREMENT;} *((*S).top)++=e; returnOK;} StatusPop(SqStack*S,SElemType*e) {/*若栈不空,则删除S的栈顶元素,用e返回其值,并返回OK;否则返回ERROR*/ if((*S).top==(*S).base) returnERROR; *e=*--(*S).top; returnOK;} StatusGetTop(SqStackS,SElemType*e) {/*若栈不空,则用e返回S的栈顶元素,并返回OK;否则返回ERROR*/ if(S.top>S.base) {*e=*(S.top-1); returnOK;} else returnERROR;} /*顺序栈的基本操作*/ StatusInitStack1(SqStack1*S) {/*构造一个空栈S*/ (*S).base=(SElemType1*)malloc(STACK_INIT_SIZE*sizeof(SElemType1)); if(! (*S).base) exit(OVERFLOW);/*存储分配失败*/ (*S).top=(*S).base; (*S).stacksize=STACK_INIT_SIZE; returnOK;} StatusStackEmpty1(SqStack1S) {/*若栈S为空栈,则返回TRUE,否则返回FALSE*/ if(S.top==S.base)returnTRUE; elsereturnFALSE;} StatusPush1(SqStack1*S,SElemType1e) {/*插入元素e为新的栈顶元素*/ if((*S).top-(*S).base>=(*S).stacksize)/*栈满,追加存储空间*/ { (*S).base=(SElemType1*)realloc((*S).base,((*S).stacksize+STACKINCREMENT)*sizeof(SElemType1)); if(! (*S).base) exit(OVERFLOW);/*存储分配失败*/ (*S).top=(*S).base+(*S).stacksize; (*S).stacksize+=STACKINCREMENT;} *((*S).top)++=e; returnOK;} StatusPop1(SqStack1*S,SElemType1*e) {/*若栈不空,则删除S的栈顶元素,用e返回其值,并返回OK;否则返回ERROR*/ if((*S).top==(*S).base) returnERROR; *e=*--(*S).top; returnOK;} StatusGetTop1(SqStack1S,SElemType1*e) {/*若栈不空,则用e返回S的栈顶元素,并返回OK;否则返回ERROR*/ if(S.top>S.base) {*e=*(S.top-1); returnOK;} else returnERROR;} #include #include /*全局变量*/ intsave_number[51];/*在按原表达式输入形式中,输入的常量保存到数组save_number中,常量最多为50个,0单元不用*/ charExpr_String[50]; StatusInput_Expr(char*string,intflag) {if(flag==0) printf("\n\n\t请输入正确的前缀表示式: "); else printf("\n\t请以表达式的原书写形式输入正确表示式: "); flushall();/*清理缓冲区*/ gets(string);/*从键盘输入一串字符串作为表达式*/ if(strlen(string)==1)/*输入的表达式字符串长度为1*/ if(string[0]=='+'||string[0]=='-'||string[0]=='*'||string[0]=='/'||string[0]=='^')/*输入的表达式只有一个运算符*/ {printf("\n\t表达式只有一个字符,为运算符,错误! ");returnERROR;} elseif((string[0]>='0'&&string[0]<'9')||(string[0]>='a'&&string[0]<='z')||(string[0]>='A'&&string[0]<='Z')) /*输入的表达式只有一个数字或字符*/ {printf("\n\t表达式只有一个字符! ");returnOK;} else{printf("\n\t输入的字符不是运算符也不是变量常量,错误! ");returnERROR;} returnOK;} /*判断字符string[i],如果是'0'-'9'常量之间,二叉树结点存为整型;否则,存为字符型*/ voidjudge_value(BiTree*E,char*string,inti) {if(string[i]>='0'&&string[i]<='9')/*为常量*/ {(*E)->data.tag=INT;(*E)->data.num=string[i]-48;} elseif(string[i]>=1&&string[i]<=20)/*为常量,常量存于数组save_number中*/ {(*E)->data.tag=INT;(*E)->data.num=save_number[string[i]];} else/*为变量*/ {(*E)->data.tag=CHAR;(*E)->data.c=string[i];}} /*以正确的前缀表示式并构造表达式E*/ StatusReadExpr(BiTree*E,char*exprstring) {SqStackS;//定义顺序栈S inti,len;/*len为表达式的长度*/ BiTreep,q; (*E)=(BiTree)malloc(sizeof(BiTNode));/*申请二叉树的根结点的空间*/ (*E)->lchild=NULL; (*E)->rchild=NULL; len=strlen(exprstring);/*len赋值为表达式的长度*/ if(len==1)/*表达式长度为1时,二叉树
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 算术 表达式
![提示](https://static.bingdoc.com/images/bang_tan.gif)