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.

用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
     
       st = new Stack<>(); 7         for (int i=0; i
     

 

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

如：

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

 

临时变量法

复杂度

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

思路

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

乘除法比如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