数学表达式有三种:前缀表达式,中缀表达式,后缀表达式。
中缀表达式就是我们平常见到的,如4+ 2 * 5 - 7/11 ,这个式子人算起来方便,但是计算机算起来却计算复杂。对于计算机,最好是将此式转换为前缀表达式或后缀表达式后再计算。
在写计算器之前,首先要知道一点基本知识:
1.中缀表达式转换为后缀表达式
举个例子:
4+ 2 * 5 - 7/11 这是中缀表达式,它的后缀表达式是: 4 2 5 * 7 11 / - + .(或者4 2 5 * + 7 11 / - )
其实也很简单,把中缀表达式其实就是表达式对应的二叉树的中序遍历,后缀表达式是对应二叉树的后序遍历,前缀表达式是前序遍历。
算法基本思想:
使用三个数组,一个数组保存用户输入的表达式(中缀表达式),一个数组保存后缀表达式,一个数组作为运算符的栈。
从头到尾扫描中缀表达式,对不同类型的字符按不同情况处理;
1. 如果是数字则直接放入后缀表达式数组;
2. 如果是左括号则直接入栈;
3. 如果是右括号,则把从栈顶直到对应左括号之间的运算符依次退栈[放入后缀表达式数组],并清除对应的左括号;
4. 对于运算符,如果该运算符的优先级大于栈顶优先级,则直接入栈;
若该运算符的优先级小于等于栈顶优先级,则先把栈顶运算符出栈,写入后缀表达式数组,然后再入栈;若该运算符的优先级小于等于栈顶优先级,则先把栈顶运算符出栈,写入后缀表达式数组,重复此操作,直到该运算符的优先级大于栈顶运算符的优先级,然后将该运算符入栈;(感谢
liwenhaosuper的test
case,现已将错误的地方修正,并修改了相应的代码)
5. 扫描完成后,取出栈中所有运算符,写入后缀表达式数组。
注:运算符优先级: *,/ 大于 +,- 大于 (
2.计算后缀表达式
算法思想:
对后缀表达式求值比直接对中缀表达式求值简单。在后缀表达式中,不需要括号,而且操作符的优先级也不再起作用了。可以通过简单的出栈如栈操作完成运算。
1. 初始化一个空栈
2. 从左到右读入后缀表达式
3. 如果字符是一个操作数,把它压入堆栈。
4. 如果字符是个操作符,弹出两个操作数,执行恰当操作,然后把结果压入堆栈。如果您不能够弹出两个操作数,后缀表达式的语法就不正确。
5. 到后缀表达式末尾,从堆栈中弹出结果。若后缀表达式格式正确,那么栈应该为空。
计算器程序如下: 本程序可计算非负数学表达式,可计算非整数,假设输入合法,结果保留2位小数
#include <stdio.h>
#include <stdlib.h>
#define MAX_LEN 80
void convert2postfix(char *src,char *dst);
float cal(char *src);
int main(){
char str1[MAX_LEN],str2[MAX_LEN];
float res;
gets(str1);
convert2postfix(str1,str2);
printf("src:%s\n",str1);
printf("dst:%s\n",str2);
res = cal(str2);
printf("result:%.2f\n",res);
return 0;
}
//中缀表达式转换为后缀表达式(操作符与操作数之间应有空格隔开)
void convert2postfix(char *src,char *dst){
char *psrc,*pdst;
char stack[MAX_LEN];
int top;
top = -1;
psrc = src;
pdst = dst;
while (*psrc != '\0') {
if (*psrc >= '0' && *psrc <= '9') {
*pdst = *psrc;
pdst++;
//加入分隔空格
if (!(*(psrc+1)>= '0' && *(psrc+1)<= '9') && *(psrc+1)!= '.') {
*pdst = ' ';
pdst++;
}
}
if (*psrc == '.') {
*pdst = *psrc;
pdst++;
}
if (*psrc == '(') {
stack[++top] = *psrc;
}
if (*psrc == ')') {
while (stack[top] != '(') {
*pdst = stack[top--];
pdst++;
//加入分隔空格
*pdst = ' ';
pdst++;
}
//弹出'('
top--;
}
if (*psrc == '*' || *psrc == '/') {
if (stack[top] == '*' || stack[top] == '/') {
*pdst = stack[top--];
pdst++;
//加入分隔空格
*pdst = ' ';
pdst++;
}
stack[++top] = *psrc;
}
if (*psrc == '+' || *psrc == '-') {
while ( stack[top] == '*'
|| stack[top] =='/'
|| stack[top] == '+'
|| stack[top] == '-') {
*pdst = stack[top--];
pdst++;
//加入分隔空格
*pdst = ' ';
pdst++;
}
stack[++top] = *psrc;
}
psrc++;
}
//扫描完成后,取出栈中所有运算符,写入后缀表达式数组。
while (top != -1 ) {
*pdst = stack[top--];
*pdst++;
*pdst = ' ';
pdst++;
}
*pdst = '\0';
}
//计算后缀表达式
float cal(char *src){
float stack[MAX_LEN];
float opd1,opd2;
int top;
char *p,*pre;
top = -1;
p = src;
while (*p != '\0') {
if (*p >= '0' && *p <= '9') {
pre = p;
while ((*p >= '0' && *p <= '9') || *p == '.') {
p++;
}
*p = '\0';
stack[++top] = atof(pre);
}
if (*p == '+' ||*p == '-' ||*p == '*' ||*p == '/' ) {
opd2 = stack[top--];
opd1 = stack[top--];
switch (*p) {
case '+':
stack[++top] = opd1+opd2;
break;
case '-':
stack[++top] = opd1-opd2;
break;
case '*':
stack[++top] = opd1*opd2;
break;
case '/':
//更严格一点,应该处理除数为0的情况
stack[++top] = opd1/opd2;
break;
}
}
p++;
}
return stack[top--];
}
分享到:
相关推荐
闲来无事自己写了一个计算器的小程序,有兴趣的同学情拿去耍耍
闲来无事自己写的一个简单计算器,虽然功能简单,不过考虑到很多细节,选择了一些实用的知识。比如用正则表达式匹配分割、表达式求值(程序使用中缀表达式转前缀表达式求值方法)、浮点数据精确计算问题、格式控制等...
闲来无事做的一个表达式计算器。 输入表达式后按回车即可得到计算结果。 支持正弦、余弦、正切、反正切、绝对值、平方根、指对数函数、随机数等数学函数的运算。因为采用的是VBScript的脚本解释引擎,所以事实上...
闲来无聊,用eclipse写了个计算器程序,但只能实现整数的输入和计算,结果也只能取整!迫切希望能得到小数计算的算法!
原创简易C++计算器原代码,仅支持普通加减乘除,及幂计算,支持小括号 C-free调试通过 业余爱好者,闲来无事之作,欢迎下载
闲来无事,自己写的一个易语言源码,请多指教,不喜勿喷! 好好学习天天向上
闲来自己做的一个计算器,非常完整的计算器,完全模拟的windows系统的,算法也完善,各项功能都有实现,相对网上的资源,我的这个有最完善的功能,自己测试了很久,解了很久的bug,不过也许还有一些自己没发现的bug,...
闲来无事,用MFC写了一个计算器,比较简单,但考虑的内容到不少,当然有更好的写法,计算其中的%没实现,应该和=差不多,当然在我测的时候,有时候会出现BUG,整体思想是很简单。
用eclipse写的简单计算器app, 闲来无事,用android做一个计算器玩玩,想着做一个私密空间,表面是计算器,按下原先设定的算式后可以跳转到私密界面,当想想有些费事,以后若还有闲散时间,再来实现。
闲来无聊,做了一个随机数为基础的人品计算器小游戏。 这样就可以娱乐一下。测试一下每时每刻的人品值啦。
闲来无事自己编写的数独计算器(包括核心计算部分),运用推算和迭代方案,快速计算计算结果,并输出计算步骤。通过MFC实现,vs2008编译,欢迎爱好者们下载学习指导!
本人不才,闲来无事用vue,HTML,js,css写了一个非常简单的两数四则运算器,只有一百多行代码
自己闲来无事做了一个基于C语言的进制转换器,可在十进制、十六进制、二进制中任意转换,方便自己平时在写代码时候的推算。
供大家参考,闲来无事,做个玩玩
本文实例为大家分享了js实现简易计算器的具体代码,供大家参考,具体内容如下 最近,博主闲来无聊,就没事用js写了个简易计算器(博主是搞后端的,不是前端>_<)。其实,感觉搞前端的很幸福,自己弄出点东西很有...
闲来无事,上传一实用电子设计计算小工具,与同行共酌!
今天闲来无聊,想写点什么,突然想到用javascript写一个计算器。程序还存在很多的Bug,先在这里记录一下,以后慢慢更正。 代码如下: <!DOCTYPE ...
【插入批注背景】 可以选定任意一幅图片为批注背景来插入一个带图片背景的批注。可视化窗体操作,可随时更换批注样式,也支持批量多存储格样式修改。 【插入行数】 对工作表隔行插入行并可以复制标题行,其中对相隔...
算力网络旨在将全网闲置的算力通过网络连接汇聚成统一的计算资源,并进行管理和调度,通过网络的形式将计算资源提供给用户,为多种场景的应用和服务提供一个可伸缩、高效且经济的解决方案。 算力是指设备根据内部...
【插入批注背景】 可以选定任意一幅图片为批注背景来插入一个带图片背景的批注。可视化窗体操作,可随时更换批注样式,也支持批量多存储格样式修改。 【插入行数】 对工作表隔行插入行并可以复制标题行,其中对相隔...