227. 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.

这个跟I比起来只有'+' '-' '*' '/',还是先在第一个数字之前加上'+'
解题主要思路：每次将数字和数字前的'+' '-'看成是正负号，利用一个栈，
1、如果这个数字的后一个符号不是'*'/'是加减，那么每次将正负数入栈。
2、如果这个数字的后一个符号是'*' '/',那么将栈顶元素出栈与之计算，然后再将结果入栈。
3、计算到最后，将栈内一系列的num求和即可。

 1 class Solution {
 2 public:
 3     int calculate(string s) {
 4        if(s.size()==0) return 0;
 5         int i=0;
 6         stack<int> st;
 7         char sign='+';
 8         int num=0;
 9         //+1+2-3-4*5/6+7
10         while(i<s.size())
11         {
12             if(isdigit(s[i]))
13             {
14                 num=num*10+s[i]-'0';
15             }
16             if(!isdigit(s[i])&&s[i]!=' '||i==s.size()-1)//i==s.size()-1还会有一个数字s[i]和前一个符号要去计算.所以不能是else if .防止i==s.size()-1的时候漏算
17             {
18                 if(sign=='+') 
19                     st.push(num);
20                 else if(sign=='-')
21                     st.push(-num);
22                 else if(sign=='*')
23                 {
24                     st.top()*=num;
25 
26                 }
27                 else if(sign=='/')
28                 {
29                     st.top()/=num;
30                 }
31                 sign=s[i];
32                 num=0;
33             }
34             i++;
35         }
36         int res=0;
37         while(st.size())
38         {
39             res+=st.top();
40             st.pop();
41         }
42         return res;
43     }
44 };