题解 P1175 【表达式的转换】
0AND1STORY
2019-07-15 16:31:28
这道题的解题思路很简单：
1. 把中缀表达式转换为后缀表达式(使用栈)
2. 根据后缀表达式计算结果(使用栈)
这两个过程都可以用栈来实现，所以实现过程就很清晰了。
### 实现过程：
#### 1. 读入中缀表达式：
因为输入的字符串长度不定，这里用`string`计算相对方便一些。
```cpp
string s;
cin >> s;
```
#### 2. 转换后缀表达式：
转换后缀表达式主要使用**栈**来实现，只需要枚举每一位，分情况处理即可。
一共有四种情况，如下：
- 数字：直接输出即可。
- 左括号：直接加入栈中。
- 右括号：一直弹出栈中元素并输出，直到遇到左括号为止。最后**弹出**左括号**但不输出**左括号。
- 一般运算符：一直弹出栈中元素并输出，直到遇到比自己运算优先级**低**的运算符。最后把当前运算符压入栈中。
最后若计算完成但**栈中还有元素**，弹出栈中所有元素并输出。
输出的字符串即为转换完成的后缀表达式。
```cpp
/* 返回每个运算符对应的优先级 */
inline int priority(const char& ch) {
switch(ch) {
// 加减的优先级最低，我们设为1
case '+':
case '-':
return 1;
// 乘除的优先级其次，设为2
case '*':
case '/':
return 2;
// 注意这里有乘方运算，而样例里没有，最开始我就栽在这里了QwQ
// 乘方的优先级最高，设为3
case '^':
return 3;
// 括号优先级另行处理，这里可以不写
case '(':
case ')':
return 0;
// 防止意外情况导致RE，default可写可不写
default:
return -1;
}
}
/* 将中缀表达式转换为后缀表达式 */
inline string toSuffix(const string& s) {
string ret = ""; // 用于返回的后缀表达式
stack<char> st; // 用于实现转换的栈
for (register int i = 0; i < s.size(); i ++) { // 枚举每一位
if (isdigit(s[i])) { // 如果为数字，直接输出到结果中
ret += s[i];
} else if (s[i] == '(') { // 如果为左括号，直接加入栈中
st.push(s[i]);
} else if (s[i] == ')') { // 如果为右括号，
while (st.top() != '(') // 一直弹出并输出直到遇到左括号，
ret += st.top(), st.pop(); // 并弹出左括号
st.pop();
} else { // 否则即为普通的运算符，
while (!st.empty() && priority(st.top()) >= priority(s[i]))
ret += st.top(), st.pop(); // 一直弹出并输出直到遇到比当前优先级低的运算符，
st.push(s[i]); // 最后把当前运算符压入栈中
}
}
while (!st.empty()) // 最后如果栈中还有剩余的字符，直接弹出并输出
ret += st.top(), st.pop();
return ret; // 最后返回结果
}
```
#### 3. 计算后缀表达式的值，并输出计算过程：
计算后缀表达式也使用栈来实现，计算过程同理要分情况处理。
一共分为两种情况，如下：
- 数字：直接压入栈即可。
- 运算符：取出栈顶的两个数进行相应的运算，将计算结果压入栈中。**一定要注意取出元素的计算顺序！先取出的数为`X数`(X为减/除/etc.)，后取出的数为`被X数`！**每次完成当前计算后输出计算过程。
输出计算过程的方法为：
1. 先输出已计算完成的数，即所有的栈中元素(**需要按照从栈底到栈顶的顺序**)。
2. 再输出还未计算的数，即字符串中当前字符到末尾的字符串。
因为需要输出栈中元素，为了方便，不需要将每个元素弹出后输出，并且使每次压入和弹出的操作的时间复杂度降到尽可能的小，这里没有使用`stack`(每次需弹出)和`vector`(常数相对较大)而使用了`list`(链表)~~(也可以说我有点强迫症吧2333)~~。
```cpp
/* 根据运算符计算相应的运算结果 */
inline int calcNum(const int& a, const int& b, const int& symbol) {
switch(symbol) {
case '+':
return a + b;
case '-':
return a - b;
case '*':
return a * b;
case '/':
return a / b;
case '^':
return (int)pow(a, b);
default: // 与上面同理，default可写可不写
return -1;
}
}
/* 将后缀表达式加上空格后输出 */
inline void printSuffix(const string& s) {
for (register int i = 0; i < s.size(); i ++)
cout << s[i] << ' ';
cout << endl;
}
/* 计算后缀表达式并输出计算过程 */
inline void calc(const string& s) {
/**
* 实现计算的数字栈，为了输出方便(不需要将每个元素弹出)
* 并且为了使压入和弹出操作的时间复杂度降到O(1)，
* 这里没有使用vector而是使用了list(链表)
*/
list<int> st;
printSuffix(s); // 注意要先输出后缀表达式，我之前栽在这里了QwQ
for (register int i = 0; i < s.size(); i ++) {
if (isdigit(s[i])) { // 如果遇到数字直接压入栈
st.push_back(s[i] - '0');
} else { // 否则计算结果并压入栈
register int a, b; //取出栈顶的两个元素
a = st.back();
st.pop_back();
b = st.back();
st.pop_back();
st.push_back(calcNum(b, a, s[i])); // 注意计算顺序
// 每计算一次输出一次计算过程
for (list<int>::iterator it = st.begin(); it != st.end(); ++it)
cout << *it << ' '; // 输出栈中已计算过的数
for (register int j = i + 1; j < s.size(); j ++)
cout << s[j] << ' '; // 再输出还未计算过的数
cout << endl;
}
}
}
```
经过这三步就完成了题目的要求，所以AC代码如下：
### AC代码：
```cpp
#include <iostream>
#include <cctype>
#include <cmath>
#include <vector>
#include <string>
#include <stack>
#include <list>
#include <algorithm>
using namespace std;
/* 返回每个运算符对应的优先级 */
inline int priority(const char& ch) {
switch(ch) {
// 加减的优先级最低，我们设为1
case '+':
case '-':
return 1;
// 乘除的优先级其次，设为2
case '*':
case '/':
return 2;
// 注意这里有乘方运算，而样例里没有，最开始我就栽在这里了QwQ
// 乘方的优先级最高，设为3
case '^':
return 3;
// 括号优先级另行处理，这里可以不写
case '(':
case ')':
return 0;
// 防止意外情况导致RE，default可写可不写
default:
return -1;
}
}
/* 将中缀表达式转换为后缀表达式 */
inline string toSuffix(const string& s) {
string ret = ""; // 用于返回的后缀表达式
stack<char> st; // 用于实现转换的栈
for (register int i = 0; i < s.size(); i ++) { // 枚举每一位
if (isdigit(s[i])) { // 如果为数字，直接输出到结果中
ret += s[i];
} else if (s[i] == '(') { // 如果为左括号，直接加入栈中
st.push(s[i]);
} else if (s[i] == ')') { // 如果为右括号，
while (st.top() != '(') // 一直弹出并输出直到遇到左括号，
ret += st.top(), st.pop(); // 并弹出左括号
st.pop();
} else { // 否则即为普通的运算符，
while (!st.empty() && priority(st.top()) >= priority(s[i]))
ret += st.top(), st.pop(); // 一直弹出并输出直到遇到比当前优先级低的运算符，
st.push(s[i]); // 最后把当前运算符压入栈中
}
}
while (!st.empty()) // 最后如果栈中还有剩余的字符，直接弹出并输出
ret += st.top(), st.pop();
return ret; // 最后返回结果
}
/* 根据运算符计算相应的运算结果 */
inline int calcNum(const int& a, const int& b, const int& symbol) {
switch(symbol) {
case '+':
return a + b;
case '-':
return a - b;
case '*':
return a * b;
case '/':
return a / b;
case '^':
return (int)pow(a, b);
default: // 与上面同理，default可写可不写
return -1;
}
}
/* 将后缀表达式加上空格后输出 */
inline void printSuffix(const string& s) {
for (register int i = 0; i < s.size(); i ++)
cout << s[i] << ' ';
cout << endl;
}
/* 计算后缀表达式并输出计算过程 */
inline void calc(const string& s) {
/**
* 实现计算的数字栈，为了输出方便(不需要将每个元素弹出)
* 并且为了使压入和弹出操作的时间复杂度降到O(1)，
* 这里没有使用vector而是使用了list(链表)
*/
list<int> st;
printSuffix(s); // 注意要先输出后缀表达式，我之前栽在这里了QwQ
for (register int i = 0; i < s.size(); i ++) {
if (isdigit(s[i])) { // 如果遇到数字直接压入栈
st.push_back(s[i] - '0');
} else { // 否则计算结果并压入栈
register int a, b; //取出栈顶的两个元素
a = st.back();
st.pop_back();
b = st.back();
st.pop_back();
st.push_back(calcNum(b, a, s[i])); // 注意计算顺序
// 每计算一次输出一次计算过程
for (list<int>::iterator it = st.begin(); it != st.end(); ++it)
cout << *it << ' '; // 输出栈中已计算过的数
for (register int j = i + 1; j < s.size(); j ++)
cout << s[j] << ' '; // 再输出还未计算过的数
cout << endl;
}
}
}
int main() {
string s;
cin >> s;
calc(toSuffix(s));
return 0;
}
```