☆打卡算法☆LeetCode 150. 逆波兰表达式求值 算法解析

本文涉及的产品
公共DNS(含HTTPDNS解析),每月1000万次HTTP解析
云解析 DNS,旗舰版 1个月
全局流量管理 GTM,标准版 1个月
简介: ☆打卡算法☆LeetCode 150. 逆波兰表达式求值 算法解析

大家好,我是小魔龙,Unity3D软件工程师,VR、AR,虚拟仿真方向,不定时更新软件开发技巧,生活感悟,觉得有用记得一键三连哦。

一、题目

1、算法题目

“根据逆波兰表达式求表达式的值。”

2、题目描述

根据 逆波兰表示法,求表达式的值。

有效的算符包括 +、-、*、/ 。每个运算对象可以是整数,也可以是另一个逆波兰表达式。

注意 两个整数之间的除法只保留整数部分。

可以保证给定的逆波兰表达式总是有效的。换句话说,表达式总会得出有效数值且不存在除数为 0 的情况。

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

二、解题

1、思路分析

首先来了解一下什么是逆波兰表达式。

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

根据 逆波兰表示法,求表达式的值,可以使用栈存储操作数,从左到右遍历逆波兰表达式:

  • 遇到操作数,将操作数入栈
  • 遇到运算符,将两个操作数出栈,先出栈的右操作数,后出栈的是左操作数,使用运算符对两个操作数进行运算
  • 将运算后的得到的新操作数入栈

整个逆波兰表达式遍历之后,栈内只有一个元素,也就是逆波兰表达式的值。

2、代码实现

代码参考:

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));
    }
}

1702362031841.jpg

3、时间复杂度

时间复杂度:O(n)

其中n是数组tokens的长度,需要遍历数组一次。

空间复杂度:O(n)

其中n是数组tokens的长度,栈内元素个数不会超过逆波兰表达式的长度。

三、总结

对于这道题来说,还可以使用递归来解。

因为对于逆波兰表达式来说,序列的最后一个符号一定是最先得到计算的,而一旦有符号,就至少需要两个以上的操作数。

用一个变量,记录表达式遍历的位置,遇到操作数可以返回,遇到符号则再递归地计算两个操作数,然后根据不同的符号进行对应的计算返回即可。

相关文章
|
23天前
|
算法 前端开发 数据处理
小白学python-深入解析一位字符判定算法
小白学python-深入解析一位字符判定算法
44 0
|
16天前
|
存储 算法 Java
解析HashSet的工作原理,揭示Set如何利用哈希算法和equals()方法确保元素唯一性,并通过示例代码展示了其“无重复”特性的具体应用
在Java中,Set接口以其独特的“无重复”特性脱颖而出。本文通过解析HashSet的工作原理,揭示Set如何利用哈希算法和equals()方法确保元素唯一性,并通过示例代码展示了其“无重复”特性的具体应用。
35 3
|
18天前
|
搜索推荐 算法
插入排序算法的平均时间复杂度解析
【10月更文挑战第12天】 插入排序是一种简单直观的排序算法,通过不断将未排序元素插入到已排序部分的合适位置来完成排序。其平均时间复杂度为$O(n^2)$,适用于小规模或部分有序的数据。尽管效率不高,但在特定场景下仍具优势。
|
1天前
|
缓存 负载均衡 算法
Linux内核中的进程调度算法解析####
本文深入探讨了Linux操作系统核心组件之一——进程调度器,着重分析了其采用的CFS(完全公平调度器)算法。不同于传统摘要对研究背景、方法、结果和结论的概述,本文摘要将直接揭示CFS算法的核心优势及其在现代多核处理器环境下如何实现高效、公平的资源分配,同时简要提及该算法如何优化系统响应时间和吞吐量,为读者快速构建对Linux进程调度机制的认知框架。 ####
|
24天前
|
机器学习/深度学习 算法 PyTorch
Pytorch-RMSprop算法解析
关注B站【肆十二】,观看更多实战教学视频。本期介绍深度学习中的RMSprop优化算法,通过调整每个参数的学习率来优化模型训练。示例代码使用PyTorch实现,详细解析了RMSprop的参数及其作用。适合初学者了解和实践。
33 1
|
18天前
|
前端开发 算法 JavaScript
无界SaaS模式深度解析:算力算法、链接力、数据确权制度
私域电商的无界SaaS模式涉及后端开发、前端开发、数据库设计、API接口、区块链技术、支付和身份验证系统等多个技术领域。本文通过简化框架和示例代码,指导如何将核心功能转化为技术实现,涵盖用户管理、企业店铺管理、数据流量管理等关键环节。
|
24天前
|
机器学习/深度学习 算法 PyTorch
Pytorch-SGD算法解析
SGD(随机梯度下降)是机器学习中常用的优化算法,特别适用于大数据集和在线学习。与批量梯度下降不同,SGD每次仅使用一个样本来更新模型参数,提高了训练效率。本文介绍了SGD的基本步骤、Python实现及PyTorch中的应用示例。
29 0
|
24天前
|
机器学习/深度学习 传感器 算法
Pytorch-Adam算法解析
肆十二在B站分享深度学习实战教程,本期讲解Adam优化算法。Adam结合了AdaGrad和RMSProp的优点,通过一阶和二阶矩估计,实现自适应学习率,适用于大规模数据和非稳态目标。PyTorch中使用`torch.optim.Adam`轻松配置优化器。
34 0
|
28天前
|
存储 搜索推荐 算法
【排序算法(二)】——冒泡排序、快速排序和归并排序—>深层解析
【排序算法(二)】——冒泡排序、快速排序和归并排序—>深层解析
|
28天前
|
搜索推荐 算法
【排序算法(一)】——插入排序,选择排序 —> 深层解析
【排序算法(一)】——插入排序,选择排序 —> 深层解析

推荐镜像

更多