力扣经典150题第五十五题:逆波兰表达式求值
目录
- 题目描述和要求
- 示例解释
- 解题思路
- 算法实现
- 复杂度分析
- 测试和验证
- 总结和拓展
- 参考资料
题目描述和要求
给你一个字符串数组 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
解题思路
我们可以使用栈来解决这个问题。遍历 tokens,当遇到操作数时,将其压入栈中;当遇到操作符时,从栈中弹出两个操作数进行计算,并将结果压入栈中。最终,栈中剩下的唯一元素就是表达式的值。
算法实现
import java.util.Stack;public class EvalRPN {public int evalRPN(String[] tokens) {Stack<Integer> stack = new Stack<>();for (String token : tokens) {if (token.equals("+")) {int b = stack.pop();int a = stack.pop();stack.push(a + b);} else if (token.equals("-")) {int b = stack.pop();int a = stack.pop();stack.push(a - b);} else if (token.equals("*")) {int b = stack.pop();int a = stack.pop();stack.push(a * b);} else if (token.equals("/")) {int b = stack.pop();int a = stack.pop();stack.push(a / b);} else {stack.push(Integer.parseInt(token));}}return stack.pop();}
}
复杂度分析
- 时间复杂度:O(n),其中 n 为 tokens 的长度。遍历一次 tokens。
- 空间复杂度:O(n),使用了一个辅助栈,最坏情况下空间复杂度为 O(n)。
测试和验证
编写测试用例对算法进行验证,确保其正确性和健壮性。
public class Main {public static void main(String[] args) {EvalRPN evalRPN = new EvalRPN();String[] tokens1 = {"2","1","+","3","*"};System.out.println(evalRPN.evalRPN(tokens1)); // 9String[] tokens2 = {"4","13","5","/","+"};System.out.println(evalRPN.evalRPN(tokens2)); // 6String[] tokens3 = {"10","6","9","3","+","-11","*","/","*","17","+","5","+"};System.out.println(evalRPN.evalRPN(tokens3)); // 22}
}
总结和拓展
本题通过使用栈来实现逆波兰表达式的求值,利用栈的后进先出特性完成了计算。这个算法思路清晰简单,在处理类似问题时是一个不错的选择。
除了当前算法,我们也可以考虑其他实现方式,例如使用队列、递归等方法来解决类似问题。
参考资料
- 《力扣经典150题》
- LeetCode 官方网站
相关文章:
力扣经典150题第五十五题:逆波兰表达式求值
目录 题目描述和要求示例解释解题思路算法实现复杂度分析测试和验证总结和拓展参考资料 题目描述和要求 给你一个字符串数组 tokens,表示一个根据逆波兰表示法表示的算术表达式。请你计算该表达式,并返回一个表示表达式值的整数。 注意: 有…...
C#队列(Queue)的基本使用
概述 在编程中,队列(Queue)是一种常见的数据结构,它遵循FIFO(先进先出)的原则。在C#中,.NET Framework提供了Queue<T>类,它位于System.Collections.Generic命名空间下&#x…...
预训练模型介绍
一、什么是GPT GPT 是由人工智能研究实验室 OpenAI 在2022年11月30日发布的全新聊天机器人模型, 一款人工智能技术驱动的自然语言处理工具 它能够通过学习和理解人类的语言来进行对话, 还能根据聊天的上下文进行互动,能完成撰写邮件、视频脚本、文案、翻译、代码等任务 二、 为…...
Pandas入门篇(三)-------数据可视化篇3(seaborn篇)(pandas完结撒花!!!)
目录 概述一、语法二、常用单变量绘图1. 直方图(histplot)2. 核密度预估图(kdeplot)3. 计数柱状图(countplot) 三、常用多变量绘图1.散点图(1) scatterplot(2)regplot 散点图拟合回归线(3)jointplot 散点图…...
SpringBoot中阿里OSS简单使用
官方文档:Java跨域设置实现跨域访问_对象存储(OSS)-阿里云帮助中心 1.pom中引入依赖 <dependency><groupId>com.aliyun.oss</groupId><artifactId>aliyun-sdk-oss</artifactId><version>3.15.1</version> </dependency> 如…...
websocket简介
服务端推送消息给浏览器 WebSocket 教程 - 阮一峰的网络日志...
Linux的shell外壳
Shell外壳 在计算机领域,“shell”(外壳)是指一种用户界面,提供了访问操作系统服务的方式。Shell 是用户与操作系统之间的桥梁,它解释并执行用户输入的命令。 Shell 的主要功能包括: 命令解释:…...
支付宝支付流程
第一步前端:点击去结算,前端将商品的信息传递给后端,后端返回一个商品的订单号给到前端,前端将商品的订单号进行存储。 对应的前端代码:然后再跳转到支付页面 // 第一步 点击去结算 然后生成一个订单号 // 将选中的商…...
打招呼得不到回复,跟头像还有关系?
现在很多人有个想法,那就是觉得某些公司是不是为了某些目的才往出发的招聘信息啊,其实他们并不需要招聘新员工。 目录 已读不回? 头像很重要 选择自己的精修照片 已读不回? 很有这种可能,但你细心观察会发现,的确有很多大公司,...
【网络原理】HTTPS 的工作过程
系列文章目录 【网络通信基础】网络中的常见基本概念 【网络编程】网络编程中的基本概念及Java实现UDP、TCP客户端服务器程序(万字博文) 【网络原理】UDP协议的报文结构 及 校验和字段的错误检测机制(CRC算法、MD5算法) 【网络…...
Python语言在地球科学中地理、气象、气候变化、水文、生态、传感器等数据可视化到常见数据分析方法的使用
Python是功能强大、免费、开源,实现面向对象的编程语言,Python能够运行在Linux、Windows、Macintosh、AIX操作系统上及不同平台(x86和arm),Python简洁的语法和对动态输入的支持,再加上解释性语言的本质&…...
【JVM】class文件格式,JVM加载class文件流程,JVM运行时内存区域,对象分配内存流程
这篇文章本来只是想讲一下class文件格式,讲着讲着越讲越多。JVM这一块吧,知识比较散比较多,如果深研究下去如死扣《深入理解Java虚拟机》,这本书很深很细,全记住是不可能的,其实也没必要。趁这个机会直接把…...
GPU系列(六)-NVIDIA GPU 驱动安装
1. 安装驱动 1.1 查看系统是否识别显卡 lspci | grep -i vga03:00.0 VGA compatible controller: NVIDIA Corporation GP102 [TITAN X] (rev a1) 0a:00.0 VGA compatible controller: Matrox Electronics Systems Ltd. G200eR2 (rev 01) 识别出显卡为 NVIDIA 的 TITAN X。 …...
第十五届蓝桥杯总结
因为本人不是计院的,以后可能也不会打算法类的竞赛了,故作此总结,纪念我四个月的算法学习经历,还算是对算法有了一定的基础,碰运气拿下了湖北b组省二,个人感觉比赛题目没有第十四届难,感觉就是纯…...
Linux驱动开发——(八)Linux异步通知
目录 一、异步通知简介 二、信号处理 2.1 驱动程序中的处理 2.1.1 fasync_struct结构体 2.1.2 fasync操作函数 2.1.3 kill_fasync函数 2.2 应用程序中的处理 三、驱动代码 一、异步通知简介 异步通知的核心就是信号。信号类似于硬件上使用的中断,只不过信号…...
Docker知识点汇总表格总结
Docker容器给我的一个很直观的感受就是将项目以及中间件安装变得比较简单直接,运行维护起来也更方便。之前做的一些微服务项目也是用docker来部署,现在很多开源的项目也流行使用docker来部署,简化了很多手动安装和配置的步骤,将项…...
Golang中实现调用Windows API向指定目标发送ARP请求
简介 Go库中很多实现的arp都是支持osx/linux/bsd之类的, 但几乎没有支持windows的, 也试了一些方式, 目前还是选用调用windows的API, 记录一下这一次windows的API的调用经验。 实现 代码 package main/* #cgo CFLAGS: -I. #cgo …...
这是一个简单的照明材料网站,后续还会更新
1、首页效果图 代码 <!DOCTYPE html> <html><head><meta charset"utf-8" /><title>爱德照明网站首页</title><style>/*外部样式*/charset "utf-8";*{margin: 0;padding: 0;box-sizing: border-box;}a{text-dec…...
【设计模式】之模板方法模式
系列文章目录 【设计模式】之策略模式 【设计模式】之责任链模式 文章目录 系列文章目录 前言 一、什么是模板方法模式 定义 角色 二、为什么要使用模板方法模式 优点 缺点 三、案例 普通案例 模拟Servlet过程案例 总结 前言 今天给大家介绍23种设计模式中的模板方法模式&a…...
【系统架构师】-选择题(十一)
1、紧耦合多机系统一般通过(共享内存)实现多机间的通信。对称多处理器结构(SMP)属于( 紧耦合)系统。 松耦合多机系统又称间接耦合系统,—般是通过通道或通信线路实现计算机间的互连。 2、采用微内核的OS结构…...
Windows 10/11 下用 Anaconda 和 Hadoop 3.3.6 搞定 PySpark 环境,附赠 Winutils 下载避坑指南
Windows 10/11 下用 Anaconda 和 Hadoop 3.3.6 搞定 PySpark 环境,附赠 Winutils 下载避坑指南 在 Windows 系统上搭建 PySpark 开发环境,对于数据科学家和开发者来说既是一个必经之路,也是一场充满挑战的冒险。不同于 Linux 或 macOS 系统&a…...
核聚变装置逼近极限时会“漏水“:科学家发现热流平衡决定密度天花板
来源:科学剃刀人类距离可控核聚变又近了一步,但一道隐形天花板始终悬在头顶。当反应堆试图提高燃料密度以获得更多能量时,等离子体总会在某个临界点突然崩溃。这种"密度极限"现象困扰了聚变界四十年。现在,美国麻省理工…...
FreeRTOS实战指南:从消息队列到内存管理,手把手解决嵌入式多任务难题
FreeRTOS实战指南:从消息队列到内存管理,手把手解决嵌入式多任务难题 1. 为什么嵌入式开发者需要FreeRTOS 在资源受限的嵌入式系统中,开发者常常面临这样的困境:既要处理实时性要求高的传感器数据采集,又要兼顾用户界面…...
【悬疑言情小说推荐】《血语玫瑰》
《血语玫瑰》国际标准书号:ISBN:978-986-6364-30-3 作者:追月逐花 本书地址:http://e.dangdang.com/products/1901197341.html 每个女孩都期待男友年轻英俊、家境优渥、学识出众,而 “魔鬼” 恰好符合所有条件&…...
3大突破:重新定义Revit插件开发流程
3大突破:重新定义Revit插件开发流程 【免费下载链接】RevitAddInManager Revit AddinManager update .NET assemblies without restart Revit for developer. 项目地址: https://gitcode.com/gh_mirrors/re/RevitAddInManager 引言:Revit插件开发…...
微信聊天记录永久保存与智能分析:WeChatMsg完全使用指南
微信聊天记录永久保存与智能分析:WeChatMsg完全使用指南 【免费下载链接】WeChatMsg 提取微信聊天记录,将其导出成HTML、Word、CSV文档永久保存,对聊天记录进行分析生成年度聊天报告 项目地址: https://gitcode.com/GitHub_Trending/we/WeC…...
Python 字典遍历全攻略:5 种常用方法 + 性能对比 + 实战优化技巧
在 Python 开发中,字典(dict) 是最常用的数据结构之一,以键值对形式存储数据,具备查询快、易操作的特点。而字典的遍历是日常开发中高频操作 —— 从简单的数据读取,到大规模数据处理、接口返回值解析&…...
Otter模型对比学习:提升跨模态表示质量的技术方案
Otter模型对比学习:提升跨模态表示质量的技术方案 【免费下载链接】Otter 🦦 Otter, a multi-modal model based on OpenFlamingo (open-sourced version of DeepMinds Flamingo), trained on MIMIC-IT and showcasing improved instruction-following a…...
Qwen3.5-4B-Claude-Opus快速上手:Web页面直接调用推理蒸馏模型
Qwen3.5-4B-Claude-Opus快速上手:Web页面直接调用推理蒸馏模型 1. 模型概述 Qwen3.5-4B-Claude-4.6-Opus-Reasoning-Distilled-GGUF 是一个基于 Qwen3.5-4B 的推理蒸馏模型,重点强化了结构化分析、分步骤回答、代码与逻辑类问题的处理能力。该版本以 G…...
FOC算法避坑指南:克拉克变换的‘等幅值’与‘等功率’到底选哪个?基于AS5600编码器的实测对比
FOC算法避坑指南:克拉克变换的‘等幅值’与‘等功率’到底选哪个?基于AS5600编码器的实测对比 在无刷电机控制领域,FOC(Field Oriented Control)算法因其优异的动态性能和效率表现,已成为工业驱动和高精度…...
