Evaluate 由+-/和非负数字构成的数学表达式。分别用两个stack nums和ops存当前结果和操作符。a+b*c时不能直接算a+b，而应该把a b c都压进nums中直到结束再从stack开始eval b*c，即让b和c从nums出栈和ops.top做操作后结果入nums。最后再eval stack所剩所有元素。
class Solution {
public:
int calculate(string s) {
stack<int> nums;
stack<char> ops;
const auto higher = [](char a, char b) {
if ((a == '*' || a == '/') && (b == '+' || b == '-')) return true;
return false;
};
const auto op = [&]() {
const auto b = nums.top(); nums.pop();
const auto a = nums.top(); nums.pop();
const auto o = ops.top(); ops.pop();
switch (o) {
case '+':
nums.push(a + b);
break;
case '-':
nums.push(a - b);
break;
case '*':
nums.push(a * b);
break;
case '/':
nums.push(a / b);
break;
}
};
int res = 0;
for (int i = 0, num = 0; i < s.length(); ++i) {
auto c = s[i];
if (isdigit(c)) {
num = c - '0';
while (i < s.length() && isdigit(s[i + 1])) {
num = num * 10 + (s[i + 1] - '0');
++i;
}
nums.push(num);
num = 0;
} else if (c == '+' || c == '-' || c == '*' || c == '/') {
while (!ops.empty() && !higher(c, ops.top())) {
op();
}
ops.push(c);
}
}
while (!ops.empty()) {
op();
}
return nums.top();
}
};