数据结构C语言表达式求值(带详细注释)_第1页
数据结构C语言表达式求值(带详细注释)_第2页
数据结构C语言表达式求值(带详细注释)_第3页
数据结构C语言表达式求值(带详细注释)_第4页
数据结构C语言表达式求值(带详细注释)_第5页
已阅读5页,还剩15页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

/*表达式求值,输入一个表达式,如1+2*3#,程序可计算出结果为7支持以下符号:+-*/()^.可以计算整数、小数其中^表示次方,2^5表示2的5次方*//*头文件*/#include<stdio.h>#include<malloc.h>#include<string.h>#include<math.h>#include<stdlib.h>/*宏定义*/#defineINIT_STACK_SIZE100#defineSET_NUM8#defineN100/*字符优先级表*/unsignedcharprior[SET_NUM][SET_NUM]={/*'+''-''*''/''('')''#''^'*//*'+'*/'>','>','<','<','<','>','>','<',/*'-'*/'>','>','<','<','<','>','>','<',/*'*'*/'>','>','>','>','<','>','>','<',/*'/'*/'>','>','>','>','<','>','>','<',/*'('*/'<','<','<','<','<','=','','<',/*')'*/'>','>','>','>','','>','>','>',/*'#'*/'<','<','<','<','<','','=','<',/*'^'*/'>','>','>','>','<','>','>','>'};unsignedcharpriorSet[SET_NUM]={'+','-','*','/','(',')','#','^'};/*结构体定义,这是用来存放字符的栈*/typedefstruct{char*base;char*top;intstacksize;}SqStackC;/*结构体定义,这是用来存放数字的栈*/typedefstruct{double*base;double*top;intstacksize;}SqStackN;voidinitStackN(SqStackN&);voidinitStackC(SqStackC&);voidpushN(SqStackN&,double);voidpushC(SqStackN&,double);voidpopN(SqStackN&,double&);voidpopC(SqStackN&,double&);doublecalculate(double,char,double);intfindInSet(char);charcompare(char,char);voidgetSolution();/*主函数*/voidmain(){getSolution();}/*初始化数字栈*/voidinitStackN(SqStackN&S){S.base=(double*)malloc(INIT_STACK_SIZE*sizeof(double));S.top=S.base;S.stacksize=INIT_STACK_SIZE;}/*初始化字符栈*/voidinitStackC(SqStackC&S){S.base=(char*)malloc(INIT_STACK_SIZE*sizeof(char));S.top=S.base;S.stacksize=INIT_STACK_SIZE;}/*向数字栈中存放数字*/voidpushN(SqStackN&S,doublex){if(S.top-S.base>=S.stacksize)return;*(S.top++)=x;}/*向字符栈中存放字符*/voidpushC(SqStackC&S,charx){if(S.top-S.base>=S.stacksize)return;*(S.top++)=x;}/*从数字栈中取出数字*/voidpopN(SqStackN&S,double&x){if(S.top==S.base)return;x=*(--S.top);}/*从字符栈中取出字符*/voidpopC(SqStackC&S,char&x){if(S.top==S.base)return;x=*(--S.top);}/*这个函数返回aoperationb的值。假如operation为'+',则返回a+b的值*/doublecalculate(doublea,charoperation,doubleb){/*判断operation,返回对应的计算结果*/switch(operation){case'+':returna+b;case'-':returnb-a;case'*':returna*b;case'/':returnb/a;case'^':returnpow(b,a);default:return0;}}/*查找字符c在priorSet中的什么位置*//*priorSet是所支持的所有字符的集合*/intfindInSet(charc){inti;for(i=0;i<SET_NUM;i++){if(priorSet[i]==c)returni;}return-1;}/*比较optrtop和c的优先关系*/charcompare(charoptrtop,charc){inti,j;/*从priorSet中取出optrtop和c的位置*/i=findInSet(optrtop);j=findInSet(c);/*如果返回值中有-1表示这个符号不支持,结束程序*/if(i==-1||j==-1){printf("不支持的符号类型\n");exit(0);}/*否则返回二者优先级关系*/elsereturnprior[i][j];}/*取得计算结果*//*解释下代码处理数字的原理:假如输入为10+2.2*3-2#循环会从这个字符串第一个位置开始,也就是1如果当前字符是个数字,则要把这个数字从字符串里取出来这个时候涉及两个问题,一是数字可能是大于10的整数,二是可能有小数。处理方法是这样的:当遇到数字,先将数字保存在n上,判断下一个字符是数字还是运算符如果是数字,则将n乘以10加上这个数字,这样即可以处理大于10的数字。如果遇到运算符,就退出循环去处理运算符如果遇到的是小数点,表示这个数字是小数。小数不会立刻计算出来,而是先将小数点忽视掉,将整数计算出。比如2.2会先计算成22变量j和begin在遇到小数点时候用来计算小数点后面有几个数字,即这个小数有多少位。当begin=1时候,表示现在要计算小数点后的数字位数。这时候j会在每次循环加1这样计算后,n=22,j=1;此时算n=n/pow(10,j);即将n缩小10的j次方。就变成了2.2*/voidgetSolution(){/*operation是当前的运算符*/charoperation;/*temp是输入的字符串*/chartemp[N];/*i是循环变量,j和begin用来控制什么时候计算出小数*/inti=0,j=-1,begin=0;/*sum是每次的计算结果,a和b是从数字栈中取出的数字,n用来存放从字符串中取出的数*/doublesum,a,b,n;/*定义堆栈并初始化*/SqStackCOPTR;SqStackNOPND;initStackC(OPTR);initStackN(OPND);/*向字符栈中压入#,标志开始*/pushC(OPTR,'#');/*获得输入*/printf("请输入一个表达式,输入#结束\n");gets(temp);/*开始计算,当遇到#表示结束*/while(temp[i]!='#'||*(OPTR.top-1)!='#'){/*如果当前字符是个数字字符*/if(temp[i]>='0'&&temp[i]<='9'){/*重置n为0*/n=0;/*当当前字符是数字或者小数点*/while(temp[i]>='0'&&temp[i]<='9'||temp[i]=='.'){/*如果是小数点,begin=1,表示要从字符串中取出一个小数*/if(temp[i]=='.')begin=1;/*否则作为整数取出*/else n=n*10+temp[i]-'0';/*如果begin不为0,表示遇到了一个小数点,表示需要合并为小数*//*j表示这个小数的小数点后面有几位*/if(begin!=0)j++;/*循环变量加1*/i++;}/*如果j不为-1,则表示这是个小数,n是整数结果,除以pow(10,j)则变成了小数*/if(j!=-1)n=n/pow(10,j);/*将数字压入栈*/pushN(OPND,n);/*重置j和begin的值*/j=-1;begin=0;}else{/*如果当前字符不是数字,比较栈顶字符和当前字符优先级,根据优先级处理*/switch(compare(*(OPTR.top-1),temp[i])){/*如果栈顶字符优先级大,则可以取出计算*/case'>':/*取出字符栈顶运算符,和数字栈顶的两个数字*/popC(OPTR,operation);popN(OPND,a);popN(OPND,b);/*计算结果*/sum=calculate(a,operation,b);/*结果入栈*/pushN(OPND,

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论