题解：AT_colopl2018_final_b 異世界数式

题意简单易懂，就是把另一种特殊的数学表达式转化成中缀表达式

这一题，我们可以使用一个栈来进行操作，这个栈用于存储正在处理的运算符号

我们遍历特殊表达式，当我们遇到括号时，即可按照题意直接输出括号。当遇到运算符号的时候，这个就是我们现在要处理的运算符号，我们把它入栈。而且这些数字并列，用都好隔开，他们需要的运算符号就是栈顶符号，所以遇到逗号我们直接输出栈顶运算符即可。注意一点，就是每次运算完成后（即遇到右括号），这个运算符就用完了，需要出栈。而数字只需直接输出。

这就是全部过程，简单梳理一下步骤

• 遇到左括号或者数字，直接输出
• 遇到右括号，输出自身并弹出栈顶元素
• 遇到运算符，直接入栈
• 遇到逗号，输出栈顶运算符

这样子时间复杂度仅仅 O(n) ，绝对不会超时

code

简单易懂

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;
string a; //存储特殊表达式
stack <char> st; //存储当前需处理的运算符
int main() {cin >> a; //先输入特殊表达式for (int i = 0 ; i < a.size() ; i++) {//遍历特殊表达式，按照刚才的步骤处理char c = a[i]; //当前遍历到的字符if (c == '(') {// 如果是左括号，直接输出cout << c;} else if (c == '+' || c == '-' || c == '*' || c == '/') {//如果是运算符，直接入栈st.push(c);} else if (c == ',') {// 如果是逗号，输出栈顶运算符cout << st.top();} else if (c == ')') {// 如果是右括号，输出并弹出栈顶元素cout << c;st.pop();} else {// 否则肯定是数字，直接输出cout << c;}}return 0;
}

当然这么多分支写起来有点累的，我们可以简化一下

简化版：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;
string a; //存储特殊表达式
stack <char> st; //存储当前需处理的运算符
int main() {cin >> a; //先输入特殊表达式for (int i = 0 ; i < a.size() ; i++) {//遍历特殊表达式，按照刚才的步骤处理char c = a[i]; //当前遍历到的字符if (c == '+' || c == '-' || c == '*' || c == '/') {// 如果是运算符号，直接入栈st.push(c);} else if (c == ')') {// 如果是右括号，输出并弹出栈顶元素cout << c;st.pop();} else if (c == ',') {// 如果是逗号，输出栈顶运算符cout << st.top();} else {// 是数字或左括号，直接输出cout << c;}}return 0;
}