题解 P1175 【表达式的转换】

rui_er · 2021-01-22 22:15:24 · 题解

本题题解貌似已经比较多了，但是我在本题卡了一段时间，写出了好几处错误，因此写一篇题解梳理一下思路。

题意：模拟 +-*/^() 以及数字初始为一位数的后缀表达式运算过程。

注意这里有一个运算符 ^，我一开始就没有注意到，然后样例也没有，硬是对着代码和题面看了半天才发现！

思路：

模拟。先转化为后缀表达式，再模拟运算过程，逐步求解。

子问题一：中缀表达式转后缀表达式。

我们考虑运算符的优先级，可以对于每个运算符给定一个数为优先级，方便后续比较。这里，我设置的优先级为：

int priority(char c) {
    if(c == '^') return 3;
    if(c == '*' || c == '/') return 2;
    if(c == '+' || c == '-') return 1;
    if(c == '(' || c == ')') return 0;
    throw "WA! Unexpected operator";
}

其中 throw 行是为了防止出现错误添加的异常，实际上也并没有进行处理，可以忽略。

然后考虑转化，遍历原字符串每一位，按照如下规则处理：

如果是数字，直接输出到后缀表达式。
如果是左括号 (，可以压进符号栈中。
如果是右括号 )，将符号栈中符号弹出到后缀表达式，直到遇到第一个左括号 (，并将其弹出。
如果是乘方 ^，可以压进符号栈中。
如果是加减乘除 +-*/，利用上面的优先级，将符号栈中符号弹出到后缀表达式，直到遇到第一个优先级低于（不含）它的符号，然后将其压进符号栈。

那么问题来了，怎么存储后缀表达式呢？这里我使用了一个结构体 struct，一个指示变量表示这个是数字还是符号，一个联合体 union 来存储具体内容，然后使用向量容器 vector 来按顺序存储后缀表达式。

结构体定义和转换后缀表达式部分代码如下：

struct Node {
    int type;
    union {
        int x;
        char op;
    }data;
    Node() {}
    Node(int x) : type(1) {data.x = x;}
    Node(char c) : type(0) {data.op = c;}
};
void toSuffix() {
    rep(i, 0, n-1) {
        if(isdigit(c[i])) v.push_back(Node(int(c[i]^'0')));
        else {
            if(c[i] == '(') op.push(c[i]);
            else if(c[i] == ')') {
                while(op.top() != '(') {
                    v.push_back(Node(char(op.top())));
                    op.pop();
                }
                op.pop();
            }
            else if(c[i] == '^') op.push(c[i]);
            else {
                while(!op.empty() && priority(op.top()) >= priority(c[i])) {
                    v.push_back(Node(char(op.top())));
                    op.pop();
                }
                op.push(c[i]);
            }
        }
    }
    while(!op.empty()) {
        v.push_back(Node(char(op.top())));
        op.pop();
    }
}

子问题二：模拟运算步骤得出结果。

这部分比较简单，做过 P1449 后缀表达式的同学都应该基本会了。我们按顺序读取后缀表达式内存储的数据，如果是数字则压入数字栈，否则弹出两个数字做运算后压回。注意运算的顺序，应该是第二个弹出的数作为被减数（加数、乘数、被除数、底数），第一个弹出的数作为减数（加数、乘数、除数、指数）！

然后每处理一个运算符，输出一次即可。

这部分代码：

void prtall() {
    int sz = v.size();
    rep(i, 0, sz-1) {
        if(v[i].type) printf("%d%c", v[i].data.x, " \n"[i==sz-1]);
        else printf("%c%c", v[i].data.op, " \n"[i==sz-1]);
    }
}
void prtsec(int u) {
    int sz = v.size();
    while(!s.empty()) {t.push(s.top()); s.pop();}
    while(!t.empty()) {printf("%d ", t.top()); s.push(t.top()); t.pop();}
    rep(i, u, sz-1) {
        if(v[i].type) printf("%d ", v[i].data.x);
        else printf("%c ", v[i].data.op);
    }
    puts("");
}
void calc() {
    prtall();
    int sz = v.size();
    rep(i, 0, sz-1) {
        if(v[i].type) s.push(v[i].data.x);
        else {
            int a, b; char _;
            b = s.top(); s.pop();
            a = s.top(); s.pop();
            _ = v[i].data.op;
            if(_ == '+') s.push(a+b);
            else if(_ == '-') s.push(a-b);
            else if(_ == '*') s.push(a*b);
            else if(_ == '/') s.push(a/b);
            else s.push(qpow(a, b));
            prtsec(i+1);
        }
    }
}

这就是本题的主体代码，我也取得了 AC，代码长度 107 行、共 2441 个字符（本地统计），可以算是一个中模拟。

由于主要代码在上面都贴过了，为了防止影响篇幅和版面，将完整代码放到云剪贴板。

完结撒花！