My simple and intuitive recursive 17ms solution


  • 0
    X
    public class Solution {
    	public int calculate(String s) {
    		this.s = s;
    		len=s.length();
    		curs   = 0;
    		return subCalc();
    	}
    
    	//call this when curs is right after a '(', returns the result of the subexpression starting at curs, and moves curs to the char right after the closing '('.
    	private int subCalc() {
    		int		sum	 = 0;
    		boolean sign = true;
    
    		// int pcurs=curs;//debug use
    		while (true) {
    			char tmp;
    			if ((curs >= len) || ((tmp = s.charAt(curs)) == ')')) {
    				// System.out.println("SubExp "+s.substring(pcurs,curs)+" is evaluated to "+sum);
    				curs++;
    				return sum;
    			}
    			if (tmp == ' ') { curs++; continue; }
    			if (tmp == '+') { sign = true; curs++; continue; }
    			if (tmp == '-') { sign = false; curs++; continue; }
    			sum += sign ? monomCalc() : -monomCalc();
    		}
    	}
    
    	//call this when curs is right at the begining of a monomial.
    	private int monomCalc() {
    		int		prod = 1;
    		boolean inv	 = false;
    
    		// int pcurs=curs;//debug use
    		while (true) {
    			char tmp;
    			if ((curs >= len) || ((tmp = s.charAt(curs)) == '+') || (tmp == '-') || (tmp == ')')) {
    				// System.out.println("Monomial "+s.substring(pcurs,curs)+" is evaluated to "+prod);
    				return prod;
    			}
    			if (tmp == ' ') { curs++; continue; }
    			if (tmp == '(') { curs++; prod = inv ? (prod / subCalc()) : (prod * subCalc()); continue; }
    			if (tmp == '*') { inv = false; curs++; continue; }
    			if (tmp == '/') { inv = true; curs++; continue; }
    			prod = inv ? (prod / nextInt()) : (prod * nextInt());
    		}
    	}
    
    	private String s;
    	private int	   curs = 0,len;
    
    
    	private int nextInt() {
    		int ret = 0;
    		char tmp;
    
    		while (curs < len && (tmp=s.charAt(curs)) >= '0' && tmp <= '9') {
    			ret *= 10;
    			ret += tmp - '0';
    			curs++;
    		}
    		return ret;
    	}
    }
    

    Well, Everything is so clear with recursion.
    There are two main functions:
    subCalculate(): to calculate subExpressions enclosed in parentheses;
    monomialCalc(): to calculate monomials (refers to an expression with only * and / at the root level).

    the recursion structure automatically forms a tree.

    It's not quick but a lot of the code can be optimized I think, for example the nextInt() function is very costly, please suggest me of a way to improve.

    It beats 92% after some optimizations of code.


Log in to reply
 

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