波兰式与逆波兰式的转换和表达式求值

您所在的位置:网站首页 表达式求值总结的方法 波兰式与逆波兰式的转换和表达式求值

波兰式与逆波兰式的转换和表达式求值

2024-07-08 10:01:57| 来源: 网络整理| 查看: 265

文章目录 一、前言二、表达式1.中缀表达式1.1 定义 2.前缀表达式2.1 定义2.2 求值 3.后缀表达式3.1 定义3.2 求值 三、表达式转换1.中缀表达式转换成后缀表达式1.1 算法1.2 例子 2.中缀表达式转换成前缀表达式 四、END

一、前言

逆波兰表示法(Reverse Polish notation,RPN,或逆波兰记法),是一种是由波兰数学家扬·武卡谢维奇1920年引入的数学表达式方式,在逆波兰记法中,所有操作符置于操作数的后面,因此也被称为后缀表示法。逆波兰记法不需要括号来标识操作符的优先级。

二、表达式 1.中缀表达式 1.1 定义

中缀表达式就是我们最熟悉的一种表达式:1+2,3*(3+4),1+2*3+6,…等都是中缀表示法。对于人们来说,也是最直观的一种求值方式,先算括号里的, 然后算乘除,最后算加减,但是,计算机处理中缀表达式却并不方便,故引出了前缀和后缀。中缀表达式得名于它是由相应的语法树的中序遍历的结果得到的。

2.前缀表达式 2.1 定义

前缀表达式又叫做波兰式。同样的道理,表达式的前缀表达式是由相应的语法树的前序遍历的结果得到的。

如1 + 2 * (3 - 4) - 5 * 6的前缀表达式为- + 1 * 2 - 3 4 * 5 6

2.2 求值

由前缀表达式求出结果有下面两种思路:

从左至右扫描表达式,如果一个操作符后面跟着两个操作数时,则计算。然后将结果作为操作数替换(这个操作符和两个操作数), 重复此步骤,直至所有操作符处理完毕。如- + 1 * 2 - 3 4 * 4 5,扫描到- 3 4时,会计算3 - 4 = -1,表达式变成:- + 1 * 2 -1 * 5 6继续扫描到* 2 -1,计算2 * -1 = -2,表达式变成:- + 1 -2 * 5 6,继续+ 1 -2,依此类推。由1知,要多遍扫描表达式,比较复杂,我们可以用一个栈S来实现计算,扫描从右往左进行,如果扫描到操作数,则压进S,如果扫描到操作符,则从S弹出两个操作数进行相应的操作,并将结果压进S(S出2进1),当扫描结束后,S的栈顶就是表达式结果。 3.后缀表达式 3.1 定义

后缀表达式又叫做逆波兰式。它是由相应的语法树的后序遍历的结果得到的。如1 + 2 * (3 - 4) - 5 * 6的后缀表达式为:1 2 3 4 - * + 5 6 * -

注意:逆波兰记法并不是简单的波兰表达式的反转。因为对于不满足交换律的操作符,它的操作数写法仍然是常规顺序,如,波兰记法“/ 6 3”的逆波兰记法是“6 3 /”而不是“3 6 /”;数字的数位写法也是常规顺序。

3.2 求值

由前缀表达式求出结果十分方便,只需要用一个栈S实现:

扫描从左往右进行,如果扫描到操作数,则压进S,如果扫描到操作符,则从S弹出两个操作数进行相应的操作,并将结果压进S(S出2进1),当扫描结束后,S的栈顶就是表达式结果。后缀表达式和前缀表达式看起来就像一对逆过程,实际上并不是这样子,因为字符读取的时候都是从左往右的,所以,前缀表达式往往需要用两个栈来计算,其中一个栈用来预处理:将字符串倒序压进栈中。 三、表达式转换 1.中缀表达式转换成后缀表达式

既然中缀表达式对于计算机的运算并不便利,而前缀后缀表达式的计算相对简单方便。因此,找到一种途径将中缀表达式转换成前缀后缀表达式就十分重要。实际上,二者的转换算法看起来也很像一个逆过程。因此,我们着重讨论中缀转后缀。

从理论上讲,已知一棵二叉树的中序遍历序列,要求出它的后序遍历序列是不唯一的,即文法是有多义性的。所以,在这里我们要加上优先级这一限制条件,转换就变得唯一了。

1.1 算法 算法: 中缀表达式转换成后缀表达式.输入: 中缀表达式串.输出: 后缀表达式串. PROCESS BEGIN: 1.从左往右扫描中缀表达式串s,对于每一个操作数或操作符,执行以下操作; 2.IF (扫描到的s[i]是操作数DATA) 将s[i]添加到输出串中; 3.IF (扫描到的s[i]是开括号'(') 将s[i]压栈; 4.WHILE (扫描到的s[i]是操作符OP) IF (栈为空 或 栈顶为'(' 或 扫描到的操作符优先级比栈顶操作符高) 将s[i]压栈; BREAK; ELSE 出栈至输出串中 5.IF (扫描到的s[i]是闭括号')') 栈中运算符逐个出栈并输出,直到遇到开括号'('; 开括号'('出栈并丢弃; 6.返回第1步 7.WHILE (扫描结束而栈中还有操作符) 操作符出栈并加到输出串中 PROCESS END 1.2 例子

中缀表达式5 + ((1 + 2) * 4) - 3写作转换成后缀表达式:5 1 2 + 4 * + 3 -

下表给出了该逆波兰表达式从左至右求值的过程,堆栈栏给出了中间值,用于跟踪算法。

输入操作堆栈注释5入栈51入栈5, 12入栈5, 1, 2+加法运算5, 31, 2出栈,将结果3入栈4入栈5, 3, 4*乘法运算5, 123, 4出栈,将结果12入栈+加法运算175, 12出栈,将结果17入栈3入栈17, 3-减法运算1417, 3出栈,将结果14入栈

计算完成时,栈内只有一个操作数,这就是表达式的结果:14。 上述运算可以重写为如下运算链方法:1 2 + 4 * 5 + 3 -

2.中缀表达式转换成前缀表达式

中缀表达式转换成前缀表达式和中缀表达式转换成后缀表达式十分类似,只需要将扫描方向由前往后变成由后往前,将(改为),)改为(。

四、END

具体的应用可以见我的另外一篇博客:基于逆波兰表达式实现图形化混合计算器.



【本文地址】

公司简介

联系我们

今日新闻


点击排行

实验室常用的仪器、试剂和
说到实验室常用到的东西,主要就分为仪器、试剂和耗
不用再找了,全球10大实验
01、赛默飞世尔科技(热电)Thermo Fisher Scientif
三代水柜的量产巅峰T-72坦
作者:寞寒最近,西边闹腾挺大,本来小寞以为忙完这
通风柜跟实验室通风系统有
说到通风柜跟实验室通风,不少人都纠结二者到底是不
集消毒杀菌、烘干收纳为一
厨房是家里细菌较多的地方,潮湿的环境、没有完全密
实验室设备之全钢实验台如
全钢实验台是实验室家具中较为重要的家具之一,很多

推荐新闻


图片新闻

实验室药品柜的特性有哪些
实验室药品柜是实验室家具的重要组成部分之一,主要
小学科学实验中有哪些教学
计算机 计算器 一般 打孔器 打气筒 仪器车 显微镜
实验室各种仪器原理动图讲
1.紫外分光光谱UV分析原理:吸收紫外光能量,引起分
高中化学常见仪器及实验装
1、可加热仪器:2、计量仪器:(1)仪器A的名称:量
微生物操作主要设备和器具
今天盘点一下微生物操作主要设备和器具,别嫌我啰嗦
浅谈通风柜使用基本常识
 众所周知,通风柜功能中最主要的就是排气功能。在

专题文章

    CopyRight 2018-2019 实验室设备网 版权所有 win10的实时保护怎么永久关闭