力扣经典150题第五十五题:逆波兰表达式求值

2024-05-06 05:20

本文主要是介绍力扣经典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题第五十五题:逆波兰表达式求值的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/963519

相关文章

Spring Security 基于表达式的权限控制

前言 spring security 3.0已经可以使用spring el表达式来控制授权,允许在表达式中使用复杂的布尔逻辑来控制访问的权限。 常见的表达式 Spring Security可用表达式对象的基类是SecurityExpressionRoot。 表达式描述hasRole([role])用户拥有制定的角色时返回true (Spring security默认会带有ROLE_前缀),去

C++11第三弹:lambda表达式 | 新的类功能 | 模板的可变参数

🌈个人主页: 南桥几晴秋 🌈C++专栏: 南桥谈C++ 🌈C语言专栏: C语言学习系列 🌈Linux学习专栏: 南桥谈Linux 🌈数据结构学习专栏: 数据结构杂谈 🌈数据库学习专栏: 南桥谈MySQL 🌈Qt学习专栏: 南桥谈Qt 🌈菜鸡代码练习: 练习随想记录 🌈git学习: 南桥谈Git 🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈�

06 C++Lambda表达式

lambda表达式的定义 没有显式模版形参的lambda表达式 [捕获] 前属性 (形参列表) 说明符 异常 后属性 尾随类型 约束 {函数体} 有显式模版形参的lambda表达式 [捕获] <模版形参> 模版约束 前属性 (形参列表) 说明符 异常 后属性 尾随类型 约束 {函数体} 含义 捕获:包含零个或者多个捕获符的逗号分隔列表 模板形参:用于泛型lambda提供个模板形参的名

HotSpot虚拟机的经典垃圾收集器

读《深入理解Java虚拟机》第三版笔记。 关系 Serial、ParNew、Parallel Scavenge、Parallel Old、Serial Old(MSC)、Concurrent Mark Sweep (CMS)、Garbage First(G1)收集器。 如图: 1、Serial 和 Serial Old 收集器 2、ParNew 收集器 3、Parallel Sc

STL经典案例(四)——实验室预约综合管理系统(项目涉及知识点很全面,内容有点多,耐心看完会有收获的!)

项目干货满满,内容有点过多,看起来可能会有点卡。系统提示读完超过俩小时,建议分多篇发布,我觉得分篇就不完整了,失去了这个项目的灵魂 一、需求分析 高校实验室预约管理系统包括三种不同身份:管理员、实验室教师、学生 管理员:给学生和实验室教师创建账号并分发 实验室教师:审核学生的预约申请 学生:申请使用实验室 高校实验室包括:超景深实验室(可容纳10人)、大数据实验室(可容纳20人)、物联网实验

两数之和--力扣1

两数之和 题目思路C++代码 题目 思路 根据题目要求,元素不能重复且不需要排序,我们这里使用哈希表unordered_map。注意题目说了只对应一种答案。 所以我们在循环中,使用目标值减去当前循环的nums[i],得到差值,如果我们在map中能够找到这个差值,就说明存在两个整数的和为目标值。 如果没有找到,就将当前循环的nums[i]以及下标i放入map中,以便后续查

如何掌握面向对象编程的四大特性、Lambda 表达式及 I/O 流:全面指南

这里写目录标题 OOP语言的四大特性lambda输入/输出流(I/O流) OOP语言的四大特性 面向对象编程(OOP)是一种编程范式,它通过使用“对象”来组织代码。OOP 的四大特性是封装、继承、多态和抽象。这些特性帮助程序员更好地管理复杂的代码,使程序更易于理解和维护。 类-》实体的抽象类型 实体(属性,行为) -》 ADT(abstract data type) 属性-》成

Java基础回顾系列-第三天-Lambda表达式

Java基础回顾系列-第三天-Lambda表达式 Lambda表达式方法引用引用静态方法引用实例化对象的方法引用特定类型的方法引用构造方法 内建函数式接口Function基础接口DoubleToIntFunction 类型转换接口Consumer消费型函数式接口Supplier供给型函数式接口Predicate断言型函数式接口 Stream API 该篇博文需重点了解:内建函数式

C语言程序设计(数据类型、运算符与表达式)

一、C的数据类型 C语言提供的数据类型: 二、常量和变量 2.1常量和符号常量 在程序运行过程中,其值不能被改变的量称为常量。 常量区分为不同的类型: 程序中用#define(预处理器指令)命令行定义变量将代表常量,用一个标识符代表一个常量,称为符合常量。 2.2变量 变量代表内存中具有特定属性的一个存储单元,用来存放数据,在程序运行期间,这些值是可以 改变的。 变

JavaSE(十三)——函数式编程(Lambda表达式、方法引用、Stream流)

函数式编程 函数式编程 是 Java 8 引入的一个重要特性,它允许开发者以函数作为一等公民(first-class citizens)的方式编程,即函数可以作为参数传递给其他函数,也可以作为返回值。 这极大地提高了代码的可读性、可维护性和复用性。函数式编程的核心概念包括高阶函数、Lambda 表达式、函数式接口、流(Streams)和 Optional 类等。 函数式编程的核心是Lambda