中缀表达式转后缀表达式。对于普通中缀表达式的计算，我们可以将其转化为后缀表达式再进行计算。转换方法也十分简单。只要建立一个用于存放运算符的栈，扫描该中缀表达式：
- 如果遇到数字，直接将该数字输出到后缀表达式（以下部分用「输出」表示输出到后缀表达式）；
- 如果遇到左括号，入栈；
- 如果遇到右括号，不断输出栈顶元素，直至遇到左括号（左括号出栈，但不输出）；
- 如果遇到其他运算符，不断去除栈顶所有运算优先级大于等于当前运算符的运算符，输出。最后，新的符号入栈；
- 把栈中剩下的符号依次输出，表达式转换结束。
对于一个后缀表达式，只需要 维护一个数字栈，每次遇到一个运算符，就取出两个栈顶元素，将运算结果重新压入栈中 。最后，栈中唯一一个元素就是该后缀表达式的运算结果时间复杂度 。
class Solution {
//适用于个位数，加减乘除
public:
int calculate(string s) {
stack<char> sign;//运算符栈
vector<char> postfix;//后缀表达式
for (auto ch :s) {
if (ch == ' ')
continue;
else if (isdigit(ch)) {
postfix.push_back(ch);
} else if (ch == '(') {
sign.push(ch);
} else if (ch == ')') {
while (!sign.empty() && sign.top() != '(') {
postfix.push_back(sign.top());
sign.pop();
}
sign.pop();
} else {
while (!sign.empty() && get_priority(sign.top()) >= get_priority(ch)) {//只要栈顶运算符的优先级不低于新运算符，就不断取出栈顶并输出
postfix.push_back(sign.top());
sign.pop();
}
sign.push(ch);
}
}
while (!sign.empty()) {
postfix.push_back(sign.top());
sign.pop();
}
//遇到运算符就计算
stack<int> nums;
for (auto item:postfix) {
if (isdigit(item))
nums.push(item - '0');
else {
int one = nums.top();
nums.pop();
int two = nums.top();
nums.pop();
if (item == '+') {
nums.push(one + two);
} else if (item == '-') {
nums.push(two - one);
} else if (item == '*') {
nums.push(one * two);
} else if (item == '/') {
nums.push(two / one);
}
}
}
return nums.top();
}
int get_priority(char ch) {
if (ch == '+' || ch == '-')
return 0;
else if (ch == '*' || ch == '/')
return 1;
else
return -1;
}
};