文档章节

逆波兰表达式算法分析。

柳初心
 柳初心
发布于 2017/04/25 21:15
字数 682
阅读 12
收藏 0

中缀表达式到后缀表达式的转换

例:1+2*3*(3+5) ———— 23*35+*1+

 

逆波兰表达式算法:

网上大部分都是写通过两个栈的入栈与出栈进行操作,但是其中有一个是要以先入先出的顺序操作栈,不符合正常的JAVA的认知,因此改为操作数队列与栈,其实本质相同。

一、 将中缀表达式转换成后缀表达式算法:

1、从左至右扫描一中缀表达式。

2、若读取的是操作数,则判断该操作数的类型,并将该操作数输出至操作数队列(以下简称队列)

3、若读取的是运算符

  (1) 该运算符为左括号"(",则直接存入运算符栈。

  (2) 该运算符为右括号")",则输出运算符栈中的运算符到操作数队列,直到遇到左括号为止。并将左右括号从栈中取出。

  (3) 该运算符为非括号运算符:

      (a) 若运算符栈栈顶的运算符为括号,则直接存入运算符栈。

      (b) 若比运算符栈栈顶的运算符优先级高,则直接存入运算符栈。

      (c) 若比运算符栈栈顶的运算符优先级低或相等,则输出栈顶运算符到操作数队列,并将当前运算符压入运算符栈。

4、当表达式读取完成后运算符堆栈中尚有运算符时,则依序取出运算符到操作数队列,直到运算符栈为空。

二、实例分析

分析前,要明确各个运算符的优先级数。 由小到大依此为(注:以,为分隔):  +-,*\,负号

例如 : 1+2*3*((-1)*3);

1.读取1压入队列,

2.读取“+”压入栈,

3.读取2压入队列,

4.读取“*” ,判断与栈顶元素“+”的优先级,大于,则压入栈。

5.读取3压入队列,

6.读取“*”,此时栈顶元素为“*” 优先级相同,则将栈顶元素“*”输出至队列。

7.读取“(”压入栈中。

8.读取“(”压入栈中。

9.读取“-(负号)”压入栈中。

10.读取1压入队列。

11.读取“)”,将 “-”号压入队列。队列中还剩一个“(”。

12.读取“*”压入栈中。

13.读取3压入队列。

14.读取“)”,将“*”号输出并压入队列。运算符栈中还剩 “*” 与“+”

15.将运算符栈清空,将“+“ 、“ * ”  依次压入队列。

15.操作数队列中 先入先出的顺序出栈,则,输出为:123*1-*3*+

 

嗯:还是有问题的,就是“-”负号的处理问题,希望可以得到指正。

代码明天手搓,今天先写个作业 。

 

 

© 著作权归作者所有

共有 人打赏支持
柳初心
粉丝 0
博文 31
码字总数 15977
作品 0
南昌
私信 提问
计算逆波兰式

在程序设计中,可能碰到需要对字符串数学表达式求值的问题,常用的方法是解析表达式,生成二叉树,然后进行计算。编译器就是使用这种方法来解析程序中的表达式的。这种方法实现起来有点难度,...

一贱书生
2016/12/26
25
0
逆波兰式的学习、运用(附带C++写的一个整数的计算器)

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

猜猜我是吧
2014/05/30
0
1
【讲古堂】表达式求值

【讲古堂】表达式求值 (dubenju@126.com 2015/12/27) 什么是表达式 表达式是由数字,操作符,变量,常量等有意义地组合而成并能求得结果的式子。 例如: 32 + ( ( 9 * Celsius ) / 5 ) 4 +...

壶漏子
2015/12/27
84
0
堆栈的应用——用JavaScript描述数据结构

栈(stack)又名堆栈,它是一种运算受限的线性表。其限制是仅允许在表的一端进行插入和删除运算。这一端被称为栈顶,相对地,把另一端称为栈底。 一、实现一个栈类Stack 基于堆栈的特性,可以...

我是leon
2018/08/10
0
0
php简单实现算术表达式转换成逆波兰式,并求解

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

joenali
2013/01/18
0
1

没有更多内容

加载失败,请刷新页面

加载更多

dockerfile 镜像构建(1)

通用dockerfile 利用已经编译好的.jar 来构建镜像。要构建的目录如下: [root@iZuf61quxhnlk9m2tkx16cZ demo_jar]# docker build -t demo:1 . 运行镜像: [root@iZuf61quxhnlk9m2tkx16cZ de...

Canaan_
31分钟前
1
0
Redis radix tree源码解析

Redis实现了不定长压缩前缀的radix tree,用在集群模式下存储slot对应的的所有key信息。本文将详述在Redis中如何实现radix tree。 核心数据结构 raxNode是radix tree的核心数据结构,其结构体...

阿里云云栖社区
34分钟前
7
0
vue import 传入变量

在做动态添加component的时候,传入变量就会报错,出现以下错误信息: vue-router.esm.js?fe87:1921 Error: Cannot find module '@/components/index'. at eval (eval at ./src/components ......

朝如青丝暮成雪
36分钟前
1
0
Flutter开发 Dio拦截器实现token验证过期的功能

前言: 之前分享过在Android中使用Retrofit实现token失效刷新的处理方案,现在Flutter项目也有“token验证过期”的需求,所以接下来我简单总结一下在Flutter项目中如何实现自动刷新token并重...

EmilyWu
37分钟前
7
0
final Map可以修改内容,final 常量不能修改

1.final Map 可以put元素,但是不可以重新赋值 如: final Map map = new HashMap(); map = new HashMap();//不可以 因为栈中变量map引用地址不能修改 2.final str = “aa”; str = "bb";/......

qimh
40分钟前
2
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部