完整版数学表达式计算c语言实现.docx
- 文档编号:14511545
- 上传时间:2023-06-24
- 格式:DOCX
- 页数:21
- 大小:252.09KB
完整版数学表达式计算c语言实现.docx
《完整版数学表达式计算c语言实现.docx》由会员分享,可在线阅读,更多相关《完整版数学表达式计算c语言实现.docx(21页珍藏版)》请在冰点文库上搜索。
完整版数学表达式计算c语言实现
一、设计思想
计算算术表达式可以用两种方法实现:
1.中缀转后缀算法
此算法分两步实现:
先将算术表达式转换为后缀表达式,然后对后缀表达式进行计算.具体实现方法如下:
(1)中缀转后缀
需要建一个操作符栈op和一个字符数组exp,op栈存放操作符,字符数组用来存放转换以后的后缀表达式。
首先,得到用户输入的中缀表达式,将其存入str数组中。
对str数组逐个扫描,如果是数字或小数点,则直接存入exp数组中,当扫描完数值后,在后面加一个#作为分隔符。
如果是操作符,并且栈为空直接入栈,如果栈不为空,与栈顶操作符比较优先等级,若比栈顶优先级高,入栈;如果比栈顶优先级低或相等,出栈将其操作符存到exp数组中,直到栈顶元素优先等级低于扫描的操作符,则此操作符入栈;如果是左括号,直接入栈,如果是右括号,出栈存入exp数组,直到遇到左括号,左括号丢掉。
然后继续扫描下一个字符,直到遇到str中的结束符号\0,扫描结束。
结束后看op栈是否为空,若不为空,继续出栈存入exp数组中,直到栈为空.到此在exp数组最后加结束字符\0。
我们就得到了后缀表达式。
(2)后缀表达式计算
此时需要一个数值栈od来存放数值。
对exp数组进行逐个扫描,当遇到数字或小数点时,截取数值子串将其转换成double类型的小数,存入od栈中。
当遇到操作符,从栈中取出两个数,进行计算后再放入栈中。
继续扫描,知道扫描结束,此时值栈中的数值就是计算的结果,取出返回计算结果。
2。
两个栈实现算法
此算法需要两个栈,一个值栈od,一个操作符栈op。
将用户输入的数学表达式存入str数组中,对其数组进行逐个扫描。
当遇到数字或小数点,截取数值子串,将其转换成double类型的数值存入od栈中;当遇到左括号,直接入op栈;遇到右括号,op栈出栈,再从值栈od中取出两个数值,计算将其结果存入值栈中,一直进行此操作,直到操作符栈栈顶为左括号,将左括号丢掉。
如果遇到操作符,若op栈为空,直接入栈;若栈不为空,与栈顶元素比较优先等级,若比栈顶操作符优先等级高,直接入op栈,如果低于或等于栈顶优先等级,op栈出栈,再从值栈中取出两个数值,计算将其结果存入值栈中,一直进行此操作,直到栈顶优先等级低于扫描的操作符等级,将此操作符入op栈。
继续扫描直到遇到str中的结束字符\0,扫描结束。
此时看操作符栈是否为空,若不为空,出栈,再从值栈中取出两个数值进行计算,将其结果存入值栈,一直进行此操作,直到操作符栈为空。
此时把值栈中的数值取出,即为所得的最终计算结果。
二、算法流程图
第一种算法:
中缀转后缀算法
其主函数流程图为:
图1主函数算法流程图
中缀转后缀算法流程图如下:
图2中缀转后缀算法流程图
计算后缀表达式流程图如下:
图3后缀表达式计算流程图
第二种算法:
两个栈算法
其主函数流程图为:
图4主函数算法流程图
直接计算数学表达式流程图如下:
图5直接计算表达式流程图
三、源代码
下面给出的是用中缀转后缀算法实现的程序的源代码:
#include
#include
#include〈math。
h>
#include h〉 #defineMAXSIZE100//定义宏,数组最大长度为100 //函数实现中缀转后缀,将存储数学表达式的数组str传参进来,exp存储后缀表达式 voidtrans(charstr[],charexp[]) { struct { chardata[MAXSIZE];//用来存放操作符 inttop;//数组下标 }op;//用结构体创建操作符栈 charch; inti=0,j=0,tempi=0; op.top=-1;//给操作符栈初始化,令下标为—1 while(ch! ='\0') { ch=str[i];//取str数组的第i个元素赋值给ch if((ch〉=’0'&&ch<=’9’)||ch=='.’)//对数值操作 { tempi=i;//若ch为数字或小数点,将其下标值赋给临时下标tempi //依次向后扫描str数组,若一直为数字,跳入while循环 while((ch〉='0’&&ch〈=’9')||ch=='.') { tempi++; exp[j]=ch;//将数字存入exp数组中 j++; ch=str[tempi];//取str数组中下标为tempi的元素赋给ch } exp[j]=’#’;j++;//用#做分隔符,将数值分隔开 i=tempi;//跳出循环,将此时的tempi赋给i,继续向后扫描 } //对操作符操作 elseif(ch==’+’||ch==’-’||ch=='*'||ch=='/’||ch=='%'||ch==’('||ch==’)') { intlevel(charop);//声明level函数 if(ch==’(’)//如果为(,直接进栈 { op.top++; op。 data[op。 top]=ch;//进栈操作 } elseif(ch==’)’) { //如果为),一直出栈直到遇到( while(level(op.data[op.top])! =—1)//若栈顶元素不为(,进入while循环 { exp[j]=op.data[op.top];//操作符出栈,存入exp数组中 op.top—-; j++; if(op。 top==-1)break;//如果栈为空,跳出循环 } op。 top—-;//左括号pop出来 } elseif(op.top==-1)//如果栈为空,直接进栈 { op。 top++; op。 data[op。 top]=ch;//进栈操作 } //如果所扫描的操作符优先等级比栈顶元素高,直接进栈 elseif(level(ch)>level(op。 data[op。 top])) { op.top++; op.data[op.top]=ch;//进栈操作 } else { //如果所扫描的操作符优先等级没有栈顶元素高, //一直出栈直到比栈顶元素优先级高 while(level(ch)〈=level(op.data[op.top])) { exp[j]=op.data[op.top];//出栈存入exp数组中 op.top——; j++; if(op.top==-1)break;//如果栈为空,跳出循环 } op.top++; op。 data[op.top]=ch;//比栈顶元素优先级高,入栈 } i++;//str下标加1,向后扫描 } } while(op。 top! =—1)//扫描结束后如果操作符栈不为空,出栈直至为空 { exp[j]=op。 data[op.top];//出栈存入exp数组中 op。 top—-; j++; } exp[j]=’\0’;//赋\0结束exp字符数组 } intlevel(charop)//判断操作符优先等级 { if(op=='+’||op=='—')//若为+、-,等级为1 return1; elseif(op==’*’||op==’/’||op==’%’) return2;//若为*、/、%,等级为2 elseif(op=='(’) return—1;//若为(,等级为-1 else return—3;//其他等级为-3; } doublecalvalue(doubleod1,doubleod2,chartempop)//计算 { switch(tempop){ case’+’: returnod1+od2;//计算加法 case'-': returnod1-od2;//计算减法 case'*': returnod1*od2;//计算乘法 case’/': returnod1/od2;//计算除法 case'%': returnfmod(od1,od2);//求余 } return0; } doublecalculate(charexp[])//计算后缀表达式 { struct//用结构体创建值栈 { doubledata[MAXSIZE];//存储数值 inttop; }od; doubled;//声明d变量存储数值 doubleod1,od2;//存储值栈依次pop出来的操作数 charch; chartempch[20];//声明临时数组存储子串 intj=0,t; intlength=strlen(exp);//计算exp数组的长度 od。 top=-1;//初始化值栈,令下标为-1 while(j { ch=exp[j];//提取exp中第j个元素 if(ch! ='+'&&ch! ='-'&&ch! =’*’&&ch! =’/’&&ch! ='%') { //如果为数字或小数点 d=0; t=0; while((ch>='0’&&ch<=’9')||ch=='。 ’) { tempch[t]=ch;t++;//依次存放到临时数组中 j++;ch=exp[j]; } tempch[t]=’\0’;//结束tempch数组 d=atof(tempch);//将子串转化成double类型的数 od.top++; od.data[od。 top]=d;//入值栈 } else//若为操作符,从值栈中pop出两个数计算 { od2=od.data[od.top];od。 top——;//先出栈的赋给od2 od1=od.data[od.top];//后出栈的赋给od1 od.data[od.top]=calvalue(od1,od2,ch);//计算出结果后再入栈 } j++; } returnod.data[od.top];//将结束后值栈中的数pop出来,即为计算结果 } main() { charstr[MAXSIZE],exps[MAXSIZE];//定义两个数组 printf("请输入算术表达式: \n”); gets(str);//从控制台输入算数表达式 printf(”表达式为: %s\n”,str); trans(str,exps);//调用trans函数,得到后缀表达式 printf(”后缀表达式: %s\n",exps); printf("结果为: %lf\n”,calculate(exps));//调用calculate函数,计算结果 } 下面给出的是用两个栈算法实现的程序的源代码: #include〈stdio。 h〉 #include〈string。 h〉 #include〈math.h〉 #include h> #defineMAXSIZE100//定义宏,数组最大长度为100 doublecalculate(charstr[]) { struct//用结构体创建操作符栈 { chardata[MAXSIZE];//用来存放操作符 inttop; }op; struct//用结构体创建值栈 { doubledata[MAXSIZE];//用来存放操作数 inttop; }od; charch; chartempch[20];//声明临时数组存储子串 intj=0,t; doubled; doubleod1,od2;//存储值栈依次pop出来的操作数 chartempop; intlength=strlen(str);//计算str数组的长度 op.top=-1;//初始化操作符栈,令下标为—1 od。 top=-1;//初始化值栈 while(j { ch=str[j]; if((ch〉=’0’&&ch〈='9')||ch==’.’)//若为数值或小数点 { d=0; t=0; while((ch>='0’&&ch<=’9')||ch=='.’)//截取子串 { tempch[t]=ch;t++;//赋值给临时数组 j++;ch=str[j]; } tempch[t]=’\0’; d=atof(tempch);//将子串转化成double类型的数 od。 top++; od.data[od。 top]=d;//入值栈 } //对操作符操作 elseif(ch=='+'||ch==’—’||ch==’*’||ch==’/’||ch=='%'||ch==’(’||ch==')’) { if(ch==’(’)//如果为(,直接进栈 { op.top++; op。 data[op。 top]=ch;//进栈操作 } elseif(ch==’)')//如果为),一直出栈直到遇到( { intlevel(charop);//声明level函数 while(level(op。 data[op。 top])! =-1)//若栈顶元素不为(,进入while循环 { //声明calvalue函数 doublecalvalue(doubleod1,doubleod2,chartempop); od2=od。 data[od.top];od.top-—; od1=od。 data[od。 top]; tempop=op.data[op。 top];op.top—-; od。 data[od。 top]=calvalue(od1,od2,tempop);//计算出结果后入值栈 if(op.top==—1)break;//如果操作符栈为空,跳出循环 } op。 top——;//左括号pop出来 } elseif(op。 top==—1)//如果栈为空,直接进栈 { op.top++; op.data[op。 top]=ch;//进栈操作 } //如果所扫描的操作符优先等级比栈顶元素高,直接进栈 elseif(level(ch)>level(op.data[op.top])) { op.top++; op.data[op.top]=ch;//进栈操作 } else { //如果所扫描的操作符优先等级没有栈顶元素高, //一直出栈直到比栈顶元素优先级高 while(level(ch)<=level(op。 data[op.top])) { od2=od.data[od.top];od。 top——; od1=od。 data[od。 top]; tempop=op.data[op.top];op。 top——; od。 data[od.top]=calvalue(od1,od2,tempop);//计算结果后入值栈 if(op。 top==—1)break;//如果栈为空,跳出循环 } op。 top++; op。 data[op。 top]=ch;//比栈顶元素优先级高,入操作符栈 } j++;//str下标加1,向后扫描 } } while(op.top! =—1)//扫描结束后如果操作符栈不为空,出栈直至为空 { od2=od.data[od.top];od.top——; od1=od。 data[od.top]; tempop=op。 data[op。 top];op.top-—; od。 data[od.top]=calvalue(od1,od2,tempop);//计算结果后入值栈 } returnod.data[od.top];//将结束后值栈中的数pop出来,即为计算结果 } intlevel(charop)//判断操作符优先等级 { if(op==’+’||op==’—')//若为+、—,等级为1 return1; elseif(op=='*'||op=='/’||op=='%’) return2;//若为*、/、%,等级为2 elseif(op=='(’) return—1;//若为(,等级为—1 else return-3;//其他等级为-3; } doublecalvalue(doubleod1,doubleod2,chartempop)//计算 { switch(tempop){ case’+': returnod1+od2;//计算加法 case'—’: returnod1-od2;//计算减法 case’*’: returnod1*od2;//计算乘法 case’/': returnod1/od2;//计算除法 case'%’: returnfmod(od1,od2);//求余 } return0; } voidmain() { charstr[MAXSIZE];//定义str数组存放数学表达式 printf(”输入算术表达式: \n”); gets(str);//从控制台输入算数表达式 printf(”结果是: %lf\n",calculate(str));//调用calculate函数,计算结果 } 四、运行结果 图6中缀转后缀算法运行结果 图7两个栈算法运行结果 五、遇到的问题及解决 编程的前期工作很重要,需要明确的理清思路,而编写运行的过程中更是会出现很多问题,有因粗心造成的拼写错误,有语法错误,也有逻辑错误。 在整个编程过程我主要遇到了如下几个大的问题,其内容与解决方法如下所列: ●将字符表示的数字转化为浮点数 Java中有现成的截取子串的方法可以用,而我的c语言基础比较薄弱,所学知识也不全面。 刚开始的思路是先将出现数字的子串计数,得到一共有多少个数字,然后再从子串开始处扫描,依次乘以它的位权,在百位就乘以10的2次方,依次类推.经过很长时间的思考,终于写出了此解决方法,可是却忽略了小数点的存在。 又开始用此方法试图解决存在小数点的问题,想了好久也没有解决方法。 无奈之下求助于网络,看有没有什么更好的解决办法,一经查询知道了stdlib.h库中有atof的函数可以将字符串类型的数字转换为浮点型。 于是我用一个while循环将数值子串截取下来存到一个临时数组中,将其成功的转换成浮点数,小数点的情况也解决了. ●打印后缀表达式时出现“喊烫”情况 情况如下图: 图8“喊烫”出错情况 编写完中缀转后缀的trans函数后,想打印后缀表达式检查是否正确时出现了问题,打印出来的全是“烫"。 刚开始觉得很奇怪,存的都是数字或操作符,怎么会出现汉字呢? 仔细检查程序,发现逻辑没有出错,但为什么打印不出正确结果很是不解。 通过和同学讨论,上网查询才知道,如果字符串没有结束符号\0就会“喊烫”。 再经过检查发现还真是没有给字符串加结束字符。 于是在循环的结束给exp[j]='\0’;解决了问题,得到了正确的结果。 ●程序运行时会中止 编写完程序后,编译没有错误,但运行总是会中止。 刚开始的问题是只打印出中缀表达式,光标停在下一行不动了。 也不是死循环,也没有出现语法错误。 说明程序进行到某一阶段出现问题不走了。 于是我把循环中可以打印出来帮助我分析程序的值都打印出来,包括循环有没有正常执行,有没有进栈,出栈。 就这样一点一点分析后,发现自己在循环嵌套中出现了一点逻辑问题,导致没有进行应有的判断,所以没有出正确结果.发现问题后及时改正,程序就正常运行了. 六、心得体会 因为C语言是大一时学的,当时就学了些基础的理论知识,上机的练习很少,敲的也是一些简单的分析素数,比大比小的程序。 由于有一年多没有碰过C语言,遗忘了不少。 通过这次的编程作业,把C语言的知识又重新温习了一遍.再通过和java语言的比较,大致理解了两种编程思想的不同.在这次的练习中也深刻的体会到了思维严谨,认真的态度十分重要。 所以在以后的学习道路中,要养成良好的编程习惯,思考问题要全面、编写时要仔细认真,不出拼写错误。 只有养成良好的编程习惯,在以后的工作中才可以更好的胜任职位,写出安全、可靠、稳定的软件,服务于大众。 还有一些深刻的体会就是算法很重要,所以学好数据结构,算法等课程,无疑是打好了地基,在以后各个编程的解决中都可以起到至关重要的作用。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 完整版 数学 表达式 计算 语言 实现
![提示](https://static.bingdoc.com/images/bang_tan.gif)