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

104828720 发布于2019-08-23 16:56 / 3136人阅读

摘要：小鹿题目根据逆波兰表示法，求表达式的值。给定逆波兰表达式总是有效的。算法思路仔细观察上述的逆波兰表达式，可以发现一个规律就是每遇到一个操作符，就将操作符前的两个操作数进行运算，将结果保存到原位置。

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...

云服务器 GPU云服务器逆波兰式逆波兰表示法逆波兰式算法c语言表达式求值

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/103539.html

LeetCode 150：逆波兰表达式求值 Evaluate Reverse Polish Nota

摘要：题目根据逆波兰表示法，求表达式的值。给定逆波兰表达式总是有效的。逆波兰表达式又叫做后缀表达式。解题思路可以看出逆波兰表达式中的每一个运算符属于该运算符前的两个数字间的运算。如如波兰表达式则加号前两个数字为。题目：根据逆波兰表示法，求表达式的值。有效的运算符包括 +, -, *, / 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。 Evaluate the value of...

Turbo 2019-08-19 10:19 评论0 收藏0
表达式类算法题小结

摘要：将表达式转换为逆波兰式，然后求值转换中缀表达式为逆波兰式鲁棒性检测，表达式中没有操作数计算逆波兰式值参考表达式类算法题小结 [TOC] 声明文章均为本人技术笔记，转载请注明出处：[1] https://segmentfault.com/u/yzwall[2] blog.csdn.net/j_dark/ 表达式分类根据运算符与相关操作操作数的位置不同，将表达式分为前缀，中缀和后缀表...

Heier 2019-08-16 10:32 评论0 收藏0
堆栈的应用——用JavaScript描述数据结构

摘要：一实现一个栈类基于堆栈的特性，可以用数组做线性表进行存储。出栈出栈同样是利用数组的方法，在数组尾部推出数据。聚合最后，将所有功能聚合后，如下所示，一个堆栈的数据结构就搞定了。堆栈的经典算法应用，首推就是汉诺塔。栈（stack）又名堆栈，它是一种运算受限的线性表。其限制是仅允许在表的一端进行插入和删除运算。这一端被称为栈顶，相对地，把另一端称为栈底。一、实现一个栈类Stack 基于堆...

Hydrogen 2019-08-23 10:54 评论0 收藏0
[Leetcode] Evaluate Reverse Polish Notation 计算逆波兰表

摘要：栈法复杂度时间空间思路逆波兰表达式的计算十分方便，对于运算符，其运算的两个数就是这个运算符前面的两个数。注意对于减法，先弹出的是减号后面的数。 Evaluate Reverse Polish Notation Evaluate the value of an arithmetic expression in Reverse Polish Notation. Valid operato...

ephererid 2019-08-14 12:40 评论0 收藏0