后缀表达式中缀表达式转后缀表达式
后缀表达式的计算机求值
计算规则
从左至右扫描表达式,遇到数字时,将数字压入堆栈,遇到运算符时,弹出栈顶的两个数,用运算符对它们做相应的计算(次顶元素 和 栈顶元素),并将结果入栈;重复上述过程直到表达式最右端,最后运算得出的值即为表达式的结果。
举例分析
例如: (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…...
【Axure高保真原型】引导弹窗
今天和大家中分享引导弹窗的原型模板,载入页面后,会显示引导弹窗,适用于引导用户使用页面,点击完成后,会显示下一个引导弹窗,直至最后一个引导弹窗完成后进入首页。具体效果可以点击下方视频观看或打开下方…...
【JVM】- 内存结构
引言 JVM:Java Virtual Machine 定义:Java虚拟机,Java二进制字节码的运行环境好处: 一次编写,到处运行自动内存管理,垃圾回收的功能数组下标越界检查(会抛异常,不会覆盖到其他代码…...
如何为服务器生成TLS证书
TLS(Transport Layer Security)证书是确保网络通信安全的重要手段,它通过加密技术保护传输的数据不被窃听和篡改。在服务器上配置TLS证书,可以使用户通过HTTPS协议安全地访问您的网站。本文将详细介绍如何在服务器上生成一个TLS证…...
MySQL 8.0 OCP 英文题库解析(十三)
Oracle 为庆祝 MySQL 30 周年,截止到 2025.07.31 之前。所有人均可以免费考取原价245美元的MySQL OCP 认证。 从今天开始,将英文题库免费公布出来,并进行解析,帮助大家在一个月之内轻松通过OCP认证。 本期公布试题111~120 试题1…...
图表类系列各种样式PPT模版分享
图标图表系列PPT模版,柱状图PPT模版,线状图PPT模版,折线图PPT模版,饼状图PPT模版,雷达图PPT模版,树状图PPT模版 图表类系列各种样式PPT模版分享:图表系列PPT模板https://pan.quark.cn/s/20d40aa…...
【HarmonyOS 5 开发速记】如何获取用户信息(头像/昵称/手机号)
1.获取 authorizationCode: 2.利用 authorizationCode 获取 accessToken:文档中心 3.获取手机:文档中心 4.获取昵称头像:文档中心 首先创建 request 若要获取手机号,scope必填 phone,permissions 必填 …...
蓝桥杯3498 01串的熵
问题描述 对于一个长度为 23333333的 01 串, 如果其信息熵为 11625907.5798, 且 0 出现次数比 1 少, 那么这个 01 串中 0 出现了多少次? #include<iostream> #include<cmath> using namespace std;int n 23333333;int main() {//枚举 0 出现的次数//因…...
ip子接口配置及删除
配置永久生效的子接口,2个IP 都可以登录你这一台服务器。重启不失效。 永久的 [应用] vi /etc/sysconfig/network-scripts/ifcfg-eth0修改文件内内容 TYPE"Ethernet" BOOTPROTO"none" NAME"eth0" DEVICE"eth0" ONBOOT&q…...
让回归模型不再被异常值“带跑偏“,MSE和Cauchy损失函数在噪声数据环境下的实战对比
在机器学习的回归分析中,损失函数的选择对模型性能具有决定性影响。均方误差(MSE)作为经典的损失函数,在处理干净数据时表现优异,但在面对包含异常值的噪声数据时,其对大误差的二次惩罚机制往往导致模型参数…...
CVE-2020-17519源码分析与漏洞复现(Flink 任意文件读取)
漏洞概览 漏洞名称:Apache Flink REST API 任意文件读取漏洞CVE编号:CVE-2020-17519CVSS评分:7.5影响版本:Apache Flink 1.11.0、1.11.1、1.11.2修复版本:≥ 1.11.3 或 ≥ 1.12.0漏洞类型:路径遍历&#x…...
