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.Have you met this question in a real interview? YesProblem Correction

Clarification

什么是逆波兰表达式？

• http://en.wikipedia.org/wiki/Reverse_Polish_notation

Example

["2", "1", "+", "3", "*"] -> ((2 + 1) * 3) -> 9
["4", "13", "5", "/", "+"] -> (4 + (13 / 5)) -> 6

注意计算的执行顺序，先pop出来的数应该在运算的前面

时间复杂度 o(n) 空间复杂度 o(k),k == nums

public class Solution {
    /**
     * @param tokens: The Reverse Polish Notation
     * @return: the value
     */
    public int evalRPN(String[] tokens) {
        // write your code here
        
        if(tokens == null || tokens.length == 0){
            return 0;
        }
        
        
        Stack<Integer> stack = new Stack<>();
        
        for (int i = 0; i < tokens.length ;i++ ){
            if(!isOperator(tokens[i])){
                stack.push(Integer.parseInt(tokens[i]));
            }else{
                int a = 0, b = 0;
                if(stack.size() >= 2){
                    a = stack.pop();
                    b = stack.pop();
                }
                
                
                if(tokens[i].equals("+")){
                    stack.push(b+a);
                }else if(tokens[i].equals("-")){
                    stack.push(b-a);
                }else if(tokens[i].equals("*")){
                    stack.push(b*a);
                }else if(tokens[i].equals("/")){
                    stack.push(b/a);
                }
                
            }
        } 
        
        return stack.pop();
        
    }
    
    
    public boolean isOperator(String s){
        if(s.equals("+") || s.equals("-") ||s.equals("*") || s.equals("/"))
            return true;
            
        else 
            return false;
    }
    
    
}

class Solution {
    public int evalRPN(String[] tokens) {
        if(tokens == null || tokens.length == 0)
            return -1;
        
        Stack<Integer> stack = new Stack<>();
        
        String operators = "+-*/";
        
        for(String s : tokens){
            if(!operators.contains(s)){
                stack.push(Integer.parseInt(s));
            }
            
            else{
                int a = 0, b = 0;
                if(stack.size() >= 2){
                    a = stack.pop();
                    b = stack.pop();
                }
                if(s.equals("+")){
                    stack.push(a+b);
                }
                else if(s.equals("-")){
                    stack.push(b-a);
                }
                else if(s.equals("*")){
                    stack.push(a*b);
                }else{
                    stack.push(b/a);
                }
            }
        }
        
        return stack.pop();
    }
}

有阶乘的版本 factorial

class Solution {
    public int evalRPN(String[] tokens) {
        if(tokens == null || tokens.length == 0) return -1;
        
       String operators = "+-*/!";
        Stack<Integer> stack = new Stack<>();
        for(String s : tokens){
            if(!operators.contains(s)){
                stack.push(Integer.parseInt(s));
            }
            else if(s.equals("!")){
                int a = 0;
                if(stack.size() >= 1){
                    a = stack.pop();
                  int res = 1;
                    
                    for(int i = 1; i <= a;i++){
                        res *= i;
                    }
                    
                    stack.push(res);
                }
                else 
                    return -1;
            }else{
                int a = 0, b = 0;
                
                if(stack.size() >= 2){
                    a = stack.pop();
                    b = stack.pop();
                }
                
                if(s.equals("+")){
                    stack.push(a+b);
                }
                
                else if(s.equals("-")){
                    stack.push(b-a);
                }else if(s.equals("*")){
                    stack.push(a*b);
                }else{
                    stack.push(b/a);
                }
            }
        }
        
        return stack.pop();
        
    }
}