|
1
2
3
4
5
6
7
8
9
|
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 " = 5Note: Do not use the eval built-in library function. |
题意：求值
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
|
public class Solution {
public int calculate(String s) {
int digt=0;
char op='+';
int res=0;
int n=s.length();
Stack<Integer> stack=new Stack<>();
for(int i=0;i<n;i++){
if(s.charAt(i)>='0' && s.charAt(i)<='9')
digt=digt*10+s.charAt(i)-'0';
int temp=digt;
if(s.charAt(i)=='+' || s.charAt(i)=='-' || s.charAt(i)=='*' || s.charAt(i)=='/' || i==n-1){
switch(op){
case '+':stack.push(digt);break;
case '-':stack.push(-digt);break;
case '*':stack.push(stack.pop()*digt);break;
case '/':stack.push(stack.pop()/digt);break;
}
op=s.charAt(i);
digt=0;
}
}
while(!stack.empty()){
res+=stack.pop();
}
return res;
}
} |
PS:
Stack
-
定义一个temp 的stack来保存运算的操作数（包括中间的运算值）
-
d 来保存上一个操作数
-
op 来保存上一个操作数，不是当前的操作数
-
遍历字符串
-
如果是数字，入 stack
-
如果是操作符
-
+: 将 +d 存入stack
-
-: 将 -d 存入 stack
-
* : 将 stack 的top值与 d 的乘积存入 stack
-
/: 将 stack 的top 值与 d 的除值 存入 stack
-
-
空间复杂度是 O(N), 时间复杂度是 O(N)。需要注意的是：每次操作数入栈的时间是下一个操作符的时候，有点类似与延迟运算，所以需要把最近的操作数和操作符存入两个额外的变量。还有一个小技巧，如果我们给字符串的前面和后面分别增加一个'+'操作符，可以减少代码的复杂度。如 "1+2*3" 修改成 "+1+2*3+ "。
本文转自 努力的C 51CTO博客，原文链接:http://blog.51cto.com/fulin0532/1902777