力扣经典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结构…...
[特殊字符] 智能合约中的数据是如何在区块链中保持一致的?
🧠 智能合约中的数据是如何在区块链中保持一致的? 为什么所有区块链节点都能得出相同结果?合约调用这么复杂,状态真能保持一致吗?本篇带你从底层视角理解“状态一致性”的真相。 一、智能合约的数据存储在哪里…...
VB.net复制Ntag213卡写入UID
本示例使用的发卡器:https://item.taobao.com/item.htm?ftt&id615391857885 一、读取旧Ntag卡的UID和数据 Private Sub Button15_Click(sender As Object, e As EventArgs) Handles Button15.Click轻松读卡技术支持:网站:Dim i, j As IntegerDim cardidhex, …...
前端倒计时误差!
提示:记录工作中遇到的需求及解决办法 文章目录 前言一、误差从何而来?二、五大解决方案1. 动态校准法(基础版)2. Web Worker 计时3. 服务器时间同步4. Performance API 高精度计时5. 页面可见性API优化三、生产环境最佳实践四、终极解决方案架构前言 前几天听说公司某个项…...
深入理解JavaScript设计模式之单例模式
目录 什么是单例模式为什么需要单例模式常见应用场景包括 单例模式实现透明单例模式实现不透明单例模式用代理实现单例模式javaScript中的单例模式使用命名空间使用闭包封装私有变量 惰性单例通用的惰性单例 结语 什么是单例模式 单例模式(Singleton Pattern&#…...
C# 类和继承(抽象类)
抽象类 抽象类是指设计为被继承的类。抽象类只能被用作其他类的基类。 不能创建抽象类的实例。抽象类使用abstract修饰符声明。 抽象类可以包含抽象成员或普通的非抽象成员。抽象类的成员可以是抽象成员和普通带 实现的成员的任意组合。抽象类自己可以派生自另一个抽象类。例…...
前端开发面试题总结-JavaScript篇(一)
文章目录 JavaScript高频问答一、作用域与闭包1.什么是闭包(Closure)?闭包有什么应用场景和潜在问题?2.解释 JavaScript 的作用域链(Scope Chain) 二、原型与继承3.原型链是什么?如何实现继承&a…...
多种风格导航菜单 HTML 实现(附源码)
下面我将为您展示 6 种不同风格的导航菜单实现,每种都包含完整 HTML、CSS 和 JavaScript 代码。 1. 简约水平导航栏 <!DOCTYPE html> <html lang"zh-CN"> <head><meta charset"UTF-8"><meta name"viewport&qu…...
[Java恶补day16] 238.除自身以外数组的乘积
给你一个整数数组 nums,返回 数组 answer ,其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。 请 不要使用除法,且在 O(n) 时间复杂度…...
Fabric V2.5 通用溯源系统——增加图片上传与下载功能
fabric-trace项目在发布一年后,部署量已突破1000次,为支持更多场景,现新增支持图片信息上链,本文对图片上传、下载功能代码进行梳理,包含智能合约、后端、前端部分。 一、智能合约修改 为了增加图片信息上链溯源,需要对底层数据结构进行修改,在此对智能合约中的农产品数…...
PHP 8.5 即将发布:管道操作符、强力调试
前不久,PHP宣布了即将在 2025 年 11 月 20 日 正式发布的 PHP 8.5!作为 PHP 语言的又一次重要迭代,PHP 8.5 承诺带来一系列旨在提升代码可读性、健壮性以及开发者效率的改进。而更令人兴奋的是,借助强大的本地开发环境 ServBay&am…...
