题目：
假设表达式由数字和双目四则运算符+，-，*，/构成。试利用栈实现一个算法，将一个通常书写形式且书写正确的表达式转换为逆波兰式（后缀表达式），同时将转换后的逆波兰式求值，最后仅需输出求值结果。
输入格式
输入共有一行，为待求值的表达式，以换行结束。表达式保证是合法的，表达式中的整数在 [0,10][0,10] 以内，表达式长度不超过 2020。表达式中仅包含+，-，*，/以及数字，不会出现其他字符。
输出格式
输出仅有一行，为输入表达式的正确计算结果。
样例输入
1+2+3+4+5
样例输出
15
提示：
表达式仅占一行，保证表达式计算的合理性，不需判断除零等情况。
表达式的计算应遵循同级运算从左往右，先乘除后加减的原则。
仅需考虑整数运算（包括中间结果）。
我的解题思路：
这道题考察了后缀表达式和栈的应用。
我首先定义了一个栈类。
成员函数包括构造，析构，入栈，出栈，返回栈顶元素，判断是否为空。
然后编写主函数。
主函数部分分为两步：
第一步把输入的表达式利用栈的存储结构写成后缀表达式。
这一步我使用了两个栈，分别定义为stack和stack_temp，前者用于存储后缀表达式，后者用来暂存操作符。
对于输入的字符数组，依次判断数组元素是否为数字。
为数字则直接压入stack。
若为操作符，则循环与stack_temp的栈顶操作符对比。
若stack_temp的栈顶操作符优先级更高，就将其出栈并压入stack，否则将操作符压入stack_temp。
读完输入的字符数组后，再将stack_temp中的操作符依次出栈压入stack中。
最后，将stack的栈顶元素依次出栈压入stack_temp。至此stack_temp存储了后缀表达式。
第二步利用存储在栈中的后缀表达式计算最终结果。
这一步依然使用了两个栈，第一个是存储了后缀表达式的stack_temp，另一个result用来存储结果（和中间结果）。
依次将stack_temp的栈顶元素出栈。
若为数字则直接压入result。
若为操作符，则通过自定义的calc函数计算result中位于栈顶的两个元素在该操作符下得到的计算结果，将这两个元素出栈，并将结果压入result。
最后输出result的栈顶元素。
最后我编写了用到的判断优先级的函数precede()，计算一对操作数与双目操作符的计算结果的函数operate()，和弹出result中两个操作数，弹出stack_temp中的操作符并调用operate()，返回计算结果的calc()。
中间出现的问题：
曾人工析构stack，段错误。这个不清楚为什么报错。
曾忘记calc中已pop过stack_temp，导致stack_temp被错误pop，最终输出了错误结果。
我的解题代码：
#include <iostream>
#include <string>
using std::cin;
using std::cout;
using std::endl;
using std::string;
template <typename Type>
class Stack {
private:
int max_size, top_index;
Type *elements;
public:
Stack(int _size): max_size(_size) {
top_index = -1;
elements = new Type[max_size];
}
~Stack() {
delete[] elements;
}
bool push(Type element) {
if (top_index >= max_size - 1) {
return false;
}
top_index++;
elements[top_index] = element;
return true;
}
bool pop() {
if (!empty()) {
top_index--;
return true;
}
return false;
}
Type top() {
return elements[top_index];
}
bool empty() {
return top_index < 0;
}
};
bool precede (char a, char b) {
if (a == '*' || a == '/') {
return true;
} else if (b == '*' || b == '/') {
return false;
} else {
return true;
}
}
int operate (char opr, int a , int b) {
if (opr == '+') {
return b + a;
} else if (opr == '-') {
return b - a;
} else if (opr == '*') {
return b * a;
} else if (opr == '/') {
return b / a;
}
return 9999;
}
int calc (Stack<int> &result, Stack<char> &stack_temp) {
int a, b;
a = result.top();
result.pop();
b = result.top();
result.pop();
char opr;
opr = stack_temp.top();
stack_temp.pop();
return operate(opr, a, b);
}
int main() {
string input;
cin >> input;
Stack<char> stack(input.length());
Stack<char> stack_temp(input.length());
int i = 0;
while (input[i] != '\0') {
if (isdigit(input[i])) {
stack.push(input[i]);
i++;
} else {
while (!stack_temp.empty() && precede(stack_temp.top(), input[i])) {
stack.push(stack_temp.top());
stack_temp.pop();
}
stack_temp.push(input[i]);
i++;
}
}
while (!stack_temp.empty()) {
stack.push(stack_temp.top());
stack_temp.pop();
}
while (!stack.empty()) {
stack_temp.push(stack.top());
stack.pop();
}
Stack<int> result(input.length());
while (!stack_temp.empty()) {
//cout << stack_temp.top() << endl;
if (isdigit(stack_temp.top())) {
result.push(stack_temp.top() - '0');
stack_temp.pop();
} else {
result.push(calc(result, stack_temp));
}
}
cout << result.top();
return 0;
}
