2015年10月15日星期四

Leetcode 150 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

Solution 1: Use stack, when it is symbol, get two number out and do the calculation then put it back. if it is number then simply put in stack.
 public class Solution {  
   public int evalRPN(String[] tokens) {  
     Deque<Integer> stack=new LinkedList<>();  
     for (String s: tokens) {  
       if (s.equals("+")) stack.push(stack.pop()+stack.pop());  
       else if (s.equals("-")) {  
         int temp=stack.pop();  
         stack.push(stack.pop()-temp);  
       }  
       else if (s.equals("*")) stack.push(stack.pop()*stack.pop());  
       else if (s.equals("/")) {  
         int temp=stack.pop();  
         stack.push(stack.pop()/temp);  
       }  
       else stack.push(Integer.valueOf(s));  
     }  
     return stack.pop();  
   }  
 }  

没有评论:

发表评论