### 题目

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.

### 利用Stack

1. 遇到+,-,*,/符号，就记录下来，作为当前符号
2. 遇到[0-9]数字，就把连续的数字读出来，然后根据当前符号，做相应的动作。
• 当前符号为+: 直接把数字压入栈
• 当前符号为-: 栈中压入数字的相反数。
• 当前符号为*: 弹出栈顶数字，和当前数字相乘，把结果压到栈顶。
• 当前符号为/: 弹出栈顶数字，除以当前数字，把结果压到栈顶。
3. 遇到空格 ，什么都不做，跳过。

#### 代码

public class Solution {
public int calculate(String s) {
char[] chars = s.toCharArray();
int cur = 0;
char oprt = '+';
while (cur < chars.length) {
switch (chars[cur]) {
case ' ': cur++; break;
case '+': cur++; break;
case '-': oprt = '-'; cur++; break;
case '*': oprt = '*'; cur++; break;
case '/': oprt = '/'; cur++; break;
default: // [0-9]
int[] pair = parseNum(chars,cur);
cur = pair[1];
switch (oprt) {
case '-': stack.push(0 - (long)pair[0]); break;
case '*': stack.push(stack.pop() * pair[0]); break;
case '/': stack.push(stack.pop() / pair[0]); break;
default: stack.push((long)pair[0]); break; // +
}
oprt = '+';
}
}
long sum = 0;
for (long n : stack) { sum += n; }
return (int)sum;
}
private int[] parseNum(char[] chars, int cur) {
int[] result = new int[2];
int num = 0;
while (cur < chars.length && chars[cur] >= '0' && chars[cur] <= '9') {
num = num * 10 + (chars[cur++] - '0');
}
result[0] = num; result[1] = cur;
return result;
}
}