java中缀表达式转后缀表达式（逆波兰算法）
四则运算是栈的重要应用之一
中缀表达式转后缀表达式（逆波兰算法）过程
- 从左到右遍历中缀表达式
- 数字直接输出为后缀表达式一部分
- 如果是符号，则判断与栈顶元素的优先级
- 高于栈顶元素优先级直接入栈
- 低于或等于栈顶优先级栈顶元素出栈并输出为后缀表达式一部分（注意这里是递归比较栈顶元素的优先级并出栈），最后将当前元素入栈
直到遍历完中缀表达式，最终输出后缀表达式
下面是自己的实现源码
package com.yhq.demospringboot;
import org.apache.commons.lang3.StringUtils;
import java.util.*;
import java.util.concurrent.LinkedBlockingQueue;
/*** yanghq* 2018/3/12*/
public class PreToAfterUtil {private static String leftChar = "(";
private static String rightChar = ")";
private static Map<String, Integer> operationSymbolMap = new HashMap<>();static {//初始化符号和优先级operationSymbolMap.put(")",00); //右括号需匹配左括号，故优先级最低operationSymbolMap.put("+",10);operationSymbolMap.put("-",10);operationSymbolMap.put("*",20);operationSymbolMap.put("/",20);operationSymbolMap.put("(",30);
}/*** 中缀表达式转化为后缀表达式* @param strings* @return*/
public Queue parsePre(String[] strings) {Stack<String> preStack = new Stack<String>();Queue<String> queue = new LinkedBlockingQueue();int i = 0;while(i<strings.length && Objects.nonNull(strings[i])) {if(StringUtils.isNumeric(strings[i])) {queue.add(strings[i]);}else if(StringUtils.isNotEmpty(strings[i])) {if(preStack.isEmpty()) {preStack.push(strings[i]);} else {String top = preStack.pop();if(comparePriority(strings[i], top) < 0) {if(top.equals(leftChar)) {preStack.push(top);preStack.push(strings[i]);}else if(strings[i].equals(rightChar)) {appendTo(queue, top);preStack.pop();} else{appendTo(queue, top);popPre(preStack, strings[i], queue);preStack.push(strings[i]); //当前元素入栈}} else {preStack.push(top);preStack.push(strings[i]);}}}i++;}while (!preStack.isEmpty()) {queue.add(preStack.pop());}return queue;
}/*** 递归比较当前元素与栈顶元素优先级* @param preStatck* @param charTemp* @param queue*/
public void popPre(Stack<String> preStatck, String charTemp, Queue queue) {if(!preStatck.isEmpty()) {String top = preStatck.pop();if(comparePriority(charTemp, top) <= 0) {//低于栈顶元素，成为后缀表达式一部分appendTo(queue, top);popPre(preStatck, charTemp, queue);} else {preStatck.push(top);}}
}private void appendTo(Queue queue, String s) {if(!s.equals(leftChar) && !s.equals(rightChar)) {queue.add(s);}
}/*** 比较优先级* @param start* @param to* @return*/
private int comparePriority(String start, String to) {return operationSymbolMap.get(start).compareTo(operationSymbolMap.get(to));
}/*** 计算后缀表达式结果* @param queue* @return*/
public int computeResult(Queue<String> queue) {int result = 0;if(Objects.isNull(queue)) {return result;}String s = queue.poll();Stack<Integer> stack = new Stack();while(Objects.nonNull(s)) {if(StringUtils.isNumeric(s)) {stack.push(Integer.valueOf(s));}else if(!StringUtils.isEmpty(s)) {int first = 0;int second = 0;switch (s) {case "+" :first = stack.pop();second = stack.pop();result = first + second;stack.push(result);break;case "-" :first = stack.pop();second = stack.pop();result = second - first;stack.push(result);break;case "*" :first = stack.pop();second = stack.pop();result = first * second;stack.push(result);break;case "/" :first = stack.pop();second = stack.pop();result = second/first;stack.push(result);break;}}s = queue.poll();}return result;
}/*** 测试* @param args*/
public static void main(String[] args) {String[] pre = new String[]{"8","+","(","6","-","1",")","*","2","+","10","/","2"};StringBuilder sb = new StringBuilder();for (int i = 0; i < pre.length; i++) {sb.append(pre[i]);}System.out.println("前缀表达式：" + sb.toString());Queue queue = new PreToAfterUtil().parsePre(pre);System.out.println("后缀表达式：" + queue.toString());System.out.println("后缀表达式计算结果：" + new PreToAfterUtil().computeResult(queue));
}}输出结果展示
前缀表达式：8+(6-1)*2+10/2
后缀表达式：[8, 6, 1, -, 2, *, +, 10, 2, /, +]
后缀表达式计算结果：23
转载于:https://blog.51cto.com/11290909/2085571
相关文章：
Wpf消息循环之消息传递
几天遇见一个问题需要检查某个wpf程序是否已经运行，如果没有运行则启动传递参数，如果已运行则需要直接传递消息。在没有运行 情况下传递参数很简单，我们只需要Process cmd窗口启动并传递参数，在程序中处理。但是如果程序已经启动有…
【Qt】使用sqlite3数据库时，主键自增和获取自增后的主键的
创建数据表格，设置主键自增 创建数据库时，启用主键自增加特性 Create table testTable (id INTEGER PRIMARY KEY AUTOINCREMENT,。。。。 注意事项：设置主键自增时（AUTOINCREMENT），主键类型必须是INTEGER&…
拿下斯坦福和剑桥双offer，00后的算法学习之路
董文馨，00后，精通英语，西班牙语。斯坦福大学计算机系和剑桥大学双Offer，秋季将进入斯坦福大学学习。10岁开始在国外上学；12岁学Scratch；13岁学HTML & CSS；14岁开始学Python & Java&…
Mybatis【配置文件】就是这么简单
配置文件和映射文件还有挺多的属性我还没有讲的，现在就把它们一一补全 映射文件 在mapper.xml文件中配置很多的sql语句，执行每个sql语句时，封装为MappedStatement对象，mapper.xml以statement为单位管理sql语句 Statement的实际位置…
cto denalil
Denali使用准虚拟化技术来提高x86电脑上虚拟机的性能。Denali的虚拟机为因特网服务专门支持了最小化的操作系统。 系统可以运行上千虚拟机。Xen与Denali不同，因为它试图运行适当数量的完整操作系统，而非大量轻量级操作系统。转载于:https://blog.51cto.c…
Redis学习笔记 - 数据类型与API（1）Key
Redis学习笔记 - 数据类型与API（1）Key Key相关命令 1. 常用命令 命令含义时间复杂度keys查找所有符合给定模式 pattern 的 keyO(N)， N 为数据库中 key 的数量dbsize计算key的总数O(1)exists检查key是否存在O(1)del删除指定的key-valueO(1)exp…
【Qt】enum和QString的相互
使用Q_ENUM注册enum Q_ENUM使用元对象系统meta-object来注册，因此在enum所在的类中必须包含宏Q_OBJECT或者Q_GADGET。 例子如下 class MyClass : public QObject{Q_OBJECTpublic:MyClass(QObject *parent = 0);~MyClass();enum Priority { High, Low, VeryHigh, VeryLow };Q_…
Gmail全球大规模宕机
整理 | 非主流出品 | AI科技大本营（ID: rgznai100）今天（3 月 13 日），Google 的多项服务在全球范围内出现了不同程度的宕机，包括 Gmail、Google Drive、 Hangouts、谷歌地图等。受影响最大的是拥有超 10 亿用…
搭建域控服务器
作业环境 服务器端(VirtualBox VM) 操作系统：Windows Server 2003 Enterprise Edition SP2 IPAddress：192.168.1.1/255.255.255.0 Gateway：null 客户端(VirtualBox VM) 操作系统：Windows XP SP3 IPAddress：192.168.1.2…
【Git】ubuntu安装git
sudo apt-get install git 图形界面的：sudo apt-get install git-gui 查看ssh服务是否启动 sudo ps -e | grep ssh 如果没有启动执行如下命令； sudo service ssh start 如果没有ssh，使用如下命令安装 sudo apt-get install ssh
Composer 篇
学习网站Composer 中文网 资源包 Packagist Packagist / Composer 中国全量镜像如何安装 Composer下载 Composer安装前请务必确保已经正确安装了PHP。打开命令行窗口并执行php -v查看是否正确输出版本号。打开命令行并依次执行下列命令安装最新版本的 Composer：php …
西工大开源拥挤人群数据集生成工具，大幅提升算法精度 | CVPR 2019
作者 | 周强（CV君）转载自 我爱计算机视觉（公众号id：aicvml）近年来，因为拥挤人群计数在视频监控、公共安全方面的应用广泛，引起了不少学者的关注。简单说来这个任务就是给定图像，返回…
getElementById 不能取得visible=false 的控件解决方法
想要绑定textbox的回车事件到一个按钮上，但不想显示这个按钮，如果你把这个button的visible设置为false,那么你使用 getElementById是获取不到的，或者说取到的为空。这是因为Visiblefalse，在编译后，该控件在页面上不显示…
【Git】在本地创建git库管理自己的代码
1、创建本地库 git init . 新建库 git config --global user.email “hello163.com” git config --global user.name “laoer” git config --global core.editor vim //将默认编辑器由nano更改为vim 2、提交 2.1 git add . 将当前目录下所有文件添加到提交缓冲区 2.2 git …
“智慧血联网平台”亮相军民融合技术装备博览会
该平台可实现血液全程跟踪溯源，为大众提供安全、透明、便捷的用血服务。 一个打造智慧化血液管理新模式的血联网平台最近亮相第三届中国军民融合技术装备博览会。该平台可实现血液全程跟踪溯源，为大众提供安全、透明、便捷的用血服务。 此次博览会以“聚…
AI专利之争：小米超华为，国家电网才是大Boss？
作者 | 一一编辑 | 琥珀出品 | AI科技大本营（ID:rgznai100）以往相关机构发布 AI 专利数量排行榜时，如果表明“中国在 AI 专利申请数量上已经超过美国，中国在 AI 技术实力上已在国际上遥遥领先”，这类榜单会招致对中国科…
SLF4J 的几种实际应用模式--之二：SLF4J+Logback
前面讲的 SLF4J 的用法之一是 SLF4JLog4J，而这里要推出的组合是 SLF4JLogBack。不用 Log4J？难道还有比 Log4J 更好的日志实现吗？是的，答案就是 LogBack。假如你知道 LogBack 和 Log4J 是同出一位大师之手，你就不会觉得…
10行Python，搭建一个游戏AI | 视频教程
昨天为大家推荐了三个Python视频，包含：《利用Python，用4分钟时间搭建一个情感分析系统》、《7行Python代码，搭建一个可以识花的机器学习APP》、《10行Python，搭建一个可以自动作曲的神经网络》，今天营长再为…
ABAP git客户端
Jerry习惯把自己写的小程序放到自己的github上：https://github.com/i042416 对于写的ABAP程序，需要先把SAPGUI里的代码手动拷贝到本地，然后用git客户端push到github上。 但是其实可以直接在SAPGUI里通过一个ABAP实现的git客户端将代码push到g…
【Git】git 与远程库交互
一、远程操作 1、克隆 git clone <url> 2、提交 git add ：添加 git commit -m “修改信息” ：提交到本地 git branch -a ：查看所有分支，红色的是远程分支 git fetch ：获取远程分支 git diff HEAD FETCH_HEAD…
[轉]在jQuery1.5中使用deferred对象 - 拿着放大镜看Promise
http://www.cnblogs.com/sanshi/archive/2011/03/11/1981789.html 不錯的JS方面的文章 三生石上
拼多多成立技术顾问委员会，陆奇将领导相关工作
整理 | 琥珀出品 | AI科技大本营（公众号id：rgznai100）美国东部时间 3 月 13 日上午，拼多多（NASDAQ：PDD）公布了截止 2018 年 12 月 31 日的第四季度和全年年的未经审计财务业绩。拼多多创始人、C…
【linux】Valgrind工具集详解（一）：简介
一、Valgrind概述 Valgrind是用于构建动态分析工具的仪器框架。它附带了一组工具，每个工具都执行某种调试，分析或类似任务，可帮助您改进程序。Valgrind的架构采用模块化设计，因此可以轻松创建新工具，而不会干扰现有结…
An internal error occurred during: Launching xxx on WebLogic10.x.
An internal error occurred during: "Launching xxx on WebLogic10.x". java.lang.NullPointerException 蕃薯耀 2018年3月15日 http://www.cnblogs.com/fanshuyao/ 一、问题描述： Myeclipse 将项目部署web服务器报错： An internal error oc…
Android -- TextView与EditText 同步显示
Android -- TextView与EditText 同步显示文章分类:JavaEye方法一.利用View.OnKeyListener"同步"显示Java代码 EditText myEdit (EditText)findViewById(R.id.myEdit); TextView myText (TextView)findViewById(R.id.myText); myEdit.setOnKeyListener(new Edit…
【linux】Valgrind工具集详解（二）：入门
一、使用valgrind 1、安装 安装超级简单： sudo apt-get install valgrind 2、使用 运行valgrind -h可以查看详细使用方法，命令格式如下： valgrind [valgrind -h中的选项] 待测程序 [待测程序的命令行参数列表]最重要的选项是–tool决定运行哪种Valgrind工具。 例如，使…
Spring Cloud - Feign调用问题
2019独角兽企业重金招聘Python工程师标准>>> 这两天在改造微服务远程调用方法时，由之前的RestTemplate方式，改为FeignClient方式。 遇到一个及其恶心的问题。 直接上错误提示： 这里面，最重要的一条是： 这个…
开源的Blink和Spark3.0，谁将称霸大数据领域？
来源 | 大数据技术与架构（import_bigdata）作者 | 王知无，阿里巴巴高级大数据开发工程师，先后在京东、阿里等大型互联网公司从事大数据平台、实时计算和离线计算中间件和业务平台开发。2018和2019年是大数据领域蓬勃发展的两年&…
Redis 集群部署及踩过的坑
本文目标 要在单台机器上搭建Redis集群，方式是通过不同的TCP端口启动多个实例，然后组成集群，同时记录在搭建过程中踩过的坑。 安装准备 centos版本：6.7 redis版本：3.2.3 安装方式：源码安装 服务器ÿ…
【linux】Valgrind工具集详解（三）：打印信息说明
一、打印信息格式 Valgrind打印信息的格式如下，很容易和程序输出信息区分出来 == 进程ID ==Valgrind的打印信息二、打印到何处 1、打印到文件描述符中 主要是设置打印到终端上，默认情况下为2（stderr标准错误输出）。如果要想打印到其他文件描述符（例如编号9），则可以指…