Java O(n) solution, beat 90%


  • 0
    M
        public int calculate(String s) {
            if(s==null || s.length()==0) return 0;
            final int N = s.length();
            Stack<Integer> stack = new Stack<>();
            char op = '+';
            for(int i=0; i<N; i++){
                char ch = s.charAt(i);
                if(ch<='9' && ch>='0') { //digit
                    long num = 0;
                    while(i<N && ch<='9' && ch>='0') {
                        num = num*10 + ch-'0';
                        if(i==N-1) break;
                        ch = s.charAt(++i);
                    }
                    // do operation
                    if(op=='-') {
                        num = -num;
                    } else if(op=='*') {
                        num *= stack.pop();
                    } else if(op=='/') {
                        num = stack.pop() / num;
                    }
                    stack.push((int)num);
                } 
                if(ch!=' '){ //update operation
                    op = ch;
                }
            }
            int res = 0;
            for(int val : stack)
                res += val;
            return res;
        }
    

Log in to reply
 

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