首页 > 代码库 > [leecode]Evaluate Reverse Polish Notation

[leecode]Evaluate Reverse Polish Notation

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 

算法思路:

很经典的stack应用,书中例题,遇到数字压栈,遇到符号弹栈,并将结果压栈,最后返回栈顶元素。

 1 public class Solution { 2     public int evalRPN(String[] tokens) { 3         if(tokens == null || tokens.length == 0) return 0; 4         String[] operand = new String[]{"+","-","*","/"}; 5         Set<String> set = new HashSet<String>(Arrays.asList(operand)); 6         Stack<Integer> num = new Stack<Integer>(); 7         for(String s : tokens){ 8             if(!set.contains(s)){ 9                 num.push(Integer.valueOf(s));10             }else{11                 int b = num.pop();12                 int a = num.pop();13                 switch(s){14                     case "*": num.push(a * b); break;15                     case "+": num.push(a + b); break;16                     case "-": num.push(a - b); break;17                     case "/": num.push(a / b); break;18                     default : break;19                 }20             }21         }22         return num.pop();23     }24 }