首页 > 其他 > 详细

[LeetCode]Evaluate Reverse Polish Notation, 解题报告

时间:2014-04-18 18:10:38      阅读:516      评论:0      收藏:0      [点我收藏+]

前言

昨天终于项目完成,历时一个多月的时间,解决了Android上内存泄露和各种ANR问题,今天终于有时间写点ACM题目了。

题目

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:

bubuko.com,布布扣


思路

这道题目还是挺奇怪的,读完题目赶紧非常简单,但是LeetCode上的AC率只有19%,尝试第一次提交代码就ac了,有点无语,这里记录一下逆波兰表达式的概念吧。

逆波兰表示法(Reverse Polish notation,RPN,或逆波兰记法),是一种是由波兰数学家扬·武卡谢维奇1920年引入的数学表达式方式,在逆波兰记法中,所有操作符置于操作数的后面,因此也被称为后缀表示法。逆波兰记法不需要括号来标识操作符的优先级。

逆波兰结构由弗里德里希·鲍尔(Friedrich L. Bauer)和艾兹格·迪科斯彻在1960年代早期提议用于表达式求值,以利用堆栈结构和减少计算机内存访问。逆波兰记法和相应的算法由澳大利亚哲学家、计算机学家查尔斯·汉布林(Charles Hamblin)在1960年代中期扩充。

逆波兰表达式的解释器一般是基于堆栈的。解释过程一般是:操作数入栈;遇到操作符时,操作数出栈,求值,将结果入栈;当一遍后,栈顶就是表达式的值。因此逆波兰表达式的求值使用堆栈结构很容易实现,和能很快求值。


AC代码

以第一次ac的代码为准吧,比较丑陋,很多可以优化的地方。

public class Solution {
    public static int evalRPN(String[] tokens) {
        int num1, num2, res = 0;
        Stack<String> stack = new Stack<String>();

        for (int i = 0; i < tokens.length; i++) {
            if (tokens[i].equals("+")) {
                num1 = Integer.parseInt(stack.pop());
                num2 = Integer.parseInt(stack.pop());
                res = num1 + num2;
                stack.push(String.valueOf(res));
            } else if (tokens[i].equals("-")) {
                num1 = Integer.parseInt(stack.pop());
                num2 = Integer.parseInt(stack.pop());
                res = num2 - num1;
                stack.push(String.valueOf(res));
            } else if (tokens[i].equals("*")) {
                num1 = Integer.parseInt(stack.pop());
                num2 = Integer.parseInt(stack.pop());
                res = num1 * num2;
                stack.push(String.valueOf(res));
            } else if (tokens[i].equals("/")) {
                num1 = Integer.parseInt(stack.pop());
                num2 = Integer.parseInt(stack.pop());
                res = num2 / num1;
                stack.push(String.valueOf(res));
            } else {
                stack.push(tokens[i]);
            }
        }

        return Integer.parseInt(stack.pop());
    }
}


[LeetCode]Evaluate Reverse Polish Notation, 解题报告,布布扣,bubuko.com

[LeetCode]Evaluate Reverse Polish Notation, 解题报告

原文:http://blog.csdn.net/wzy_1988/article/details/23999583

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!