2ms beats 100% recursive solution with java.


  • 0
    X
    public class Solution {
    	public int evalRPN(String[] tokens) {
    	    if(tokens.length==1)return toInt(tokens[0]);
    	    
    		this.tokens = tokens;
    		this.curs	= tokens.length - 1;
    		return subEvalRPN();
    	}
    
    	private String[] tokens;
    	private int		 curs;
    
    
    	private int subEvalRPN() {
    		int	 b, a;
    // 		int curss=curs;
    		char operator = tokens[curs--].charAt(0);
    
    		if ( isNumber() ) { b = toInt(tokens[curs--]); }
    		else { b = subEvalRPN(); }
    		if ( isNumber() ) { a = toInt(tokens[curs--]); }
    		else { a = subEvalRPN(); }
    		
    // 		System.out.println("subExp "+curss+" through "+(curs+1)+" is evaluated to "+a+operator+b);
    
    		switch (operator) {
    			case '+':
    				return a + b;
    
    			case '-':
    				return a - b;
    
    			case '*':
    				return a * b;
    
    			case '/':
    				return a / b;
    
    			default:
    				return 0;
    		}
    	}
    	
    	private int toInt(String s){
    	    int i=0;
    	    int len=s.length();
    	    int ret=0;
    	    boolean neg=false;
    	    if(s.charAt(0)=='-'){i++;neg=true;}
    	    for(;i<len;i++){ret*=10;ret+=s.charAt(i)-'0';}
    	    return neg?-ret:ret;
    	    
    	}
    
    	private boolean isNumber() {
    		char tmp;
    
    		return ( tmp = tokens[curs].charAt(tokens[curs].length()-1) ) >= '0' && tmp <= '9';
    	}
    }
    

    well, just recursively call the subEvalRPN().

    the toInt() function is to speed up the program, turns out Integer.parseInt() is too slow.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.