Leetcode: 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.

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来做：时间 O(N) 空间 O(N) 因为乘法和除法不仅要知道下一个数，也要知道上一个数。所以我们用一个栈把上次的数存起来，遇到加减法就直接将数字压入栈中，遇到乘除法就把栈顶拿出来乘或除一下新数，再压回去。最后我们把栈里所有数加起来就行了。

 1 public class Solution {
 2     public int calculate(String s) {
 3         int res = 0;
 4         int num = 0;
 5         char sign = '+';
 6         Stack<Integer> st = new Stack<>();
 7         for (int i=0; i<s.length(); i++) {
 8             char c = s.charAt(i);
 9             if (Character.isDigit(c)) {
10                 num = num * 10 + (int)(c - '0');
11             }
12             if(!Character.isDigit(c) && c!=' ' || i==s.length()-1) {
13                 switch(sign) {
14                     case '+': st.push(num); break;
15                     case '-': st.push(-1*num); break;
16                     case '*': st.push(st.pop()*num); break;
17                     case '/': st.push(st.pop()/num); break;
18                 }
19                 num = 0;
20                 sign = c;
21             }
22         }
23         
24         while (!st.isEmpty()) {
25             res += st.pop();
26         }
27         return res;
28     }
29 }

上面这段code可以先用String.replace()去掉所有的空格

如：

s = s.replace(" ", "");

临时变量法

复杂度

时间 O(N) 空间 O(1)

思路

这题很像Expression Add Operator。因为没有括号，其实我们也可以不用栈。首先维护一个当前的结果，加减法的时候，直接把下一个数加上或减去就行了。

乘除法比如2+3*4，当算完3时，结果是5，当算到4时，先用5-3=2，再用2+3*4=14，注意preVal此时更新为12

 1 public class Solution {
 2     public int calculate(String s) {
 3         if (s==null || s.length()==0) return 0;
 4         int num = 0;
 5         int sum = 0;
 6         char sign = '+';
 7         int preVal = 0;
 8         for (int i=0; i<s.length(); i++) {
 9             char cur = s.charAt(i);
10             if (Character.isDigit(cur)) {
11                 num = num*10 + (int)(cur-'0');
12             }
13             if (!Character.isDigit(cur) && cur!=' ' || i==s.length()-1) {
14                 if (sign == '+') {
15                     sum = sum + num;
16                     preVal = num;
17                 }
18                 if (sign == '-') {
19                     sum -= num;
20                     preVal = -num;
21                 }
22                 if (sign == '*') {
23                     sum = sum-preVal+preVal*num;
24                     preVal = preVal*num;
25                 }
26                 if (sign == '/') {
27                     sum = sum-preVal+preVal/num;
28                     preVal = preVal/num;
29                 }
30                 sign = cur;
31                 num = 0;
32             }
33         }
34         return sum;
35     }
36 }