Simple intuitive O(n) recursive java solution


  • 0
    C
    public int calculate(String s) {
            return helper(0, s, new int[1]);
        }
        private int helper(int start, String s, int[] nextPos){
            int pt = start, cur = 0, val = 0;
            int sign = 1;
            while(pt < s.length()){
                if(s.charAt(pt) == ' ') pt++;
                else if(s.charAt(pt) >= '0' && s.charAt(pt) <= '9')
                    cur = cur * 10 + (s.charAt(pt++) - '0');
                else{
                    val += sign * cur;
                    cur = 0;
                    if(s.charAt(pt) == '+'){
                        sign = 1;
                        pt++;
                    }else if(s.charAt(pt) == '-'){
                        sign = -1;
                        pt++;
                    }else if(s.charAt(pt) == '('){
                        val += sign * helper(pt+1, s, nextPos);
                        pt = nextPos[0];
                    }else if(s.charAt(pt) == ')'){
                        nextPos[0] = pt+1;
                        return val;
                    }
                }
            }
            val += sign * cur;
            return val;
        }
    

Log in to reply
 

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