文档章节

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

猜猜我是吧
 猜猜我是吧
发布于 2014/05/30 21:02
字数 1697
阅读 916
收藏 30
点赞 1
评论 1

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

所谓的逆波兰表示法(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;
}


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








© 著作权归作者所有

共有 人打赏支持
猜猜我是吧
粉丝 9
博文 15
码字总数 7806
作品 0
广州
加载中

评论(1)

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

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

joenali
2013/01/18
0
1
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
一个从硬盘上取空间的STL内存空间分配器

最近在读侯捷写的《STL源码剖析》。 看完STL的内存空间分配器这章。在这章里,作者开玩笑的说,你甚至可以写一个直接从硬盘上取空间的配置器。我想,我确实可以写这样的分配器。然后今天就动...

costaxu
2012/12/09
0
0
大神告诉你学好这几点,你就学会了C语言

很多小伙伴在初学C语言的时候完全没有什么概念,完全不知道怎么去学怎样才能掌握这门语言的重要知识点。 今天小编就来总结一下学习C语言过程中四大重点吧 ! (一)C语言要学到什么程度才算差...

诸葛玥
05/25
0
0
C语言编程入门学习:求100~999的水仙花数

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

小辰带你看世界
05/31
0
0
C语言/C++编程学习强势之处的体现

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

小辰带你看世界
05/12
0
0
C语言/C++编程学习之二进制原码、反码和补码

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

小辰带你看世界
05/17
0
0
大神有话说之c++,还在迷茫的朋友可以来看一下

C++ 是一种中级语言,它是由 Bjarne Stroustrup 于 1979 年在贝尔实验室开始设计开发的。C++ 进一步扩充和完善了 C 语言,是一种面向对象的程序设计语言。C++ 可运行于多种平台上,如 Window...

悟空_b201
05/30
0
0
C语言编程学习:写的秒速计算四则混合运算项目

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

小辰带你看世界
06/05
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

Scala Configuration 相关API

Play使用了 Typesafe config library,但是也提供了一个有着更多Scala高级特性的的 Configuration 封装。不熟悉Typesafe配置的开发者可以移步 configuration文件的语法和特性文档。 读取配置...

Landas
今天
1
0
使用cookie技术 记住账号

1. 效果 2. 实现过程 2.1 前端 将用户的选中传递给后台 这个参数的获取是 参考:https://my.oschina.net/springMVCAndspring/blog/1860498 // var rememberLogin = $("#rememberLoginId").i...

Lucky_Me
今天
1
0
《趣谈网络协议》02之网络分层的真实含义

一、提出问题 1.提出问题 当你听到什么二层设备、三层设备、四层 LB 和七层 LB 中层的时候,是否有点一头雾水,不知道这些所谓的层,对应的各种协议具体要做什么“工作”? 2.这四个问题你弄...

aibinxiao
今天
2
0
Python3学习日志二 Python中的集合set和字典dict

1.集合set 定义一个集合set 我们可以看到定义集合set有两种不同的形式,如果要定义一个空的集合set不能用{}而是要用set();另外,集合是无序的,而且set中的元素是不可重复的,如果你定义了一...

Mr_bullshit
今天
0
0
adb 操作指令详解

ADB,即 Android Debug Bridge,它是 Android 开发/测试人员不可替代的强大工具,也是 Android 设备玩家的好玩具。 注:有部分命令的支持情况可能与 Android 系统版本及定制 ROM 的实现有关。...

孟飞阳
今天
0
0
nodejs安装以及环境配置(很好的node安装和配置文章,少走很多弯路)

一、安装环境 1、本机系统:Windows 10 Pro(64位) 2、Node.js:v6.9.2LTS(64位) 二、安装Node.js步骤 1、下载对应你系统的Node.js版本:https://nodejs.org/en/download/ 2、选安装目录进...

sprouting
今天
1
0
Redisson

了解了Redisson,发现使用挺简单的,接下来准备深入学习一下。 Redisson介绍 Redisson是架设于Redis基础之上的一个Java驻内存数据网格(In-Memory Data Grid) Redisson在基于NIO的Netty框架上...

to_ln
今天
0
0
python有哪些好玩的应用实现,用python爬虫做一个二维码生成器

python爬虫不止可以批量下载数据,还可以有很多有趣的应用,之前也发过很多,比如天气预报实时查询、cmd版的实时翻译、快速浏览论坛热门帖等等,这些都可以算是爬虫的另一个应用方向! 今天给...

python玩家
今天
0
0
python爬虫日志(3)-爬去异步加载网页

在浏览器检查元素页面中,选取Network中的XHR选项即可观察每次加载页面,网页发出的请求,观察url的规律即可利用封装的函数对每一页进行爬取。

茫羽行
今天
0
0
Python数据分析numpy基础-维度的认识

什么是多维数组? 核心对象是同型的多维数组(简单理解就是一个表格,通常内容都是些数字),具有相同的数据类型。 概念: 1. axes(轴):数组的维度统称为轴。 2. rank:轴的数量称为rank。...

十年磨一剑3344
今天
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部