文档章节

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

猜猜我是吧
 猜猜我是吧
发布于 2014/05/30 21:02
字数 1697
阅读 1005
收藏 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
0
1
汪都能理解的逆波兰计算器(C++实现)

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

vernzhao
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程序的设计首要考虑的是如何通过一个过程,对输入(或环境条件)进行运算处理得到...

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

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

Start-up
2012/05/08
0
0

没有更多内容

加载失败,请刷新页面

加载更多

零距离接触阿里云时序时空数据库TSDB

概述 最近,Amazon新推出了完全托管的时间序列数据库Timestream,可见,各大厂商对未来时间序列数据库的重视与日俱增。 阿里云TSDB是阿里巴巴集团数据库事业部研发的一款高性能分布式时序时空...

阿里云云栖社区
15分钟前
0
0
OkHttpClient封装

import java.io.BufferedReader; import java.io.InputStream; import java.io.InputStreamReader; import java.util.Map; import java.util.TreeMap; import java.util.Map.Entry; import o......

尘叙缘
17分钟前
1
0
零距离接触阿里云时序时空数据库TSDB

概述 最近,Amazon新推出了完全托管的时间序列数据库Timestream,可见,各大厂商对未来时间序列数据库的重视与日俱增。 阿里云TSDB是阿里巴巴集团数据库事业部研发的一款高性能分布式时序时空...

阿里云官方博客
17分钟前
0
0
centos 7 nginx_install.sh

#!/bin/bashset -eprintf "============开始安装nginx\n"printf "============输入nginx下载url,按Enter默认下载1.14.2版本\n"download_url='';while truedoread down...

偶遇一只小仙女
18分钟前
0
0
数据库高并发下乐观锁的原理

在高并发下,经常需要处理SELECT之后,在业务层处理逻辑,再执行UPDATE的情况。 若两个连接并发查询同一条数据,然后在执行一些逻辑判断或业务操作后,执行UPDATE,可能出现与预期不相符的结...

hansonwong
20分钟前
2
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部