题目地址
https://leetcode.com/problems/evaluate-reverse-polish-notation/description/
题目描述
Evaluate the value of an arithmetic expression in Reverse Polish Notation.
Valid operators are +, -, *, /. Each operand may be an integer or another expression.
Note:
Division between two integers should truncate toward zero.
The given RPN expression is always valid. That means the expression would always evaluate to a result and there won't be any divide by zero operation.
思路
逆波兰表达式又叫做后缀表达式。在通常的表达式中,二元运算符总是置于与之相关的两个运算对象之间,这种表示法也称为中缀表示
。
波兰逻辑学家J.Lukasiewicz于1929年提出了另一种表示表达式的方法,按此方法,每一运算符都置于其运算对象之后,故称为后缀表示
。
逆波兰表达式是一种十分有用的表达式,它将复杂表达式转换为可以依靠简单的操作得到计算结果的表达式。例如(a+b)(c+d)转换为ab+cd+
关键点
-
栈的基本用法
-
如果你用的是JS的话,需要注意/ 和 其他很多语言是不一样的
-
如果你用的是JS的话,需要先将字符串转化为数字。否则有很多意想不到的结果
-
操作符的顺序应该是 先出栈的是第二位,后出栈的是第一位。 这在不符合交换律的操作中很重要, 比如减法和除法。
代码
/* * @lc app=leetcode id=150 lang=javascript * * [150] Evaluate Reverse Polish Notation * * https://leetcode.com/problems/evaluate-reverse-polish-notation/description/ * * algorithms * Medium (31.43%) * Total Accepted: 153.3K * Total Submissions: 485.8K * Testcase Example: '["2","1","+","3","*"]' * * Evaluate the value of an arithmetic expression in Reverse Polish Notation. * * Valid operators are +, -, *, /. Each operand may be an integer or another * expression. * * Note: * * * Division between two integers should truncate toward zero. * The given RPN expression is always valid. That means the expression would * always evaluate to a result and there won't be any divide by zero * operation. * * * Example 1: * * * Input: ["2", "1", "+", "3", "*"] * Output: 9 * Explanation: ((2 + 1) * 3) = 9 * * * Example 2: * * * Input: ["4", "13", "5", "/", "+"] * Output: 6 * Explanation: (4 + (13 / 5)) = 6 * * * Example 3: * * * Input: ["10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"] * Output: 22 * Explanation: * ((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 * * */ /** * @param {string[]} tokens * @return {number} */ var evalRPN = function(tokens) { // 这种算法的前提是 tokens是有效的, // 当然这由算法来保证 const stack = []; for (let index = 0; index < tokens.length; index++) { const token = tokens[index]; // 对于运算数, 我们直接入栈 if (!Number.isNaN(Number(token))) { stack.push(token); } else { // 遇到操作符,我们直接大胆运算,不用考虑算术优先级 // 然后将运算结果入栈即可 // 当然如果题目进一步扩展,允许使用单目等其他运算符,我们的算法需要做微小的调整 const a = Number(stack.pop()); const b = Number(stack.pop()); if (token === "*") { stack.push(b * a); } else if (token === "/") { stack.push(b / a >> 0); } else if (token === "+") { stack.push(b + a); } else if (token === "-") { stack.push(b - a); } } } return stack.pop(); };
扩展
逆波兰表达式中只改变运算符的顺序,并不会改变操作数的相对顺序,这是一个重要的性质。
另外逆波兰表达式完全不关心操作符的优先级,这在中缀表达式中是做不到的,这很有趣,感兴趣的可以私下查找资料研究下为什么会这样。
堆排序和快速排序都是时间复杂度$O(nlogn)$ 的算法,其中 n 为数据规模。 那么两者谁更快呢? 为什么?题解:快排最坏情况下是O(n^2),平均和最好是O(nlogn) ,堆排序始终为O(nlogn),还是堆排序快吧
LeetCode题解斜着遍历遍历是算法的基础。 我们平时看到的 DFS 和 BFS 都是搜索, 而搜索的核心就是遍历,而关键点就是遍历的方式。 从根本上说动态规划也是枚举所有的可能,而枚举就需要用到遍历。 而平时遍历一个二维数组 martrix 的时候, 我们习惯的方式是按行从左到右或者从右到左遍历。 少有情况是按照列遍历, 更少有情况是斜着遍历。那么这次就考考你, 怎么斜着遍历一个二…
LeetCode题解砝码的最小数量假设有三种重量的砝码,2g、3g、7g,对于任意重量物品,请设计一个函数getResult(weight),接收一个参数weight,返回所需砝码的最小数量。输入示例:const weight = 100;输出示例:getResult(weight) // 15 其中7g的14个,2g的1个题解:```phpfunction getResult($weigh…
LeetCode题解93. 复原IP地址给定一个只包含数字的字符串,复原它并返回所有可能的 IP 地址格式。有效的 IP 地址正好由四个整数(每个整数位于 0 到 255 之间组成),整数之间用 '.' 分隔。 示例:输入: \"25525511135\"输出: [\"255.255.11.135\", \"255.255.111.35\"]来源:力扣(LeetCode)链接:https://le…
可以在没有操作系统的情况下运行Java程序吗? - java我知道所有Java程序都由JVM执行。这使Java与所有操作系统兼容(一次编写,可在任何地方运行)。但是我可以在没有操作系统的情况下运行Java程序吗?也许只运行JVM?并且,如果可能,功能是否会受到任何影响?注意:我的主要问题是,java程序可以直接在硬件上运行(通过JVM)吗?我可以在计算机中“启动”任何低级别的JVM吗? java大神给出的解决方案 实…