后缀表达式中缀表达式转后缀表达式
后缀表达式的计算机求值
计算规则
从左至右扫描表达式,遇到数字时,将数字压入堆栈,遇到运算符时,弹出栈顶的两个数,用运算符对它们做相应的计算(次顶元素 和 栈顶元素),并将结果入栈;重复上述过程直到表达式最右端,最后运算得出的值即为表达式的结果。
举例分析
例如: (3+4)*5-6 对应的后缀表达式就是 3 4 + 5 * 6 - , 针对后缀表达式求值步骤如下:
- 从左至右扫描,将3和4压入堆栈;
- 遇到+运算符,因此弹出4和3(4为栈顶元素,3为次顶元素),计算出3+4的值,得7,再将7入栈;
- 将5入栈;
- 接下来是*运算符,因此弹出5和7,计算出7*5=35,将35入栈;
- 将6入栈;
- 最后是-运算符,计算出35-6的值,即29,由此得出最终结果
扫描元素 | s1(栈底->栈顶) | 说明 |
3 | 3 | 数字,入栈 |
4 | 3 4 | 数字,入栈 |
+ | 7 | 运算符,弹出栈顶的两个数,用运算符对它们做相应的计算(顺序:次顶元素 和 栈顶元素),并将结果入栈 |
5 | 7 5 | 数字,入栈 |
* | 35 | 运算符,弹出栈顶的两个数,用运算符对它们做相应的计算(顺序:次顶元素 和 栈顶元素),并将结果入栈 |
6 | 35 6 | 数字,入栈 |
- | 29 | 运算符,弹出栈顶的两个数,用运算符对它们做相应的计算(顺序:次顶元素 和 栈顶元素),并将结果入栈 |
29 | 最终结果保存在操作数栈中 |
代码实现
import java.util.Stack;/*** @Author: * @Create: 2024-10-01 10:36* @Description:* (3+4)×5-6 --> 3 4 + 5 × 6 -*/
public class 后缀表达式 {public static void main(String[] args) {String expression = "3 4 + 5 * 6 - ";String[] str = expression.split(" ");Stack<Integer> numStack = new Stack<>();int res = 0;for (String s : str) {if (s.matches("\\d+")) {numStack.push(Integer.parseInt(s));} else {Integer num1 = numStack.pop();Integer num2 = numStack.pop();switch (s) {case "+":res = num2 + num1;break;case "-":res = num2 - num1;break;case "*":res = num2 * num1;break;case "/":res = num2 / num1;break;default:throw new ArithmeticException("运算符有误");}numStack.push(res);}}System.out.println(res);}
}
逆波兰计算器
逆波兰表达式(后缀表达式)支持小括号和多位数整数计算,后缀表达式适合计算机进行运算,但是人却不太容易写出来,尤其是表达式很长的情况下,因此在开发中,我们需要将中缀表达式转成后缀表达式。
中缀表达式转后缀表达式规则
具体步骤如下:
- 初始化两个栈:存储中间结果的栈s1和运算符栈s2;定义-+优先级为1,*/优先级为2,其他0
- 从左至右扫描中缀表达式;
- 遇到操作数时,将其压s1;
- 遇到运算符时,比较其与s2栈顶运算符的优先级:
- 如果s2不为空 && 优先级<=栈顶运算符(优先级的定义判定了栈顶运算符为左括号“(”的情况,所以不用在考虑遇到做括号的情况),将s2栈顶的运算符弹出并压入到s1中,循环判断,再次转到(4-1)与s2中新的栈顶运算符相比较;
- 出了循环,将运算符压入s2;
- 遇到括号时:
- 如果是左括号“(”,则直接压入s2
- 如果是右括号“)”,则依次弹出s2栈顶的运算符,并压入s1,直到遇到左括号为止,此时将这一对括号丢弃
- 重复步骤3至5,直到表达式的最右边
- 将s2中剩余的运算符依次弹出并压入s1
- 依次弹出s1中的元素并输出,结果的逆序即为中缀表达式对应的后缀表达式
举例分析
将中缀表达式 “1+((2+3)*4)-5” 转换为后缀表达式 "1 2 3 + 4 * + 5 –" 的过程如下:
扫描元素 | s1(栈底->栈顶) | s2(栈底->栈顶) | 说明 |
1 | 1 | 操作数,直接入栈s1 | |
+ | 1 | + | s2为空,入栈s2 |
( | 1 | + ( | 左括号,直接入栈s2 |
( | 1 | + ( ( | 左括号,直接入栈s2 |
2 | 1 2 | + ( ( | 操作数,直接入栈s1 |
+ | 1 2 | + ( ( + | s2栈顶运算符为左括号,入栈s2 |
3 | 1 2 3 | + ( ( + | 操作数,直接入栈s1 |
) | 1 2 3 + | + ( | 右括号,依次弹出s2栈顶的运算符,压入s1,直到遇到左括号为止,此时将这一对括号丢弃 |
* | 1 2 3 + | + ( * | s2栈顶运算符为左括号,入栈s2 |
4 | 1 2 3 + 4 | + ( * | 操作数,直接入栈s1 |
) | 1 2 3 + 4 * | + | 右括号,依次弹出s2栈顶的运算符,压入s1,直到遇到左括号为止,此时将这一对括号丢弃 |
- | 1 2 3 + 4 * + | - | -优先级不比+高,将+弹出并压入到s1中,此时s2为空,-入栈s2 |
5 | 1 2 3 + 4 * + 5 | - | 操作数,直接入栈s1 |
1 2 3 + 4 * + 5 - | s2中剩余的运算符依次弹出并压入s1,结果为s1出栈的逆序 |
代码实现
import java.util.ArrayList;
import java.util.Stack;/*** @Author: * @Create: 2024-10-01 11:58* @Description: 1+((2+3)*4)-5 --> 1 2 3 + 4 * + 5 –*/
public class 中缀转后缀 {public static void main(String[] args) {String infix = "1+((2+3)*4)-5";ArrayList<String> suffixList = new ArrayList<>();Stack<String> oper = new Stack<>();int len = infix.length();for (int i = 0; i < len; i++) {char c = infix.charAt(i);if (Character.isDigit(c)) {int j = i;while (j < len && Character.isDigit(infix.charAt(j))) {j++;}suffixList.add(infix.substring(i, j));i = j - 1;} else if (c == '(') {oper.push(c + "");} else if (c == ')') {while (!oper.isEmpty() && !oper.peek().equals("(")) {suffixList.add(oper.pop());}oper.pop(); // 弹出左括号} else { // 运算符while (!oper.isEmpty() && getPriority(c + "") <= getPriority(oper.peek())) {suffixList.add(oper.pop());}oper.push(c + "");}}// 弹出剩下运算符while (!oper.isEmpty()) {suffixList.add(oper.pop());}System.out.println(suffixList);}private static int getPriority(String operator) {if ("*".equals(operator) || "/".equals(operator)) return 2;else if ("+".equals(operator) || "-".equals(operator)) return 1;else return 0;}
}
逆波兰计算器代码实现
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
import java.util.Stack;/*** @Author: * @Create: 2024-10-01 13:51* @Description:*/
public class 逆波兰计算器 {public static void main(String[] args) {Scanner in = new Scanner(System.in);String infix = in.nextLine().replace(" ", "");// 转化后缀表达式List<String> suffix = changeToSuffix(infix);// 计算后缀表达式int res = calculateSuffix(suffix);System.out.println(res);}private static int calculateSuffix(List<String> suffix) {Stack<Integer> nums = new Stack<>();int res = 0;for (String s : suffix) {if (s.matches("\\d+")) {nums.push(Integer.parseInt(s));} else {Integer num1 = nums.pop();Integer num2 = nums.pop();switch (s) {case "*":res = num2 * num1;break;case "/":res = num2 / num1;break;case "+":res = num2 + num1;break;case "-":res = num2 - num1;break;default:throw new ArithmeticException("运算符有误");}nums.push(res);}}return res;}private static List<String> changeToSuffix(String infix) {Stack<String> oper = new Stack<>();ArrayList<String> res = new ArrayList<>();int len = infix.length();for (int i = 0; i < len; i++) {char c = infix.charAt(i);if (Character.isDigit(c)) {int j = i;while (j < len && Character.isDigit(infix.charAt(j))) {j++;}res.add(infix.substring(i, j));i = --j;} else if (c == '(') {oper.push(c + "");} else if (c == ')') {while (!oper.isEmpty() && !"(".equals(oper.peek())) {res.add(oper.pop());}oper.pop();} else {while (!oper.isEmpty() && getPriority(c + "") <= getPriority(oper.peek())) {res.add(oper.pop());}oper.push(c + "");}}while (!oper.isEmpty()) {res.add(oper.pop());}return res;}private static int getPriority(String operator) {if ("*".equals(operator) || "/".equals(operator)) return 2;else if ("+".equals(operator) || "-".equals(operator)) return 1;else return 0;}
}
相关文章:
后缀表达式中缀表达式转后缀表达式
后缀表达式的计算机求值 计算规则 从左至右扫描表达式,遇到数字时,将数字压入堆栈,遇到运算符时,弹出栈顶的两个数,用运算符对它们做相应的计算(次顶元素 和 栈顶元素),并将结果入…...

Qemu开发ARM篇-7、uboot以及系统网络连接及配置
文章目录 1、uboot及linux版本网络设置1、宿主机虚拟网卡创建2、uboot使用tap0网卡3、启动测试 2、访问外网设置 在上一篇Qemu开发ARM篇-6、emmc/SD卡AB分区镜像制作并通过uboot进行挂载启动中,我们制作了AB分区系统镜像,并成功通过uboot加载kernel以及d…...
两数相加leetcode
第一个是测试用例代码,测试的是两个带头的逆序链表相加,并且有反转操作 但是题目要求的是不带头链表直接相加,不需要逆转,输出结果也是逆序的, 题解放在第二个代码中 #include<stdio.h> #include<stdlib.h…...

C0004.Qt中QComboBox设置下拉列表样式后,下拉列表样式无效的解决办法
问题描述 我们平时在使用Qt Creator对控件QComboBox的样式进行设置后,在运行程序启动界面时,发现设置的样式无效,效果如下: /* 设置下拉菜单框的样式 */ QComboBox QAbstractItemView {border: 1px solid rgb(161,161,161); /* …...

AI 对话工具汇总
🐣个人主页 可惜已不在 🐤这篇在这个专栏AI_可惜已不在的博客-CSDN博客 🐥有用的话就留下一个三连吧😼 目录 前言: 正文: 前言: 在科技飞速发展的时代,AI 对话正逐渐成为我们获取信息、交流思想的新方式。它以强…...

面试题05.08绘制直线问题详解(考察点为位运算符)
目录 一题目: 二详细思路汇总: 三代码解答(带注释版): 一题目: leetcode原题链接:. - 力扣(LeetCode) 二详细思路汇总: 这里先剧透一下简单版思路哦&…...

埃及 Explained
古埃及,位于尼罗河畔的神秘文明,曾在北非的荒漠中繁荣昌盛。这个充满谜团的王国凭借其宏伟的成就和神秘的文化,数百年来吸引了无数人的好奇心。 埃及人创造了复杂的象形文字,建造了像吉萨大金字塔这样宏伟的建筑,并通…...

【Linux】第一个小程序——进度条实现
🔥 个人主页:大耳朵土土垚 🔥 所属专栏:Linux系统编程 这里将会不定期更新有关Linux的内容,欢迎大家点赞,收藏,评论🥳🥳🎉🎉🎉 文章目…...

如何确定光纤用几芯 用光纤与网线区别在哪里
光纤用几芯? 光纤芯数,主要和光纤连接的设备接口和设备的通信方式有关。一般来说,光纤中光芯的数量,为设备接口总数乘以2后,再加上10%~20%的备用数量,而如果设备的通信方式有设备多…...
使用Chrome浏览器时打开网页如何禁用缓存
缓存是浏览器用于临时存储网页资源的一种机制,可以提高网页加载速度和减轻服务器负载。 然而,有时候我们需要阻止缓存中的Chrome浏览器,以便获取最新的网页内容。以下是一些方法可以实现这个目标: 1、强制刷新页面:在C…...

zabbix7.0创建自定义模板的案例详解(以监控httpd服务为例)
前言 服务端配置 链接: rocky9.2部署zabbix服务端的详细过程 环境 主机ip应用zabbix-server192.168.10.11zabbix本体zabbix-client192.168.10.12zabbix-agent zabbix-server(服务端已配置) 创建模板 模板组直接写一个新的,不用选择 通过名称查找模板…...
从零开始Ubuntu24.04上Docker构建自动化部署(五)Docker安装jenkins
安装jenkins 下载 sudo docker pull jenkins/jenkins:lts docker-compose启动 jenkins: image: jenkins/jenkins:lts container_name: compose_jenkins user: root restart: always ports: - 28080:8080 volumes: - /home/jenkins_home/:/var/jenkins_home - /usr/local/bin/d…...
【JS】访问器成员
前言 如下例,有一商品对象,其中属性分别为单价和数量以及一个用于计算总价的方法,需要通过 product.getTotal() 获得总价,也可以使用访问器成员getter控制属性读写逻辑,通过 product.total 的方式获取总价,…...

五子棋双人对战项目(3)——匹配模块
目录 一、分析需求 二、约定前后端交互接口 匹配请求: 匹配响应: 三、实现游戏大厅页面(前端代码) game_hall.html: common.css: game_hall.css: 四、实现后端代码 WebSocketConfig …...
开源软件简介
一、开源运动的发起 近几十年,软件已经称为战略性的社会资源。各大软件供应商传统的对外封锁源代码的运营模式虽说有积极的一面,比如可以维护开发商的利益,使其可以持续地维护进一步开发的能力,以及可以保护软件商及客户的私密信息…...

Bruno:拥有 11.2k star 的免费开源 API 测试工具
Github 开源地址: https://github.com/usebruno/bruno 官网地址: https://www.usebruno.com/ 下载地址: https://www.usebruno.com/downloads 使用文档: https://docs.usebruno.com/ Bruno 是一款全新且创新的 API 客户端&…...

C动态内存管理
前言:不知不觉又过去了很长的一段时间。今天对C语言中的动态内存管理进行一个系统性的总结。 1 为什么要有动态内存分配 在C语言中,使用int,float,double,short等数据内置类型以及数组不是也可以开辟内存空间吗&…...

系列二、案例实操
一、创建表空间 1.1、概述 在Oracle数据库中,表空间是一个逻辑存储单位,它是Oracle数据库中存储数据的地方。 1.2、超级管理员登录 sqlplus / as sysdba 1.3、创建表空间 create tablespace water_boss datafile C:\Programs\oracle11g\oradata\orcl\…...

Python编码系列—Python状态模式:轻松管理对象状态的变化
🌟🌟 欢迎来到我的技术小筑,一个专为技术探索者打造的交流空间。在这里,我们不仅分享代码的智慧,还探讨技术的深度与广度。无论您是资深开发者还是技术新手,这里都有一片属于您的天空。让我们在知识的海洋中…...

卸载WSL(Ubuntu),卸载linux
禁用 WSL 功能 打开 Windows 功能: 按下 Windows R 打开运行对话框,输入 optionalfeatures,然后按回车。 禁用 WSL: 在弹出的 Windows 功能窗口中,找到 适用于 Linux 的 Windows 子系统(Windows Subsystem…...

阿里云ACP云计算备考笔记 (5)——弹性伸缩
目录 第一章 概述 第二章 弹性伸缩简介 1、弹性伸缩 2、垂直伸缩 3、优势 4、应用场景 ① 无规律的业务量波动 ② 有规律的业务量波动 ③ 无明显业务量波动 ④ 混合型业务 ⑤ 消息通知 ⑥ 生命周期挂钩 ⑦ 自定义方式 ⑧ 滚的升级 5、使用限制 第三章 主要定义 …...
深入浅出:JavaScript 中的 `window.crypto.getRandomValues()` 方法
深入浅出:JavaScript 中的 window.crypto.getRandomValues() 方法 在现代 Web 开发中,随机数的生成看似简单,却隐藏着许多玄机。无论是生成密码、加密密钥,还是创建安全令牌,随机数的质量直接关系到系统的安全性。Jav…...
【位运算】消失的两个数字(hard)
消失的两个数字(hard) 题⽬描述:解法(位运算):Java 算法代码:更简便代码 题⽬链接:⾯试题 17.19. 消失的两个数字 题⽬描述: 给定⼀个数组,包含从 1 到 N 所有…...
电脑插入多块移动硬盘后经常出现卡顿和蓝屏
当电脑在插入多块移动硬盘后频繁出现卡顿和蓝屏问题时,可能涉及硬件资源冲突、驱动兼容性、供电不足或系统设置等多方面原因。以下是逐步排查和解决方案: 1. 检查电源供电问题 问题原因:多块移动硬盘同时运行可能导致USB接口供电不足&#x…...

页面渲染流程与性能优化
页面渲染流程与性能优化详解(完整版) 一、现代浏览器渲染流程(详细说明) 1. 构建DOM树 浏览器接收到HTML文档后,会逐步解析并构建DOM(Document Object Model)树。具体过程如下: (…...

P3 QT项目----记事本(3.8)
3.8 记事本项目总结 项目源码 1.main.cpp #include "widget.h" #include <QApplication> int main(int argc, char *argv[]) {QApplication a(argc, argv);Widget w;w.show();return a.exec(); } 2.widget.cpp #include "widget.h" #include &q…...
Java入门学习详细版(一)
大家好,Java 学习是一个系统学习的过程,核心原则就是“理论 实践 坚持”,并且需循序渐进,不可过于着急,本篇文章推出的这份详细入门学习资料将带大家从零基础开始,逐步掌握 Java 的核心概念和编程技能。 …...
汇编常见指令
汇编常见指令 一、数据传送指令 指令功能示例说明MOV数据传送MOV EAX, 10将立即数 10 送入 EAXMOV [EBX], EAX将 EAX 值存入 EBX 指向的内存LEA加载有效地址LEA EAX, [EBX4]将 EBX4 的地址存入 EAX(不访问内存)XCHG交换数据XCHG EAX, EBX交换 EAX 和 EB…...

在WSL2的Ubuntu镜像中安装Docker
Docker官网链接: https://docs.docker.com/engine/install/ubuntu/ 1、运行以下命令卸载所有冲突的软件包: for pkg in docker.io docker-doc docker-compose docker-compose-v2 podman-docker containerd runc; do sudo apt-get remove $pkg; done2、设置Docker…...

如何理解 IP 数据报中的 TTL?
目录 前言理解 前言 面试灵魂一问:说说对 IP 数据报中 TTL 的理解?我们都知道,IP 数据报由首部和数据两部分组成,首部又分为两部分:固定部分和可变部分,共占 20 字节,而即将讨论的 TTL 就位于首…...