X

LEETCODE 150. Evaluate Reverse Polish Notation 解题思路分析

题目大意:

逆波兰表达式求值

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

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

说明:

  • 整数除法只保留整数部分。
  • 给定逆波兰表达式总是有效的。换句话说,表达式总会得出有效数值且不存在除数为 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
 = 2

如果想查看本题目是哪家公司的面试题,请参考以下免费链接: https://leetcode.jp/problemdetail.php?id=150

解题思路分析:

关于逆波兰表达式的定义大家可以参考:

关于本题,这是一道典型的Stack题目,我们从数组首位向后逐一循环,如果当前字符是数字,我们将它push进栈,如果是运算符号,我们就从Stack中取出2个元素a和b,然后用当前符号对a和b进行运算,运算结果再push进栈。这里需要注意一点,从Stack中pop出2个元素a和b时,Stack基于先进后出的原则,先pop出的a实际上是在后pop出的b的后面,所以,计算时应该用b(+-*/)a,不要写反。

最后循环完所有字符串,Stack中应该剩下唯一一个数值,该数值即是返回结果。

实现代码:

public int evalRPN(String[] tokens) {
    Stack<Integer> stack = new Stack<>();
    // 循环每一个字符串
    for(String s : tokens){
        // 如果当前字符串是运算符号
        if(s.equals("+")||s.equals("-")||s.equals("*")||s.equals("/")){
            // 从Stack取出两个数字
            int a=stack.pop();
            int b=stack.pop();
            // 根据符号对两个数字进行运算,并将运算结果存入Stack
            if(s.equals("+")) stack.push(b+a);
            if(s.equals("-")) stack.push(b-a);
            if(s.equals("*")) stack.push(b*a);
            if(s.equals("/")) stack.push(b/a);
        }else{
            // 如果当前字符串是数字,存入Stack
            stack.push(Integer.valueOf(s));
        }
    }
    // Stack中最后剩下的数字是返回结果。
    if(stack.size()>0) return stack.pop();
    return 0;
}

本题解法执行时间为6ms。

Runtime: 6 ms, faster than 74.91% of Java online submissions for Evaluate Reverse Polish Notation.

Memory Usage: 46.7 MB, less than 6.00% of Java online submissions for Evaluate Reverse Polish Notation.

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: http://leetcode.jp/leetcode-150-evaluate-reverse-polish-notation-解题思路分析/
Categories: leetcode
kwantong: