首页 > 代码库 > Leetcode: Evaluate Reverse Polish Notation
Leetcode: 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
难度：70. RPN中文名字叫做逆波兰表示法，它的好处维基百科说了，就是不需要括号来表示运算的先后，直接根据式子本身就可以求解。解题思路就是维护一个栈，遇到数字就入栈，遇到操作符就两次出栈得到栈顶的两个操作数，运用操作符进行运算以后，再把结果入栈。直到式子结束，此时栈中唯一一个元素便是结果。
以上代码中有一个没有周全的地方是没有对逆波兰式错误的情况进行出错处理，其实也不难，就是每次pop操作检查栈空情况，如果栈空，则说明出错，throw an exception。还有就是最后检查一下栈的size，如果不是1也说明运算数多了，返回错误。
1 public class Solution { 2 public int evalRPN(String[] tokens) { 3 if (tokens==null || tokens.length==0) return 0; 4 LinkedList<Integer> stack = new LinkedList<Integer>(); 5 for (int i=0; i<tokens.length; i++) { 6 if (tokens[i].equals("+") || tokens[i].equals("-") || tokens[i].equals("*") || tokens[i].equals("/")) { 7 if (stack.isEmpty()) return 0; 8 int operand1 = stack.pop(); 9 if (stack.isEmpty()) return 0;10 int operand2 = stack.pop();11 if (tokens[i].equals("+")) stack.push(operand2 + operand1);12 if (tokens[i].equals("-")) stack.push(operand2 - operand1);13 if (tokens[i].equals("*")) stack.push(operand2 * operand1);14 if (tokens[i].equals("/")) stack.push(operand2 / operand1);15 }16 else {17 stack.push(Integer.parseInt(tokens[i]));18 }19 }20 return stack.peek();21 }22 }
Leetcode: Evaluate Reverse Polish Notation
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。