2015年11月3日星期二

Leetcode 227 Basic Calculator II

Implement a basic calculator to evaluate a simple expression string.
The expression string contains only non-negative integers, +-*/ operators and empty spaces . The integer division should truncate toward zero.
You may assume that the given expression is always valid.
Some examples:
"3+2*2" = 7
" 3/2 " = 1
" 3+5 / 2 " = 5
Note: Do not use the eval built-in library function.
Solution 1: O(n) complexity and O(1) space
 public class Solution {  
   public int calculate(String s) {  
     int n=s.length();  
     int pre=0, curr=1;   
     boolean blank=true; //if s only contains ' '  
     boolean preSign=true, sign=true; //preSign: + or -; sign: * or /  
     for (int i=0; i<n; i++) {  
       if (s.charAt(i)==' ') continue;  
       else if (s.charAt(i)=='*') sign=true;  
       else if (s.charAt(i)=='/') sign=false;  
       else if (s.charAt(i)=='+' || s.charAt(i)=='-') {  
         pre=preSign? pre+curr:pre-curr;  
         preSign=s.charAt(i)=='+';  
         curr=1;  
         sign=true;  
       }  
       else {  
         blank=false;  
         int j=i+1;  
         while (j<n && s.charAt(j)>='0' && s.charAt(j)<='9') j++;  
         curr=sign? curr*Integer.valueOf(s.substring(i,j)):curr/Integer.valueOf(s.substring(i,j));  
         i=j-1;  
       }  
     }  
     if (blank) return 0;  
     return preSign? pre+curr:pre-curr;  
   }  
 }  

没有评论:

发表评论