227. Basic Calculator II

The difference with problem "224. Basic Calculator" is that this problem contains '*' and '/' operator but no parenthesis. We can use stack to solve this problem. Stack stores all the numbers that need to sum up. So when we meet '+', we simply push the number into stack. When we meet '-', we simply push the negative number into the stack. When we meet '*' or '/' which has high priority, we only need to pop the top number out of the stack, operate on it and push it back to stack. With this operation, the stack will store all the numbers that need to sum up only.

1:  class Solution {  
2:  public:  
3:    int calculate(string s) {  
4:      char sign = '+';  
5:      int num = 0;  
6:      stack<int> stk;  
7:      for (int i = 0; i < s.size(); i++) {  
8:        if (s[i] >= '0' && s[i] <= '9') {  
9:          num = num*10+s[i]-'0';  
10:        }  
11:        if (((s[i] < '0' || s[i] > '9') && (s[i] != ' ')) || i == s.size()-1) {  
12:          if (sign == '+') stk.push(num);  
13:          else if (sign == '-') stk.push(-num);  
14:          else if (sign == '*') {num *= stk.top(); stk.pop(); stk.push(num);}  
15:          else if (sign == '/') {num = stk.top()/num; stk.pop(); stk.push(num);}  
16:          sign = s[i];  
17:          num = 0;  
18:        }  
19:      }  
20:      int res = 0;  
21:      while (!stk.empty()) {  
22:        res += stk.top();  
23:        stk.pop();  
24:      }  
25:      return res;  
26:    }  
27:  };