原题链接在这里:https://leetcode.com/problems/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.
Example 1:
Input: "3+2*2"
Output: 7
Example 2:
Input: " 3/2 "
Output: 1
Example 3:
Input: " 3+5 / 2 "
Output: 5
Note:
- You may assume that the given expression is always valid.
- Do not use the
eval
built-in library function.
题解:
It could apply the generic method. Use two level of operations. Calculate * and / first, accumlate the result into num2.
Then + and -, accumlate the result into num1.
When current char is digit, get the current number, perform * and /.
If current char is * and /, update operator 2.
If current char is + and -, perform previous + and - operation and update operator 1, reset num2, operator 2.
Time Complexity: O(n). n = s.length().
Space: O(1).
AC Java:
class Solution {
public int calculate(String s) {
if(s == null || s.length() == 0){
return 0;
} int num1 = 0;
int o1 = 1;
int num2 = 1;
int o2 = 1;
for(int i = 0; i<s.length(); i++){
char c = s.charAt(i);
if(Character.isDigit(c)){
int cur = c - '0';
while(i+1 < s.length() && Character.isDigit(s.charAt(i+1))){
cur = cur * 10 + s.charAt(i+1)-'0';
i++;
} num2 = o2 == 1 ? num2 * cur : num2 / cur;
}else if(c == '*' || c == '/'){
o2 = c == '*' ? 1 : -1;
}else if(c == '+' || c == '-'){
num1 = num1 + o1 * num2;
o1 = c == '+' ? 1 : -1; num2 = 1;
o2 = 1;
}
} return num1 + o1 * num2;
}
}