LeetCode 之 JavaScript 解答第150题 —— 逆波兰表达式求值

2019-04-15 admin

Time:2019/4/14 Title: Evaluate Reverse Polish Notation Difficulty: Medium Author:小鹿


题目:Evaluate Reverse Polish Notation

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.

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

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

说明:

  • 整数除法只保留整数部分。
  • 给定逆波兰表达式总是有效的。换句话说,表达式总会得出有效数值且不存在除数为 0 的情况。

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

Solve:

▉ 算法思路

仔细观察上述的逆波兰表达式,可以发现一个规律就是每遇到一个操作符,就将操作符前的两个操作数进行运算,将结果保存到原位置。

1)我们可以将这个过程用栈来进行操作。

2)所有的操作数都执行近栈操作,当遇到操作符时,在栈中取出两个操作数进行计算,然后再将其压入栈内,继续遍历数组元素,直到遍历完整个数组为止。

3)到最后,栈内只剩下一个数,那就是最后的结果。

▉ 注意事项

虽然过程很好理解,代码写起来很简单,但是想把算法写的全面还是需要考虑到很多方面的。

1)数组中的是字符串类型,要进行数据类型转换 parseInt()

2)两个操作数进行运算时,第二个出栈的操作数在前,第一个出栈的操作数在后(注意除法)。

3)对于浮点型数据,只取小数点之前的整数。

4)关于负的浮点型(尤其是 0 点几 ),要取 0 绝对值 0 ,或直接转化为整数。

▉ 代码实现
var evalRPN = function(tokens) {
   // 声明栈
    let stack = [];
    for(let item of tokens){
        switch(item){
            case '+':
                let a1 = stack.pop();
                let b1 = stack.pop();
                stack.push(b1 + a1);
                break;
            case '-':
                let a2 = stack.pop();
                let b2 = stack.pop();
                stack.push(b2 - a2);
                break;
            case '*':
                let a3 = stack.pop();
                let b3 = stack.pop();
                stack.push(b3 * a3);
                break;
            case '/':
                let a4 = stack.pop();
                let b4 = stack.pop();
                stack.push(parseInt(b4 / a4));
                break;
            default: 
                stack.push(parseInt(item));
        }
    }
    return parseInt(stack.pop());
};

欢迎一起加入到 LeetCode 开源 Github 仓库,可以向 me 提交您其他语言的代码。在仓库上坚持和小伙伴们一起打卡,共同完善我们的开源小仓库! Github:https://github.com/luxiangqia…

[转载]原文链接:https://segmentfault.com/a/1190000018875981

本站文章除注明转载外,均为本站原创或编译。欢迎任何形式的转载,但请务必注明出处。

转载请注明:文章转载自 JavaScript中文网 [https://www.javascriptcn.com]

本文地址:https://www.javascriptcn.com/read-61859.html

文章标题:LeetCode 之 JavaScript 解答第150题 —— 逆波兰表达式求值

相关文章
JavaScript常用特效chm下载
下载地址:JavaScript常用特效chm下载 对了,如果打开空白,在手册上右键属性解除锁定即可。 ...
2015-11-12
JavaScript教程:JS中的原型
Keith Peters 几年前发表的一篇博文,关于学习没有“new”的世界,其中解释了使用原型继承代替构造函数。两者都是纯粹的原型编码。 标准方法(The Standard Way) 一直以来,我们学习的在 JavaScript 里创建对...
2015-11-12
javascript是什么意思
avaScript是Netscape开发的一个对象脚本语言,它使用在世界各地数以百万计的网页和服务器应用程序上。 网景的JavaScript是ecma - 262版的标准脚本语言,和公布的标准只有轻微的差异。 与广为流行的错误理解相反,Ja...
2015-11-12
21天学通javascript
简介: 本书是Javascript入门教程。Javascript是Web开发中应用最早、发展最成熟、用户最多的脚本语言。其语法简洁,代码可读性在众多脚本语言中最好,它在使用时不用考虑数据类型,是真正意义上的动态语言。本书总分为四篇,共21章...
2015-11-16
canvas图片绘制跨域问题解决方案Tainted canvases may not be exported
图片跨域问题的一般解决方法 当使用canvas绘制网络图片的时候,经常会出现“Tainted canvases may not be exported”报错,上网搜一下解决方案,应该给的都是给img添加crossOrigin属性,尝试了一下...
2018-04-19
JavaScript的组成
一个完整的JavaScript由3个部分组成:核心(ECMAScript) 文档对象模型(DOM) 浏览器对象模型(BOM) ECMAScript 描述了该语言的语法和基本对象 ; DOM 描述了处理网页内容的方法和接口 ; BOM 描...
2015-11-12
JavaScript 事件流、事件处理程序及事件对象总结
JS与HTML之间的交互通过事件实现。事件就是文档或浏览器窗口中发生的一些特定的交互瞬间。可以使用监听器(或处理程序)来预定事件,以便事件发生时执行相应的代码。这种在传统软件工程中被称为观察员模式,支持页面的行为与页面的外观之间的松散耦合。...
2017-04-05
javaScript+turn.js实现图书翻页效果实例代码
为了实现图书翻页的效果我们在网上可以看到很多教程 在这里推荐turn.js 网上的turn.js 有api 不过是英文的  很多人看起来不方便 .关于代码也是奇形怪状在这里我将详细讲解如何使用turn.js实现翻页效果 ,本篇文章只是讲解 ...
2017-03-16
JavaScript变量的声明
声明变量 变量在脚本中的首次亮相是在其声明中。 在变量首次出现时将会在内存中设置它,因此您稍后可在脚本中引用它。 应在使用变量之前先声明变量。 可以使用 var 关键字实现此目的。 <span id=“mt9” class=“sent...
2015-11-12
jQuery中DOM树操作之使用反向插入方法实例分析
本文实例讲述了jQuery中DOM树操作之使用反向插入方法。分享给大家供大家参考。具体分析如下: 使用反向插入方法 这里我们先把创建的内容插人到元素前面,然后再把同一个元素插人到文档 中的另一个位置。通常,当在jQuery中操作元素时,利用...
2015-11-13
回到顶部