题解：P14305 【MX-J27-T2】转换

UNNN · 2025-10-25 14:35:30 · 题解

题解交迟了所以没申请

题意

给定 t 个类型表达式，求表达式运算后的最终结果。

思路

我们先看 , 运算，, 连接的两个表达式的结果取的是 , 右边的整个表达式，由于该运算优先级最低，所以我们不妨先把 , 连接的表达式全部看成一个整体，那么我们显然可以推出：a_1,a_2,a_3,...,a_r = a_2,a_3,...,a_r = ... = a_r。所以我们找到位于表达式最右边的 ,，从此处开始取表达式的子串即可，这样 , 运算就轻松处理完了。

随后我们开始存储表达式中的各个类型以及符号。我们可以把类型名和符号分成数组中的若干个元素来存储，例如表达式 char+int*longlong+double 可以存储为 {"char", "+", "int", "*", "longlong", "+", "double"}。

在代码实现中，因为每个类型的名字开头的第一个字母各不相同，所以我们遍历表达式时，遇到类型名的第一个字符就可以直接得出类型名并存到表达式数组里。

由于表达式中类型名和计算符号交替连接，所以数组下标为奇数的位置存储类型名，偶数位置存储符号。

随后，题目中说明了乘法优先级高于加法，所以我们另开一个数组，存储将原表达式中所有乘法运算计算完毕后的表达式元素。先将所有类型名存放入该数组中，然后遍历原始数组，寻找乘号，找到乘号后向右遍历到连乘结束，中途不断更新这串连乘的结果，将最终结果存到第二个数组中即可。

最后，将第二个数组中的所有类型进行运算操作，即可得到最终答案，更新答案的方式和连乘操作是一样的。

对于运算操作，实际上无论乘法加法，这两种计算出的结果都是一样的。题目对运算的解释可以简化为：

将 char 和 bool 全部转化为 int。
两类型相同，最终得出的类型跟这两个也相同。
若不相同，如果存在 double，则最终答案为 double；如果不存在 double 但存在 float，则最终答案为 float；如果不存在上两者但存在 longlong，则最终答案为 longlong；如果上三者都不存在，则最终答案为 int。

还要注意，两个数组大小需要开 2 \times 10^5，因为我们同时存入了类型和符号。

Code

#include <iostream>
#include <cstdio>
#include <string>
using namespace std;
const int MAXN = 2e5 + 5;
int c, t, len = 0, comaflg = -1;
string s, str[MAXN], sm[MAXN], ans;
string oper(string x, string y){ // 运算
    if(x == "char" || x == "bool") x = "int";
    if(y == "char" || y == "bool") y = "int";
    if(x == y) return x;
    else{
        if(x == "double" || y == "double") return "double";
        if(x == "float" || y == "float") return "float";
        if(x == "longlong" || y == "longlong") return "longlong";
        return "int";
    }
}
int main()
{
    scanf("%d%d", &c, &t);
    while(t--){
        // 初始化
        len = 0;
        comaflg = -1;
        cin >> s;
        // 逗号运算
        for(int i = s.length() - 1;i >= 0;i--){
            if(s[i] == ','){
                comaflg = i;
                break;
            }
        }
        s = s.substr(comaflg + 1); // 取逗号最终运算结果
        for(int i = 0;i < s.length();){ // 开始存储
            if(s[i] == 'c'){
                str[++len] = "char";
                i = i + 4;
            }
            else if(s[i] == 'i'){
                str[++len] = "int";
                i = i + 3;
            }
            else if(s[i] == 'd'){
                str[++len] = "double";
                i = i + 6;
            }
            else if(s[i] == 'l'){
                str[++len] = "longlong";
                i = i + 8;
            }
            else if(s[i] == 'f'){
                str[++len] = "float";
                i = i + 5;
            }
            else if(s[i] == 'b'){
                str[++len] = "bool";
                i = i + 4;
            }
            else if(s[i] == '+'){
                str[++len] = "+";
                i++;
            }
            else if(s[i] == '*'){
                str[++len] = "*";
                i++;
            }
        }
        for(int i = 1;i <= len;i = i + 2) sm[i] = str[i]; // 初始化第二个数组
        for(int i = 2;i <= len;i = i + 2){
            if(str[i] == "*"){
                string res = str[i - 1]; // 结果累乘
                int j;
                for(j = i + 1;str[j - 1] == "+" && j <= len;j = j + 2){
                    res = oper(res, str[j]); // 累乘
                    sm[j] = "void"; // 由于存储时要对应下标存储，而这若干个类型全部合并为了一个类型，所以剩余部分全部存成 void，后面累加时跳过即可
                }
                sm[i - 1] = res; // 累乘结果
                i = j - 1; // i 跳转至连乘末尾
            }
        }
        ans = sm[1]; // 结果累加
        for(int i = 3;i <= len;i = i + 2){
            if(sm[i] == "void") continue; // 跳过 void
            ans = oper(ans, sm[i]); // 累加
        }
        cout << ans << endl; // 输出
    }
    return 0; // 结束 (｡･ω･｡)
}