0150. 逆波兰表达式求值 · ttttt

# 0150. 逆波兰表达式求值 ## 题目地址(150. 逆波兰表达式求值) <https://leetcode-cn.com/problems/evaluate-reverse-polish-notation/> ## 题目描述 ``` <pre class="calibre18">``` 根据逆波兰表示法，求表达式的值。有效的运算符包括 +, -, *, / 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。说明：整数除法只保留整数部分。给定逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。示例 1：输入: ["2", "1", "+", "3", "*"] 输出: 9 解释: 该算式转化为常见的中缀算术表达式为：((2 + 1) * 3) = 9 示例 2：输入: ["4", "13", "5", "/", "+"] 输出: 6 解释: 该算式转化为常见的中缀算术表达式为：(4 + (13 / 5)) = 6 示例 3：输入: ["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 逆波兰表达式：逆波兰表达式是一种后缀表达式，所谓后缀就是指算符写在后面。平常使用的算式则是一种中缀表达式，如 ( 1 + 2 ) * ( 3 + 4 ) 。该算式的逆波兰表达式写法为 ( ( 1 2 + ) ( 3 4 + ) * ) 。逆波兰表达式主要有以下两个优点：去掉括号后表达式无歧义，上式即便写成 1 2 + 3 4 + * 也可以依据次序计算出正确结果。适合用栈操作运算：遇到数字则入栈；遇到算符则取出栈顶两个数字进行计算，并将结果压入栈中。 ``` ``` ## 前置知识 - 栈 ## 公司 - 阿里 - 腾讯 ## 思路逆波兰表达式又叫做后缀表达式。在通常的表达式中，二元运算符总是置于与之相关的两个运算对象之间，这种表示法也称为`中缀表示`。波兰逻辑学家J.Lukasiewicz于1929年提出了另一种表示表达式的方法，按此方法，每一运算符都置于其运算对象之后，故称为`后缀表示`。 > 逆波兰表达式是一种十分有用的表达式，它将复杂表达式转换为可以依靠简单的操作得到计算结果的表达式。例如(a+b)*(c+d)转换为ab+cd+* ## 关键点 1. 栈的基本用法 2. 如果你用的是JS的话，需要注意/ 和其他很多语言是不一样的 3. 如果你用的是JS的话，需要先将字符串转化为数字。否则有很多意想不到的结果 4. 操作符的顺序应该是先出栈的是第二位，后出栈的是第一位。这在不符合交换律的操作中很重要，比如减法和除法。 ## 代码 ``` <pre class="calibre18">``` /** * @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(); }; ``` ``` ## 扩展逆波兰表达式中只改变运算符的顺序，并不会改变操作数的相对顺序，这是一个重要的性质。另外逆波兰表达式完全不关心操作符的优先级，这在中缀表达式中是做不到的，这很有趣，感兴趣的可以私下查找资料研究下为什么会这样。