[Leetcode] Evaluate Reverse Polish Notation 计算逆波兰表

ephererid 发布于2019-08-14 12:40 / 1543人阅读

摘要：栈法复杂度时间空间思路逆波兰表达式的计算十分方便，对于运算符，其运算的两个数就是这个运算符前面的两个数。注意对于减法，先弹出的是减号后面的数。

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.
Some examples:
  ["2", "1", "+", "3", "*"] -> ((2 + 1) * 3) -> 9
  ["4", "13", "5", "/", "+"] -> (4 + (13 / 5)) -> 6

栈法 复杂度

时间 O(N) 空间 O(N)

思路

逆波兰表达式的计算十分方便，对于运算符，其运算的两个数就是这个运算符前面的两个数。所以我们只要用一个栈，每次遇到数字就压入栈内，每次遇到运算符就弹出两个数，计算后再压回栈内，最后栈内剩下的那个数就是计算结果了。

注意

对于减法，先弹出的是减号后面的数。对于除法，先弹出的是除号后面的数。

代码

public class Solution {
    public int evalRPN(String[] tokens) {
        Stack stk = new Stack();
        for(String token : tokens){
            switch(token){
                case "+":
                    stk.push(stk.pop() + stk.pop());
                    break;
                case "-":
                    stk.push(-stk.pop() + stk.pop());
                    break;
                case "/":
                    int num1 = stk.pop();
                    int num2 = stk.pop();
                    stk.push(num2 / num1);
                    break;
                case "*":
                    stk.push(stk.pop() * stk.pop());
                    break;
                default:
                    stk.push(Integer.parseInt(token));
            }
        }
        return stk.pop();
    }
}

私有云云服务器逆波兰式逆波兰表示法逆波兰式算法c语言 Polish

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

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

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

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

Turbo 2019-08-19 10:19 评论0 收藏0
LeetCode 之 JavaScript 解答第150题 —— 逆波兰表达式求值

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

104828720 2019-08-23 16:56 评论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