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;
}
}
没有评论:
发表评论