Explicit Thought Process without stack & Boilerplate code in Java


  • 0
    P

    Thought Process:
    Example 1: calculate(2+2*3) can be sectioned into 2 + calculate(2*3).
    The idea is: for + & -operation, we can recursively calling calculate(subString) function. Yes, you get it, it will be a DFS.
    for *& /operation, it is in-place operation: we get the result without calling calculate().

    Example 2: 2+3*4+4*5 the result is achieved by the following processes:

    1. 2 + calculate(3*4+4*5)
    2. And calculate(3*4+4*5) will be achieved by 12 + calculate(4*5). 12 is computed from 3*4 in place.
    3. And calculate(4*5)will be achieved by 4*5 in place.

    And finally it is the code:

    public int calculate(String s) {
            if(s == "" || s == " ") return 0;        
            
            // the following variables will be used for multiply/divide operation 
            int op1 = 0;
            int op2 = 0;
            boolean fop = false;
            char optype = '0';	
            
            // these two used for addition/subtraction operation 
            int left = 0;
            int right = 0;
            
            for(int i = 0; i < s.length(); i++) {
            	switch(s.charAt(i)) {
            		case '\0': 		// should be considered for SPACE character
            			break;
            		case '+':
            		case '-':
            			if(fop == true){
            				left = (optype == '*') ? (op1 * op2) : (op1 / op2);
            			}   
            			else 
            				left = op1;
            			right = calculate(s.substring(i+1, s.length()));
            			return (s.charAt(i) == '+') ? left + right : left - right;
            		case '*':
            		case '/':
            			optype = s.charAt(i);
            			fop = true;
            			break;
            		default: 
            			if(fop == false)
            				op1 = op1 * 10 + s.charAt(i) - '0';
            			else 
            				op2 = op2 * 10 + s.charAt(i) - '0';
            			break;   			
            	}
            }
            
            if(fop==false) 		// for string only contains digit "234"
            	return op1;
            else 				// for string only contains multiply/divide operation, like "2*2"
            	return (optype == '*') ? (op1 * op2) : (op1 / op2);	
        }
    

    I called it the Boilerplate code simply because:

    1. For SPACE, need more tweet.
    2. For ( & ), need more tweet.
    3. It is possible to eliminate left & rightvariable and use op1 & op2. I simply don't like to sacrifice the readability.

    And I will tag this problem as String and DFS.

    Time Complexity:

    1. Come to the idea: 5 mins.
    2. Key in the code: 10 mins.
    3. Tweet the code that can run run relatively complex string: 10 mins.
    4. Refine the code: 10 mins.
    5. Post my solution: 30 mins.

    If you read here, it is a great honor for me. Thank you.


Log in to reply
 

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