题意
表达式求值，只含有+, -, (, )。
思路
转逆波兰表示后求值。
转逆波兰的过程：
扫描字符串，如果是数字直接输出
如果是)，那么一直出栈到遇到(。
如果是运算符，比较当前运算符op和栈顶运算符top的优先级，如果
top≥op，那么出栈直到上述条件不满足。将op放到栈里面。
在处理数字的过程中，注意空格的处理。
代码
class Solution {
public:
int changeOpToNum(char ch) {
if (ch == '(') return -1;
if (ch == ')') return -2;
if (ch == '+') return -3;
return -4;
}
bool isOp(char ch) {
return ch == '(' || ch == ')' || ch == '+' || ch == '-';
}
int
PRi(int op) {
if (op == -3 || op == -4) return 1;
}
//v to save RPN
vector<int> v;
void toRPN(string str) {
stack<int> s;
int y = -1;
for (int i = 0; i < str.length(); i++) {
auto x = str[i];
if (i == str.length() - 1 && (!isOp(x) || x == ' ')) {
if (!isOp(x) && x != ' ') v.push_back(y == -1 ? x - '0' : y * 10 + x - '0');
else if (y != -1) v.push_back(y);
continue;
}
if (x == ' ') continue;
if (isOp(x)) {
if (y != -1) v.push_back(y);
y = -1;
int op = changeOpToNum(x);
// ')'
if (op == -2) {
while (s.top() != -1) {
v.push_back(s.top());
s.pop();
}
s.pop();
} else {
if (op == -1) s.push(op);
else {
while (!s.empty() && s.top() != -1 && pri(op) <= pri(s.top())) {
v.push_back(s.top());
s.pop();
}
s.push(op);
}
}
} else {
if (y == -1) y = 0;
y *= 10;
y += x - '0';
}
}
while (!s.empty()) v.push_back(s.top()), s.pop();
}
int calculate(string str) {
toRPN(str);
int res = 0;
stack<int> s;
for (auto x : v) {
if (x >= 0) s.push(x);
else {
int x2 = s.top(); s.pop();
int x1 = s.top(); s.pop();
if (x == -3) s.push(x1 + x2);
else s.push(x1 - x2);
}
}
return s.top();
}
};
