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

简介: ☆打卡算法☆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的长度,栈内元素个数不会超过逆波兰表达式的长度。

三、总结

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

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

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

相关文章
|
5天前
|
机器学习/深度学习 数据采集 自然语言处理
理解并应用机器学习算法:神经网络深度解析
【5月更文挑战第15天】本文深入解析了神经网络的基本原理和关键组成,包括神经元、层、权重、偏置及损失函数。介绍了神经网络在图像识别、NLP等领域的应用,并涵盖了从数据预处理、选择网络结构到训练与评估的实践流程。理解并掌握这些知识,有助于更好地运用神经网络解决实际问题。随着技术发展,神经网络未来潜力无限。
|
3天前
|
缓存 算法 Java
数据结构~缓存淘汰算法--LRU算法(Java的俩种实现方式,万字解析
数据结构~缓存淘汰算法--LRU算法(Java的俩种实现方式,万字解析
|
3天前
|
缓存 算法 前端开发
前端开发者必知的缓存淘汰策略:LRU算法解析与实践
前端开发者必知的缓存淘汰策略:LRU算法解析与实践
|
4天前
|
算法 PyTorch Go
深入解析yolov5,为什么算法都是基于yolov5做改进的?(一)
深入解析yolov5,为什么算法都是基于yolov5做改进的?(一)
|
5天前
leetcode代码记录(逆波兰表达式求值
leetcode代码记录(逆波兰表达式求值
12 0
|
5天前
|
存储 算法
Leetcode 30天高效刷数据结构和算法 Day1 两数之和 —— 无序数组
给定一个无序整数数组和目标值,找出数组中和为目标值的两个数的下标。要求不重复且可按任意顺序返回。示例:输入nums = [2,7,11,15], target = 9,输出[0,1]。暴力解法时间复杂度O(n²),优化解法利用哈希表实现,时间复杂度O(n)。
22 0
|
5天前
|
存储 机器学习/深度学习 算法
|
5天前
|
机器学习/深度学习 自然语言处理 算法
深度解析深度学习中的优化算法:从梯度下降到自适应方法
【4月更文挑战第28天】 在深度学习模型训练的复杂数学迷宫中,优化算法是寻找最优权重配置的关键导航者。本文将深入探讨几种主流的优化策略,揭示它们如何引导模型收敛至损失函数的最小值。我们将比较经典的批量梯度下降(BGD)、随机梯度下降(SGD)以及动量概念的引入,进一步探索AdaGrad、RMSProp和Adam等自适应学习率方法的原理与实际应用。通过剖析这些算法的理论基础和性能表现,我们旨在为读者提供一个关于选择合适优化器的参考视角。
|
5天前
|
机器学习/深度学习 数据采集 人工智能
【热门话题】AI作画算法原理解析
本文解析了AI作画算法的原理,介绍了基于机器学习和深度学习的CNNs及GANs在艺术创作中的应用。从数据预处理到模型训练、优化,再到风格迁移、图像合成等实际应用,阐述了AI如何生成艺术作品。同时,文章指出未来发展中面临的版权、伦理等问题,强调理解这些算法对于探索艺术新境地的重要性。
34 3
|
5天前
|
存储 算法 安全

推荐镜像

更多