当前位置: 首页 > news >正文

逆波兰表达式求值[中等]

优质博文:IT-BLOG-CN

一、题目

给你一个字符串数组tokens,表示一个根据 逆波兰表示法 表示的算术表达式。请你计算该表达式。返回一个表示表达式值的整数。

有效的算符为 ‘+’、‘-’、‘*’ 和 ‘/’ 。
每个操作数(运算对象)都可以是一个整数或者另一个表达式。
两个整数之间的除法总是 向零截断 。
表达式中不含除零运算。
输入是一个根据逆波兰表示法表示的算术表达式。
答案及所有中间计算结果可以用32位 整数表示。

示例 1:
输入:tokens = ["2","1","+","3","*"]
输出:9
解释:该算式转化为常见的中缀算术表达式为:((2 + 1) * 3) = 9

示例 2:
输入:tokens = ["4","13","5","/","+"]
输出:6
解释:该算式转化为常见的中缀算术表达式为:(4 + (13 / 5)) = 6

示例 3:
输入:tokens = ["10","6","9","3","+","-11","*","/","*","17","+","5","+"]
输出:22
解释:该算式转化为常见的中缀算术表达式为:
((10 * (6 / ((9 + 3) * -11))) + 17) + 5
= ((10 * (6 / (12 * -11))) + 17) + 5
= ((10 * (6 / -132)) + 17) + 5
= ((10 * 0) + 17) + 5
= (0 + 17) + 5
= 17 + 5
= 22

1 <= tokens.length <= 104
tokens[i]是一个算符(“+”、“-”、“*” 或 “/”),或是在范围[-200, 200]内的一个整数

逆波兰表达式由波兰的逻辑学家卢卡西维兹提出。逆波兰表达式的特点是:没有括号,运算符总是放在和它相关的操作数之后。因此,逆波兰表达式也称后缀表达式。

二、代码

【1】栈: 逆波兰表达式严格遵循「从左到右」的运算。计算逆波兰表达式的值时,使用一个栈存储操作数,从左到右遍历逆波兰表达式,进行如下操作:如果遇到操作数,则将操作数入栈;如果遇到运算符,则将两个操作数出栈,其中先出栈的是右操作数,后出栈的是左操作数,使用运算符对两个操作数进行运算,将运算得到的新操作数入栈。整个逆波兰表达式遍历完毕之后,栈内只有一个元素,该元素即为逆波兰表达式的值。

class Solution {public int evalRPN(String[] tokens) {Deque<Integer> stack = new LinkedList<Integer>();int n = tokens.length;for (int i = 0; i < n; i++) {String token = tokens[i];if (isNumber(token)) {stack.push(Integer.parseInt(token));} else {int num2 = stack.pop();int num1 = stack.pop();switch (token) {case "+":stack.push(num1 + num2);break;case "-":stack.push(num1 - num2);break;case "*":stack.push(num1 * num2);break;case "/":stack.push(num1 / num2);break;default:}}}return stack.pop();}public boolean isNumber(String token) {return !("+".equals(token) || "-".equals(token) || "*".equals(token) || "/".equals(token));}
}

时间复杂度: O(n),其中n是数组tokens的长度。需要遍历数组tokens一次,计算逆波兰表达式的值。
空间复杂度: O(n),其中n是数组tokens的长度。使用栈存储计算过程中的数,栈内元素个数不会超过逆波兰表达式的长度。

【2】数组模拟栈: 方法一使用栈存储操作数。也可以使用一个数组模拟栈操作。如果使用数组代替栈,则需要预先定义数组的长度。对于长度为n的逆波兰表达式,显然栈内元素个数不会超过n,但是将数组的长度定义为n仍然超过了栈内元素个数的上界。那么,栈内元素最多可能有多少个?

对于一个有效的逆波兰表达式,其长度n一定是奇数,且操作数的个数一定比运算符的个数多1个,即包含(n+1)/2个操作数和(n−1)/2个运算符。考虑遇到操作数和运算符时,栈内元素个数分别会如何变化:
1、如果遇到操作数,则将操作数入栈,因此栈内元素增加1个;
2、如果遇到运算符,则将两个操作数出栈,然后将一个新操作数入栈,因此栈内元素先减少2个再增加1个,结果是栈内元素减少1个。

由此可以得到操作数和运算符与栈内元素个数变化的关系:遇到操作数时,栈内元素增加1个;遇到运算符时,栈内元素减少1个。

最坏情况下,(n+1)/2个操作数都在表达式的前面,(n−1)/2个运算符都在表达式的后面,此时栈内元素最多为(n+1)/2个。在其余情况下,栈内元素总是少于(n+1)/2个。因此,在任何情况下,栈内元素最多可能有(n+1)/2个,将数组的长度定义为(n+1)/2即可。

具体实现方面,创建数组stack模拟栈,数组下标0的位置对应栈底,定义index表示栈顶元素的下标位置,初始时栈为空,index=−1。当遇到操作数和运算符时,进行如下操作:
1、如果遇到操作数,则将index的值加1,然后将操作数赋给stack[index]
2、如果遇到运算符,则将index的值减1,此时stack[index]stack[index+1]的元素分别是左操作数和右操作数,使用运算符对两个操作数进行运算,将运算得到的新操作数赋给stack[index]

整个逆波兰表达式遍历完毕之后,栈内只有一个元素,因此index=0,此时stack[index]即为逆波兰表达式的值。

class Solution {public int evalRPN(String[] tokens) {int n = tokens.length;int[] stack = new int[(n + 1) / 2];int index = -1;for (int i = 0; i < n; i++) {String token = tokens[i];switch (token) {case "+":index--;stack[index] += stack[index + 1];break;case "-":index--;stack[index] -= stack[index + 1];break;case "*":index--;stack[index] *= stack[index + 1];break;case "/":index--;stack[index] /= stack[index + 1];break;default:index++;stack[index] = Integer.parseInt(token);}}return stack[index];}
}

时间复杂度: O(n),其中n是数组tokens的长度。需要遍历数组tokens一次,计算逆波兰表达式的值。
空间复杂度: O(n),其中n是数组tokens的长度。需要创建长度为(n+1)/2的数组模拟栈操作。

相关文章:

逆波兰表达式求值[中等]

优质博文&#xff1a;IT-BLOG-CN 一、题目 给你一个字符串数组tokens&#xff0c;表示一个根据 逆波兰表示法 表示的算术表达式。请你计算该表达式。返回一个表示表达式值的整数。 有效的算符为 ‘’、‘-’、‘*’ 和 ‘/’ 。 每个操作数&#xff08;运算对象&#xff09;都…...

Oracle连接和使用

5. Oracle连接和使用 5.1. sqlplus sqlplus作为甲骨文公司提供的一款本族工具产品,有着悠久的历史和积淀,它几乎伴随着Oracle数据库产生至今的整个生命周期,而且,还会继续和Oracle数据库产品相伴一直发展下去。该工具看似简单灵活的背后,却为广大用户使用Oracle数据库提…...

redis单线程为什么这么快

redis单线程为什么这么快 redis是使用的单线程来进行操作的&#xff0c;因为所有的数据都是在内存中的&#xff0c;内存操作特别快。而且单线程避免了多线程切换性能损耗问题 单线程如何处理并发客户端连接&#xff1f; redis利用epoll来实现IO多路复用&#xff0c;将连接信息和…...

工业机器视觉megauging(向光有光)使用说明书(五,轻量级的visionpro)

这个说明主要介绍抓线功能。 第一步&#xff0c;添加线工具&#xff0c;鼠标双击工具箱“抓线”&#xff0c;出现如下界面&#xff1a; 第二步&#xff0c;我们拉一条&#xff0c;“九点标定”到“抓线1”的线&#xff0c;和visionpro操作一样&#xff1a; 第三步&#xff0c;…...

【LittleXi】2023年广东工业大学腾讯杯新生程序设计竞赛

文章目录 【LittleXi】2023年广东工业大学腾讯杯新生程序设计竞赛A.星期几考试&#xff1f;C.信件D、乘除法E、不知道叫什么名字F.我要学会盾反&#xff01;G.闪闪发光心动不已&#xff01;H.不想想背景的gcdI.uu爱玩飞行棋J.火柴人小游戏K .有趣的BOSS 【LittleXi】2023年广东…...

【C语言:数据在内存中的存储】

文章目录 1.整数在内存中的存储1.1整数在内存中的存储1.2整型提升 2.大小端字节序2.1什么是大小端2.2为什么有大小端之分 3.整数在内存中的存储相关题目题目一题目二题目三题目四题目五题目六题目七 4.浮点数在内存中的存储4.1浮点数存的过程4.2浮点数取得过程 在这之前呢&…...

每日一练:阿姆斯特朗数

如果一个 n 位正整数等于其各位数字的 n 次方之和&#xff0c;则称该数为阿姆斯特朗数。 例如 1^3 5^3 3^3 153。 1000 以内的阿姆斯特朗数&#xff1a; 1, 2, 3, 4, 5, 6, 7, 8, 9, 153, 370, 371, 407。...

fatal: remote error: upload-pack: not our ref (未解决问题)

PX4使用 git submodule update --init --recursive报错 fatal: remote error: upload-pack: not our ref解决办法参考&#xff1a;https://stackoverflow.com/questions/61163082/why-does-git-submodule-update-fail-with-fatal-remote-error-upload-pack-not-o 感觉就是清…...

Python 3 使用 read()、readline()、readlines() 函数 读取文件

1 样例文件 example.txt 春晓 孟浩然〔唐代〕 春眠不觉晓&#xff0c;处处闻啼鸟。 夜来风雨声&#xff0c;花落知多少。 2 分别使用 read()、readline()、readlines() 函数 2.1 # read() -------- 一次性读取所有文本&#xff0c;以字符串的形式返回结果。 # read() ----…...

勒索解密后oracle无法启动故障处理----惜分飞

客户linux平台被勒索病毒加密,其中有oracle数据库.客户联系黑客进行解密【勒索解密oracle失败】,但是数据库无法正常启动,dbv检查数据库文件报错 [oraclehisdb ~]$ dbv filesystem01.dbf DBVERIFY: Release 11.2.0.1.0 - Production on 星期一 11月 27 21:49:17 2023 Copyrig…...

Leetcode144. 二叉树的前序遍历-C语言

文章目录 题目介绍题目分析解题思路1.创建一个数组来储存二叉树节点的值2.根据二叉树的大小来开辟数组的大小3.边前序遍历边向创建的数组中存入二叉树节点的值 完整代码 题目介绍 题目分析 题目要求我们输出二叉树按前序遍历排列的每个节点的值。 解题思路 1.创建一个数组来…...

dmesg命令在软件测试中的实际应用

简介&#xff1a;当你想要了解 Linux 系统在启动时究竟发生了什么&#xff1f;或者当硬件设备不工作时&#xff0c;如何进行调试&#xff1f;这就是 dmesg 命令的用武之地。本文将介绍 dmesg 的基本功能&#xff0c;并深入探讨其在软件测试中的实际应用。 历史攻略&#xff1a…...

【渗透】记录阿里云CentOS一次ddos攻击

文章目录 发现防御 发现 防御 流量清洗 使用高防...

前端面试提问(3)

1、js两个数相加会不会丢精度&#xff1f; 可能会遇到精度丢失的问题。JavaScript 使用的是 IEEE 754 浮点数标准&#xff0c;即一种二进制表示法&#xff0c;有时不能准确地表示十进制小数。如果你需要进行精确的十进制数值计算&#xff0c;可以使用一些处理精确数值的库&…...

fl studio21.2最新汉化中文完整版网盘下载

fl studio 21中文版是Image-Line公司继20版本之后更新的水果音乐制作软件&#xff0c;很多用户不太理解&#xff0c;为什么新版本不叫fl studio 21或fl studio2024&#xff0c;非得直接跳到21.2版本&#xff0c;其实该版本是为了纪念该公司22周年&#xff0c;所以该版本也是推出…...

差分数组相关知识点以及刷题

差分数组 差分数组是什么&#xff1f; **举例&#xff1a;**对于数组考虑数组 a[1,3,3,5,8]&#xff0c;对其中的相邻元素两两作差&#xff08;右边减左边&#xff09;&#xff0c;得到数组 [2,0,2,3]。然后在开头补上 a[0]&#xff0c;得到差分数组&#xff1a; ​ d[1,2,0…...

使用 DMA 在 FPGA 中的 HDL 和嵌入式 C 之间传输数据

使用 DMA 在 FPGA 中的 HDL 和嵌入式 C 之间传输数据 该项目介绍了如何在 PL 中的 HDL 与 FPGA 中的处理器上运行的嵌入式 C 之间传输数据的基本结构。 介绍 鉴于机器学习和人工智能等应用的 FPGA 设计中硬件加速的兴起&#xff0c;现在是剥开几层“云雾”并讨论 HDL 之间来回传…...

uniapp地图基本使用及解决添加markers不生效问题?

uniapp地图使用 App端 通过 nvue 页面实现地图 文章目录 uniapp地图使用效果图templatejs添加 marker使用地图查看位置移到到当前位置 效果图 template <template><view class"mapWrap"><!-- #ifdef APP-NVUE --><map class"map-containe…...

使用系统ProgressBar实现三色进度条

使用系统ProgressBar实现如图三色进度条&#xff1a; //布局中<ProgressBarandroid:layout_width"0dp"android:layout_height"8dp"android:layout_marginLeft"16dp"app:layout_constraintBottom_toBottomOf"id/photo"app:layout_c…...

Vue3中的组合式API的详细教程和介绍

文章目录 前言介绍组合式 API 基础setup 组件选项 带 ref 的响应式变量生命周期钩子注册内部 setupwatch 响应式更改独立的 computed 属性后言 前言 hello world欢迎来到前端的新世界 &#x1f61c;当前文章系列专栏&#xff1a;vue.js &#x1f431;‍&#x1f453;博主在前端…...

什么是库存周转?如何用进销存系统提高库存周转率?

你可能听说过这样一句话&#xff1a; “利润不是赚出来的&#xff0c;是管出来的。” 尤其是在制造业、批发零售、电商这类“货堆成山”的行业&#xff0c;很多企业看着销售不错&#xff0c;账上却没钱、利润也不见了&#xff0c;一翻库存才发现&#xff1a; 一堆卖不动的旧货…...

【开发技术】.Net使用FFmpeg视频特定帧上绘制内容

目录 一、目的 二、解决方案 2.1 什么是FFmpeg 2.2 FFmpeg主要功能 2.3 使用Xabe.FFmpeg调用FFmpeg功能 2.4 使用 FFmpeg 的 drawbox 滤镜来绘制 ROI 三、总结 一、目的 当前市场上有很多目标检测智能识别的相关算法&#xff0c;当前调用一个医疗行业的AI识别算法后返回…...

初学 pytest 记录

安装 pip install pytest用例可以是函数也可以是类中的方法 def test_func():print()class TestAdd: # def __init__(self): 在 pytest 中不可以使用__init__方法 # self.cc 12345 pytest.mark.api def test_str(self):res add(1, 2)assert res 12def test_int(self):r…...

React---day11

14.4 react-redux第三方库 提供connect、thunk之类的函数 以获取一个banner数据为例子 store&#xff1a; 我们在使用异步的时候理应是要使用中间件的&#xff0c;但是configureStore 已经自动集成了 redux-thunk&#xff0c;注意action里面要返回函数 import { configureS…...

面向无人机海岸带生态系统监测的语义分割基准数据集

描述&#xff1a;海岸带生态系统的监测是维护生态平衡和可持续发展的重要任务。语义分割技术在遥感影像中的应用为海岸带生态系统的精准监测提供了有效手段。然而&#xff0c;目前该领域仍面临一个挑战&#xff0c;即缺乏公开的专门面向海岸带生态系统的语义分割基准数据集。受…...

DingDing机器人群消息推送

文章目录 1 新建机器人2 API文档说明3 代码编写 1 新建机器人 点击群设置 下滑到群管理的机器人&#xff0c;点击进入 添加机器人 选择自定义Webhook服务 点击添加 设置安全设置&#xff0c;详见说明文档 成功后&#xff0c;记录Webhook 2 API文档说明 点击设置说明 查看自…...

windows系统MySQL安装文档

概览&#xff1a;本文讨论了MySQL的安装、使用过程中涉及的解压、配置、初始化、注册服务、启动、修改密码、登录、退出以及卸载等相关内容&#xff0c;为学习者提供全面的操作指导。关键要点包括&#xff1a; 解压 &#xff1a;下载完成后解压压缩包&#xff0c;得到MySQL 8.…...

在 Spring Boot 项目里,MYSQL中json类型字段使用

前言&#xff1a; 因为程序特殊需求导致&#xff0c;需要mysql数据库存储json类型数据&#xff0c;因此记录一下使用流程 1.java实体中新增字段 private List<User> users 2.增加mybatis-plus注解 TableField(typeHandler FastjsonTypeHandler.class) private Lis…...

沙箱虚拟化技术虚拟机容器之间的关系详解

问题 沙箱、虚拟化、容器三者分开一一介绍的话我知道他们各自都是什么东西&#xff0c;但是如果把三者放在一起&#xff0c;它们之间到底什么关系&#xff1f;又有什么联系呢&#xff1f;我不是很明白&#xff01;&#xff01;&#xff01; 就比如说&#xff1a; 沙箱&#…...

医疗AI模型可解释性编程研究:基于SHAP、LIME与Anchor

1 医疗树模型与可解释人工智能基础 医疗领域的人工智能应用正迅速从理论研究转向临床实践,在这一过程中,模型可解释性已成为确保AI系统被医疗专业人员接受和信任的关键因素。基于树模型的集成算法(如RandomForest、XGBoost、LightGBM)因其卓越的预测性能和相对良好的解释性…...