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.
Solution:
class Solution {
public int calculate(String s) {
if (s == null || s.length() == 0) {
return 0;
}
Deque<Integer> stack = new ArrayDeque<>();
int num = 0;
char prevSign = '+';
for (int i = 0; i < s.length(); i ++) {
char c = s.charAt(i);
if (Character.isDigit(c)) {
num = num * 10 + c - '0';
}
if (!Character.isDigit(c) && c != ' ' || i == s.length() - 1) {
switch(prevSign) {
case '+':
stack.push(num);
break;
case '-':
stack.push(-num);
break;
case '*':
stack.push(stack.pop() * num);
break;
case '/':
stack.push(stack.pop() / num);
break;
}
num = 0;
prevSign = c;
}
}
int res = 0;
while (!stack.isEmpty()) res += stack.pop();
return res;
}
}