2017-06-06 01:35:03 +0000   |     algorithm leetcode stack   |   Viewed times   |    

题目

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

Stack缓存数字

原理很简单,用一个Stack缓存多有读到过的数字,遇到+-*/计算符号,就从Stack里读出最后压入的两个数进行计算,然后再将结果压入Stack.

这题需要注意String间的比较不要用==,而是equals()比较好。 因为不同版本的Java可能对字符串常量池的处理不同,有的不保证两个值相等的字符串就是同一个对象。用equals()可以避免这个麻烦。

另一个需要注意的是switch语法,对Stringswitch是Java 7才引入的特性,如果leetcode用的Java版本过低,会导致无法通过。

代码

这是 带防御 的版本。

public class Solution {
    public int evalRPN(String[] tokens) {
        Deque<Integer> stack = new LinkedList<>();
        for (String token : tokens) {
            try {
                stack.offerFirst(Integer.parseInt(token));
            } catch (NumberFormatException e) {
                if (isOperator(token) && stack.size() >= 2) {
                    int b = stack.pollFirst();
                    int a = stack.pollFirst();
                    stack.offerFirst(calculate(a,b,token));
                } else { // 格式不对
                    return 0;
                }
            }
        }
        int size = stack.size();
        if (size == 0 || size > 1) { return 0; } // stack必须只能有结果一个值
        return stack.pollFirst();
    }
    private int calculate(int a, int b, String token) {
        if (token.equals("+")) {
            return a + b;
        } else if (token.equals("-")) {
            return a - b;
        } else if (token.equals("*")) {
            return a * b;
        } else if (token.equals("/")) {
            return a / b;
        } else {
            return 0;
        }
    }
    private boolean isOperator(String s) {
        return (s.equals("+")) || (s.equals("-")) || (s.equals("*")) || (s.equals("/"));
    }
}

结果

evaluate-reverse-polish-notation-1

防御性编程,尤其是try-catch影响了效率

假设String[]中的元素格式,数量,顺序都合法,去掉所有的格式检查。

代码

下面是 不带防御 的版本。

public class Solution {
    public int evalRPN(String[] tokens) {
        Deque<Integer> stack = new LinkedList<>();
        for (String token : tokens) {
            if (token.equals("+") || token.equals("-") || token.equals("*") || token.equals("/")) {
                int b = stack.pollFirst();
                int a = stack.pollFirst();
                stack.offerFirst(calculate(a,b,token));
            } else {
                stack.offerFirst(Integer.parseInt(token));
            }
        }
        return stack.pollFirst();
    }
    public int calculate(int a, int b, String token) {
        if (token.equals("+")) {
            return a + b;
        } else if (token.equals("-")) {
            return a - b;
        } else if (token.equals("*")) {
            return a * b;
        } else if (token.equals("/")) {
            return a / b;
        } else {
            return 0;
        }
    }
}

结果

银弹! evaluate-reverse-polish-notation-2