洛谷UVA727 Equation

Description

给定一串合法的中缀表达式，求它的后缀表达形式。

Solution

这道题很水毒瘤。你可能会问，为什么会毒瘤？挺简单的啊。

好的，那我告诉你，这道题输入输出细节处理能死人的！！1

那么，我们来先不管这毒瘤的输入输出，来看看算法的主体部分。

中缀表达式转后缀

正好临近CSP 2021，复习一下。

转换的过程中，我们需要使用栈进行临时存储。

我们不妨设 \(s\) 为待转换的中缀表达式字符串。我们从左往右遍历该表达式，并按下列情况处理：

1. 若 \(s_i\) 为操作数，直接输出；
2. 若 \(s_i\) 为左括号 ( ，我们把它压入栈中；
3. 若 \(s_i\) 为操作运算符，那么，我们按照下列方式执行：
   1. 若 \(s_i\) 的优先级 \(>\) 栈顶元素的优先级，将 \(s_i\) 压入栈中；
   2. 若 \(s_i\) 的优先级 \(\leqslant\) 栈顶元素的优先级，我们进行循环弹出栈顶元素并输出，直到满足条件一为止，并将 \(s_i\) 压入栈中。
4. 若 \(s_i\) 为右括号 ) ，我们循环弹出栈顶元素并输出，直到栈顶元素为左括号 ( 为止。
5. 当 \(s_i\) 为 \0 时（扫描结束），若栈非空，那么我们循环弹出栈顶元素并输出，直到栈空。

更详细的可以去参考一下这篇dalao写的博客。

避坑指北

好的，讲完了主要算法，我们来步入今天的主题避坑环节。

坑点一

输入是一行一行输入的。所以，不要使用单纯的 cin 或 getline 进行输入！你需要使用循环进行读入。

你也需要注意，每行只有一个字符，所以数字有可能是分开的。但是，由于我们直接输出数字即可，所以这条倒没有什么关系。

坑点二

每次输入会有多个测试点！在输入的时候，测试点使用一个换行 \n 进行分割，如：

2  # 两组测试数据
1  # 第一组
+
2
   # 注意：这里有一个换行作为分割线！
2  # 第二组
*
1  # 15被分割成了两行（坑点一）
5

因此，我们需要在输入的时候统计换行数量，连续换行两次即为新的测试点。

坑点三

在输出的时候，每个测试点之间，都要有一个换行作为分割！形式跟坑点二的差不多。

为了保险起见，我也特殊处理了最后一个样例：不输出换行。

坑点四

输入测试点数量 \(t\) 之后，会有一个回车。如果此时不把回车过滤掉的话，有可能会被识别为新测试点。所以，保险起见，在输入 \(t\) 之后最好也把这个回车过滤掉（ cin不会过滤，它碰到回车就结束了，不读入回车）。

坑点五

由于有多组数据，我们需要在每次读入前初始化一遍所有的变量，避免造成数据存储错误。

Code

STL stack 万岁！

#include 
#include 
#include 
#include 
using namespace std;

stack  s;  // 转换用的栈
string ans;  // 最终结果的存储串
char tmp;
int t, flag = 0;  // flag判断输入换行次数

int check(string op) {  // 判断运算符优先级
    if (op == "(") return 2;
    if (op == "*" || op == "/") return 1;
    if (op == "+" || op == "-") return 0;
    return -1;
}

int main() {  // 这道题特别麻烦：输入输出细节太多
    cin >> t;  // t个测试点
    getchar();  // 这里还有一个回车
    while (t--) {
        ans = "";
        while ((tmp = getchar()) != EOF) {  // 循环输入
            if (tmp == '\n') {  // 回车分两种情况：1. 普通换行 2. 两个回车连在一起，是新起一个测试点
                flag++;  // 回车个数统计
                if (flag == 2) break;  // 新测试点就跳出当前输入循环
                continue;
            }
            flag = 0;
            string ch(1, tmp);  // 小技巧：char转string
            if (ch[0] >= '0' && ch[0] <= '9') {  // 数字直接输出
                ans += ch;
            } else if (ch[0] == ')') {  // 括号特判
                while (s.top() != "(") {  // 既然输入了右括号，肯定有左括号，一直弹出直到找到左括号为止
                    ans += s.top();
                    s.pop();
                }
                s.pop();  // 还要弹出左括号
            } else {  // 运算符
                if (!s.empty() && (ch == "+" || ch == "-" || ch == "/" || ch == "*")) {  // 非空且不是左括号
                    while (!s.empty() && check(ch) <= check(s.top()) && s.top() != "(") {  // 找到比自己优先级小的插进去
                        ans += s.top();
                        s.pop();
                    }
                    s.push(ch);
                } else s.push(ch);  // 空的或者是括号直接压进栈中
            }
        }
        while (!s.empty()) {  // 继续处理没有弹出的部分，直接输出即可
            ans += s.top();
            s.pop();
        }
        cout << ans << endl;  // 输出最后汇总的后序表达式
        if (t != 0) cout << endl;  // 测试点之间的换行
    }
    return 0;
}

其实这道题目我个人认为还是比较考验耐心的，我调试了一个晚上才搞出来……也许是我太弱了吧……

最后也祝大家 CSP-J/S 2021 rp++！