227. Basic Calculator II
Given a string s which represents an expression, evaluate this expression and return its value.
The integer division should truncate toward zero.
Note: You are not allowed to use any builtin function which evaluates strings as mathematical expressions, such as eval().
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 29 30 31 32 33 34 35 36 37 38 39 40 41 42
 class Solution { int nextVal(string& s, int& pos) { int res = 0; ++pos; for(; pos < s.length(); pos++) { if(s[pos] == ' ') continue; switch (s[pos]) { case '+' : case '' : case '*' : case '/' : pos; return res; default: res = (res<<3) + (res<<1) + (s[pos]&0b1111); } } return res; } public: int calculate(string s) { list<char> op; list<int> num; int val = 0; for(int i = 0; i < s.length(); i++) { if(s[i] == ' ') continue; switch (s[i]) { case '+' : case '' : num.push_back(val); op.push_back(s[i]); val = 0; break; case '*' : case '/' : val = s[i] == '*' ? val * nextVal(s, i) : val / nextVal(s, i); break; default : val = (val<<3) + (val<<1) + (s[i]&0b1111); } } num.push_back(val); while(op.size()) { int n1 = num.front(); num.pop_front(); int n2 = num.front(); num.pop_front(); int res = op.front() == '+' ? n1 + n2 : n1  n2; op.pop_front(); num.push_front(res); }
return num.front(); } };
