逆波兰表达式求值[中等]
优质博文: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的数组模拟栈操作。
相关文章:
逆波兰表达式求值[中等]
优质博文:IT-BLOG-CN 一、题目 给你一个字符串数组tokens,表示一个根据 逆波兰表示法 表示的算术表达式。请你计算该表达式。返回一个表示表达式值的整数。 有效的算符为 ‘’、‘-’、‘*’ 和 ‘/’ 。 每个操作数(运算对象)都…...
Oracle连接和使用
5. Oracle连接和使用 5.1. sqlplus sqlplus作为甲骨文公司提供的一款本族工具产品,有着悠久的历史和积淀,它几乎伴随着Oracle数据库产生至今的整个生命周期,而且,还会继续和Oracle数据库产品相伴一直发展下去。该工具看似简单灵活的背后,却为广大用户使用Oracle数据库提…...
redis单线程为什么这么快
redis单线程为什么这么快 redis是使用的单线程来进行操作的,因为所有的数据都是在内存中的,内存操作特别快。而且单线程避免了多线程切换性能损耗问题 单线程如何处理并发客户端连接? redis利用epoll来实现IO多路复用,将连接信息和…...
工业机器视觉megauging(向光有光)使用说明书(五,轻量级的visionpro)
这个说明主要介绍抓线功能。 第一步,添加线工具,鼠标双击工具箱“抓线”,出现如下界面: 第二步,我们拉一条,“九点标定”到“抓线1”的线,和visionpro操作一样: 第三步,…...
【LittleXi】2023年广东工业大学腾讯杯新生程序设计竞赛
文章目录 【LittleXi】2023年广东工业大学腾讯杯新生程序设计竞赛A.星期几考试?C.信件D、乘除法E、不知道叫什么名字F.我要学会盾反!G.闪闪发光心动不已!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 次方之和,则称该数为阿姆斯特朗数。 例如 1^3 5^3 3^3 153。 1000 以内的阿姆斯特朗数: 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解决办法参考: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 春晓 孟浩然〔唐代〕 春眠不觉晓,处处闻啼鸟。 夜来风雨声,花落知多少。 2 分别使用 read()、readline()、readlines() 函数 2.1 # read() -------- 一次性读取所有文本,以字符串的形式返回结果。 # 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命令在软件测试中的实际应用
简介:当你想要了解 Linux 系统在启动时究竟发生了什么?或者当硬件设备不工作时,如何进行调试?这就是 dmesg 命令的用武之地。本文将介绍 dmesg 的基本功能,并深入探讨其在软件测试中的实际应用。 历史攻略:…...
【渗透】记录阿里云CentOS一次ddos攻击
文章目录 发现防御 发现 防御 流量清洗 使用高防...
前端面试提问(3)
1、js两个数相加会不会丢精度? 可能会遇到精度丢失的问题。JavaScript 使用的是 IEEE 754 浮点数标准,即一种二进制表示法,有时不能准确地表示十进制小数。如果你需要进行精确的十进制数值计算,可以使用一些处理精确数值的库&…...
fl studio21.2最新汉化中文完整版网盘下载
fl studio 21中文版是Image-Line公司继20版本之后更新的水果音乐制作软件,很多用户不太理解,为什么新版本不叫fl studio 21或fl studio2024,非得直接跳到21.2版本,其实该版本是为了纪念该公司22周年,所以该版本也是推出…...
差分数组相关知识点以及刷题
差分数组 差分数组是什么? **举例:**对于数组考虑数组 a[1,3,3,5,8],对其中的相邻元素两两作差(右边减左边),得到数组 [2,0,2,3]。然后在开头补上 a[0],得到差分数组: d[1,2,0…...
使用 DMA 在 FPGA 中的 HDL 和嵌入式 C 之间传输数据
使用 DMA 在 FPGA 中的 HDL 和嵌入式 C 之间传输数据 该项目介绍了如何在 PL 中的 HDL 与 FPGA 中的处理器上运行的嵌入式 C 之间传输数据的基本结构。 介绍 鉴于机器学习和人工智能等应用的 FPGA 设计中硬件加速的兴起,现在是剥开几层“云雾”并讨论 HDL 之间来回传…...
uniapp地图基本使用及解决添加markers不生效问题?
uniapp地图使用 App端 通过 nvue 页面实现地图 文章目录 uniapp地图使用效果图templatejs添加 marker使用地图查看位置移到到当前位置 效果图 template <template><view class"mapWrap"><!-- #ifdef APP-NVUE --><map class"map-containe…...
使用系统ProgressBar实现三色进度条
使用系统ProgressBar实现如图三色进度条: //布局中<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欢迎来到前端的新世界 😜当前文章系列专栏:vue.js 🐱👓博主在前端…...
生成xcframework
打包 XCFramework 的方法 XCFramework 是苹果推出的一种多平台二进制分发格式,可以包含多个架构和平台的代码。打包 XCFramework 通常用于分发库或框架。 使用 Xcode 命令行工具打包 通过 xcodebuild 命令可以打包 XCFramework。确保项目已经配置好需要支持的平台…...
大话软工笔记—需求分析概述
需求分析,就是要对需求调研收集到的资料信息逐个地进行拆分、研究,从大量的不确定“需求”中确定出哪些需求最终要转换为确定的“功能需求”。 需求分析的作用非常重要,后续设计的依据主要来自于需求分析的成果,包括: 项目的目的…...
【大模型RAG】Docker 一键部署 Milvus 完整攻略
本文概要 Milvus 2.5 Stand-alone 版可通过 Docker 在几分钟内完成安装;只需暴露 19530(gRPC)与 9091(HTTP/WebUI)两个端口,即可让本地电脑通过 PyMilvus 或浏览器访问远程 Linux 服务器上的 Milvus。下面…...
ServerTrust 并非唯一
NSURLAuthenticationMethodServerTrust 只是 authenticationMethod 的冰山一角 要理解 NSURLAuthenticationMethodServerTrust, 首先要明白它只是 authenticationMethod 的选项之一, 并非唯一 1 先厘清概念 点说明authenticationMethodURLAuthenticationChallenge.protectionS…...
BCS 2025|百度副总裁陈洋:智能体在安全领域的应用实践
6月5日,2025全球数字经济大会数字安全主论坛暨北京网络安全大会在国家会议中心隆重开幕。百度副总裁陈洋受邀出席,并作《智能体在安全领域的应用实践》主题演讲,分享了在智能体在安全领域的突破性实践。他指出,百度通过将安全能力…...
智能分布式爬虫的数据处理流水线优化:基于深度强化学习的数据质量控制
在数字化浪潮席卷全球的今天,数据已成为企业和研究机构的核心资产。智能分布式爬虫作为高效的数据采集工具,在大规模数据获取中发挥着关键作用。然而,传统的数据处理流水线在面对复杂多变的网络环境和海量异构数据时,常出现数据质…...
USB Over IP专用硬件的5个特点
USB over IP技术通过将USB协议数据封装在标准TCP/IP网络数据包中,从根本上改变了USB连接。这允许客户端通过局域网或广域网远程访问和控制物理连接到服务器的USB设备(如专用硬件设备),从而消除了直接物理连接的需要。USB over IP的…...
html css js网页制作成品——HTML+CSS榴莲商城网页设计(4页)附源码
目录 一、👨🎓网站题目 二、✍️网站描述 三、📚网站介绍 四、🌐网站效果 五、🪓 代码实现 🧱HTML 六、🥇 如何让学习不再盲目 七、🎁更多干货 一、👨…...
【分享】推荐一些办公小工具
1、PDF 在线转换 https://smallpdf.com/cn/pdf-tools 推荐理由:大部分的转换软件需要收费,要么功能不齐全,而开会员又用不了几次浪费钱,借用别人的又不安全。 这个网站它不需要登录或下载安装。而且提供的免费功能就能满足日常…...
【JVM面试篇】高频八股汇总——类加载和类加载器
目录 1. 讲一下类加载过程? 2. Java创建对象的过程? 3. 对象的生命周期? 4. 类加载器有哪些? 5. 双亲委派模型的作用(好处)? 6. 讲一下类的加载和双亲委派原则? 7. 双亲委派模…...
