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

Turbo 发布于2019-08-19 10:19 / 2631人阅读

摘要：题目根据逆波兰表示法，求表达式的值。给定逆波兰表达式总是有效的。逆波兰表达式又叫做后缀表达式。解题思路可以看出逆波兰表达式中的每一个运算符属于该运算符前的两个数字间的运算。如如波兰表达式则加号前两个数字为。

题目：

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

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

Evaluate the value of an arithmetic expression in Reverse Polish Notation.

Valid operators are +, -, *, /. Each operand may be an integer or another expression.

说明：

整数除法只保留整数部分。

给定逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。

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.

示例 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

扩展：

逆波兰表达式，它的语法规定，表达式必须以逆波兰表达式的方式给出。逆波兰表达式又叫做后缀表达式。这个知识点在数据结构和编译原理这两门课程中都有介绍，下面是一些例子：

a+b ---> a,b,+
a+(b-c) ---> a,b,c,-,+
a+(b-c)*d ---> a,b,c,-,d,*,+
a+d*(b-c)--->a,d,b,c,-,*,+
a=1+3 ---> a,1,3,+,=

从上面的例子可以看出：
(1) 在两种表示中，运算对象出现的顺序相同；
(2) 在后缀表示中，运算符按实际计算顺序从左到右排列，且每一运算符总是跟在其运算对象之后。

这种表达式很反人类，但是对计算机很友好，因为计算机运算是利用栈数据结构。

解题思路：

可以看出逆波兰表达式中的每一个运算符属于该运算符前的两个数字间的运算。如：

如波兰表达式：1,2,+
则加号前两个数字为1,2。其运算符就是加号：1+2
得出结果：1+2=3

如波兰表达式：1,2,3,+,-
则加号前两个数字为2,3。其运算符就是加号：2+3
得出结果2+3=5,则波兰表达式变为:1,5,-
减号前两个数字为1,5，其运算符就是减号：1-5
得出结果1-5=-4

由上面的的例子思路就很清晰了，直接用指针遍历表达式，遇到数字就入栈，遇到运算符就弹出两个数字，把他们运算之后得出结果，再作为独立数字入栈。最后栈内只剩一个元素即表达式运算结果。也可以用递归

Java：

class Solution {
    public int evalRPN(String[] tokens) {
        Stack stack = new Stack<>();
        for (String t : tokens) {
            if (t.equals("+")) {
                stack.push(stack.pop() + stack.pop());
            } else if (t.equals("-")) {
                int tmp = stack.pop();
                stack.push(stack.pop() - tmp);
            } else if (t.equals("*")) {
                int tmp = stack.pop();
                stack.push(stack.pop() * tmp);
            } else if (t.equals("/")) {
                int tmp = stack.pop();
                stack.push(stack.pop() / tmp);
            } else {
                stack.push(Integer.parseInt(t));
            }
        }
        return stack.pop();
    }
}

Python:

python也可以用数组代替栈完成上述方法解答本题。这里用另一个函数 eval() 代替上述四个 if 判断：

class Solution:
    def evalRPN(self, tokens: List[str]) -> int:
        stack = []
        for t in tokens:
            if t in "+-*/":
                tmp = stack.pop()
                stack.append(int(eval("stack.pop()" + t + "tmp")))
            else:
                stack.append(int(t))
        return stack.pop()

eval() 函数可以执行传入参数字符串语句。

如 eval("print("hhhhh")") 会执行参数字符串打印出hhhhh

欢迎大家关注微.信公.众号：爱写Bug

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

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

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

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

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

104828720 2019-08-23 16:56 评论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
表达式类算法题小结

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

Heier 2019-08-16 10:32 评论0 收藏0
leetcode150. Evaluate Reverse Polish Notation

摘要：我们一般看到的数学表达式就是中缀表达式，也就是将符号放在两个数字之间。后缀表达式也就是将运算符放在相应数字的后面。后缀表达式相当于树中的后序遍历。通过获得对应位置的操作符。如果对应的还是操作符，则继续递归往前计算。题目要求 Evaluate the value of an arithmetic expression in Reverse Polish Notation. Valid...

bitkylin 2019-08-16 10:40 评论0 收藏0
[LeetCode] 150. Evaluate Reverse Polish Notation

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

KoreyLee 2019-08-16 13:59 评论0 收藏0