文档章节

逆波兰式的学习、运用(附带C++写的一个整数的计算器)

猜猜我是吧
 猜猜我是吧
发布于 2014/05/30 21:02
字数 1697
阅读 1116
收藏 31

    我们今天普遍使用计算器,在初级的计算器中,由于计算机可没有人那么聪明,很难能够准确得判断运算的优先级,所以在写计算机的计算器的时候,我们需要将获得的四则运算的表达式改写为逆波兰式,方便计算机进行运算。

所谓的逆波兰表示法(Reverse Polish notation RPN, 或者逆波兰记法),这是一种数学表达式方式,在逆波兰记发中,所有操作符置于操作数的后面,因此也被称为后缀表示法。

就像是树的搜索方式,有前序、中序、后序遍历,在一棵树中,我们将操作符放在节点处,将操作数放在叶子处,优先级越高的操作越靠下,我们普通四则运算的表达式就是使用中序遍历得到的式子,而逆波兰式则是通过后序遍历得到的,举个例子:中缀表达式(a+b)*c-(a+b)/e的逆波兰式是ab+c*ab+e/-

要使用逆波兰式进行运算,首先我们需要知道如何将一个普通的四则运算表达式转换为一个标准的逆波兰式,在算法书上都有讲的,也已经是一个很成熟,很方便的算法了。

在理解逆波兰式的时候,我们使用了树的中序遍历辅助我们理解,但是在正式使用的时候,大家千万不要想着先将普通的四则表达式生成一棵树,然后再进行后序遍历生成逆波兰式,这是二逼做的事哈。我帮大家找了一个很简洁,很易懂的哈:

Step 1:我们使用两个栈构建逆波兰式,栈S1用于临时储存运算符号,运算符在栈内遵循越往栈顶优先级越高的原则;栈S2用于输入逆波兰式。由于我们需要判断式子是否读完,所以先在S1内放入一个优先级最低的运算符,大家随意哈;

Step 2:从表达式的左端开始逐个读取字符x,进行如下步骤:

         1、       x19内的数,那么继续读,直到读出完整的操作数,然后将操作数压入栈S2

                2、        x是运算符,则分情况讨论:

                若x'(',则直接压入栈s1

                若x')',则将距离栈s1栈顶的最近的'('之间的运算符,逐个出栈,依次压入栈s2,此时抛弃'('

                若x是除'('')'外的运算符,则再分如下情况讨论:

              若当前栈s1的栈顶元素为'(',则将x直接压入栈s1

                若当前栈s1的栈顶元素不为'(',则将x与栈s1的栈顶元素比较,若x的优先级大于栈s1栈顶运算符优先级,则将x直接压入栈s1。否者,将栈s1的栈顶运算符弹出,压入栈s2中,直到栈s1的栈顶运算符优先级别低于(不包括等于)x的优先级,或栈s2的栈顶运算符为'(',此时再则将x压入栈s1;

        Step 3:在进行完(2)后,检查栈s1是否为空,若不为空,则将栈中元素依次弹出并压入栈s2中(不包括最末尾的标志符);

         Step 4:完成上述步骤后,栈s2便为逆波兰式输出结果。但是栈s2应做一下逆序处理,因为此时表达式的首字符位于栈底;

      能顺利生成逆波兰式得话基本就大功告成了,相对于生成波兰式,使用波兰式计算那就是再简单不过的了,建议使用一个栈存取操作数,然后顺序读就可以了,在下面的代码中,有实现,大家可以看一下。

这里附上做练习时写的一个计算器的代码,逆波兰式的练习哈:

#include<iostream>
#include<stack>
using namespace std;
class Calculator {                         // 整数的加减乘除运算器 
	private:
		string Polish;
		long int result;
	public:
		Calculator() {
		}
		long int& getResult(string exp) {
			Polish.clear();
			stack<char> s1,s2;
			s1.push('#');         //以#号作为标记 
			char temp;
			for(int i=0; i<exp.length(); i++) {                 //利用两个堆栈生成逆波兰式 
				if (exp[i] >= '0' && exp[i] <= '9') {
					s2.push(exp[i]);
				} else if (exp[i] == '+' || exp[i] == '-' ||exp[i] == '*' ||exp[i] == '/') {
					s2.push('#');
					temp = s1.top();
					if(temp == '#'||(temp == '+' || temp == '-')&&(exp[i] == '*' ||exp[i] == '/')) {
						s1.push(exp[i]);
					} else {
						while (!(temp=='#'||temp == '(' || (temp == '+' || temp == '-') && (exp[i] == '*' ||exp[i] == '/'))) {
							s2.push(temp);
							s1.pop();
							temp = s1.top();
						}
						s1.push(exp[i]);
					  } 
					} else if(exp[i] == ')'|| exp[i] == '(') {
				  	    if(exp[i] == '(') {
				  		s1.push(exp[i]);
				  	    } else {
				  	    temp = s1.top();
				  		while (temp != '(' ) {
				  		s2.push(temp);
						s1.pop();
						temp = s1.top();
					    }
					    s1.pop();
				  	    }
				  }
				}
			while(s1.top()!='#') {
				s2.push(s1.top());
				s1.pop();
			}
			for(;s2.size()>=1;) {
				Polish.push_back(s2.top());
				s2.pop();
			}
			long int temp2;
			long int temp3;
			long int temp1=0;
			stack<long int> s3;
			bool sign =0;
			for(int i = Polish.length()-1; i >= 0; i--) {   //进行逆波兰式的运算 
				if(Polish[i] >= '0' && Polish[i] <= '9') {
					temp1 = temp1*10 +  Polish[i]-'0';
                    sign = 1;
				}
				if((Polish[i] == '#'||Polish[i] == '+'||Polish[i] == '-'||Polish[i] == '*'||Polish[i] == '/')&&(sign == 1)||(i == 0&&sign == 1)) {
					if(sign == 1){
					s3.push(temp1);
					temp1 = 0;
				    sign = 0;
					}
				}
				if(Polish[i] == '+'||Polish[i] == '-'||Polish[i] == '*'||Polish[i] == '/') {
					temp2 =s3.top();
					s3.pop();
					temp3 =s3.top();
					s3.pop();
					switch(Polish[i]) {
						case '+':
							s3.push(temp3+temp2);break;
						case '-':
							s3.push(temp3-temp2);break;
						case '*':
							s3.push(temp3*temp2);break;
						case '/':
							s3.push(temp3/temp2);break;
					}
				}
			}
			result = s3.top();
			return result;
		}
};
int main()
{
	Calculator c;    //对各种极端情况进行验证 
	cout<<c.getResult("3")<<endl;
	cout<<c.getResult("((3+4)*5+6)*7")<<endl;
	cout<<c.getResult("1+2*3")<<endl;
	cout<<c.getResult("2*5+10")<<endl;
	cout<<c.getResult("3*(5+4)")<<endl;
	cout<<c.getResult("(4+5)*(2+2)")<<endl;
	cout<<c.getResult("1/2+1/2")<<endl;
	cout<<c.getResult("0+0")<<endl;
	cout<<c.getResult("4*5-7*8")<<endl;
	cout<<c.getResult("378+456-500*12/2")<<endl;
	cout<<c.getResult("((11*(12+13)*(14+15))+(16+17))*(18+19)")<<endl;
	cout<<c.getResult("4+5")<<endl;
	cout<<c.getResult("4")<<endl;
	cout<<c.getResult("77+44-22*33/11")<<endl;
	return 0;
}


       一点点学习心得:也许大家都不太喜欢研究这些看似比较脑残的东西哈,但是,亲身写了之后,我觉得这货真是考验一个人的思维的清晰程度,而且,如果仅仅是看算法,我觉得不论背得多熟,也总是云里雾里的,还是需要自己动手写一写,感受感受。反正代码嘛,多写写总没什么坏处,特别是这种特别绕人的东西,写了后再看其它的算法,理解起来事半功倍哈。








© 著作权归作者所有

猜猜我是吧
粉丝 10
博文 15
码字总数 7806
作品 0
广州
私信 提问
加载中

评论(1)

blu10ph
blu10ph
赞~
php简单实现算术表达式转换成逆波兰式,并求解

最近一直在学习C/C++,可学的都是原理语法之类的,没有实战成绩甚是令人不爽。想用C/C++写个计算器一直是我的夙愿,刚敲键盘,就不知可否了,想来想去还是对计算器的算法不是很清楚。由于本人...

joenali
2013/01/18
894
1
汪都能理解的逆波兰计算器(C++实现)

简介 EXPLANATION 逆波兰表示法(Reverse Polish notation, RPN)也称作后缀表示法,与之对应的是波兰表示法(Polish notation),也就是前缀表示法。之所以使用“波兰”来命名,是因为发明者的...

vernzhao
2018/08/30
0
0
CalcStar —— 一个 C++ 的数学表达式计算器

下载源码 - 969.2 KB 下载发行版 - 4.4 MB 介绍 CalcStar是一个可扩展的、快速的C++函数计算器,它有着像科学计算器一样强大的计算能力。它的库可以在任何C++工程中使用,提供函数计算功能。...

oschina
2014/03/25
1K
2
C语言/C++永远都不会过时的编程语言

C语言是面向过程的,而C++是面向对象的 C和C++的区别: C是一个结构化语言,它的重点在于算法和数据结构。C程序的设计首要考虑的是如何通过一个过程,对输入(或环境条件)进行运算处理得到...

小辰带你看世界
2018/03/30
0
0
对malloc的返回值应该如何转型

本文概括叙述了一篇老文的内容,并且总结对malloc返回值的3种转型方式,(相对于原文)更全面的总结其各自的应用范围。 1. 原文内容 2. 对malloc的3种转型方式 3. 各自的应用范围 以前有篇文...

Start-up
2012/05/08
65
0

没有更多内容

加载失败,请刷新页面

加载更多

计算机实现原理专题--二进制减法器(二)

在计算机实现原理专题--二进制减法器(一)中说明了基本原理,现准备说明如何来实现。 首先第一步255-b运算相当于对b进行按位取反,因此可将8个非门组成如下图的形式: 由于每次做减法时,我...

FAT_mt
昨天
6
0
好程序员大数据学习路线分享函数+map映射+元祖

好程序员大数据学习路线分享函数+map映射+元祖,大数据各个平台上的语言实现 hadoop 由java实现,2003年至今,三大块:数据处理,数据存储,数据计算 存储: hbase --> 数据成表 处理: hive --> 数...

好程序员官方
昨天
7
0
tabel 中含有复选框的列 数据理解

1、el-ui中实现某一列为复选框 实现多选非常简单: 手动添加一个el-table-column,设type属性为selction即可; 2、@selection-change事件:选项发生勾选状态变化时触发该事件 <el-table @sel...

everthing
昨天
6
0
【技术分享】TestFlight测试的流程文档

上架基本需求资料 1、苹果开发者账号(如还没账号先申请-苹果开发者账号申请教程) 2、开发好的APP 通过本篇教程,可以学习到ios证书申请和打包ipa上传到appstoreconnect.apple.com进行TestF...

qtb999
昨天
10
0
再见 Spring Boot 1.X,Spring Boot 2.X 走向舞台中心

2019年8月6日,Spring 官方在其博客宣布,Spring Boot 1.x 停止维护,Spring Boot 1.x 生命周期正式结束。 其实早在2018年7月30号,Spring 官方就已经在博客进行过预告,Spring Boot 1.X 将维...

Java技术剑
昨天
18
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部