题解：P1054 [NOIP2005 提高组] 等价表达式

ClV_Csy · 2024-12-21 13:18:31 · 题解

P1054 [NOIP2005 提高组] 等价表达式

前言

做题顺序建议：

1. P1449 后缀表达式
2. P10473 表达式计算4
3. P1054 [NOIP2005 提高组] 等价表达式

注意：

• 下文中的表达式（前缀表达式、中缀表达式、后缀表达式除外）表示“含有一个未知数 a 或不含未知数的代数式”。
• 下文中的表达式的元素表示“*表达式中的数、运算符+，-，`，^和左右括号(，)`**”。

  题意

  先给出一个表达式，再给出 n 个选项，每个选项都是一个表达式。需要输出这 n 个表达式中与原表达式等价的表达式的选项序号（大写字母）。

  思路

  一、如何判断两表达式等价

  将未知数 a 替换为一个已知数（例如 1145），再计算表达式，表达式的值相等即认为两表达式相等。

  二、如何计算表达式

  （这也是前言中 P10473 表达式计算4 的常规做法）
  本题的表达式是中缀表达式，较难直接计算。所以，我们可以使用如下顺序完成计算：

  1.将中缀表达式转换为后缀表达式

  要将中缀表达式转换为后缀表达式，可以通过对表达式内每个元素按以下规则完成：
  （有一个“运算符栈”，用于存放运算符 +，-，*，^ 和左括号 (。注意：右括号 ) 从不出现在“运算符栈”内。）

  1. 如果为数，则直接添加到后缀表达式中。
  2. 如果为运算符 +，-，*，^，则重复将“运算符栈”栈顶元素添加到后缀表达式中，再将“运算符栈”栈顶元素从“运算符栈”中弹出，直到“运算符栈”栈顶元素优先级小于该运算符优先级或“运算符栈”为空，再加入该运算符。
  3. 如果为左括号 (，则直接加入“运算符栈”。
  4. 如果为右括号 )，则重复弹出“运算符栈”栈顶元素，直到左括号 ( 也弹出。
  5. 当表达式内所有元素处理完毕后，依次弹出“运算符栈”所有元素并添加到后缀表达式中。

例如，我们要将中缀表达式 1*2-3^4+5 转换成后缀表达式，则执行顺序如下：

1. 第一个元素为 1，是数。直接加入到后缀表达式内。此时后缀表达式为 1，“运算符栈”为 。
2. 第二个元素为 *，是运算符。此时“运算符栈”为空，直接加入 * 到“运算符栈”内。此时后缀表达式为 1，“运算符栈”为 *。
3. 第三个元素为 2，是数。直接加入到后缀表达式内。此时后缀表达式为 1 2，“运算符栈”为 *。
4. 第四个元素为 -，是运算符。“运算符栈”栈顶 * 优先级大于 -，弹出并加入到后缀表达式内。现在栈为空，直接加入 - 到“运算符栈”内。此时后缀表达式为 1 2 *，“运算符栈”为 -。
5. 第五个元素为 3，是数。直接加入到后缀表达式内。此时后缀表达式为 1 2 * 3，“运算符栈”为 -。
6. 第六个元素为 ^，是运算符。“运算符栈”栈顶元素 - 优先级小于 ^，不弹出，并将 ^ 加入到“运算符栈”内。此时后缀表达式为 1 2 * 3，“运算符栈”为 - ^。
7. 第七个元素为 4，是数。直接加入到后缀表达式内。此时后缀表达式为 1 2 * 3 4，“运算符栈”为 - ^。
8. 第八个元素为 +，是运算符。“运算符栈”栈顶元素 ^ 优先级大于 +，弹出并加入到后缀表达式内。现在“运算符栈”栈顶元素 - 优先级等于 +，也弹出并加入到后缀表达式内。现在栈为空，直接加入 + 到“运算符栈”内。此时后缀表达式为 1 2 * 3 4 ^ -，“运算符栈”为 +。
9. 第九个元素为 5，是数。直接加入到后缀表达式内。此时后缀表达式为 1 2 * 3 4 ^ - 5，“运算符栈”为 +。
10. 所有元素处理完毕，弹出“运算符栈”内所有元素并加入到后缀表达式内。此时后缀表达式为 1 2 * 3 4 ^ - 5 +，“运算符栈”为 。
11. 转换结束，后缀表达式结果为 1 2 * 3 4 ^ - 5 +。

注意：

• 记得判断正负
• 十年 OI 一场空，不开 long long 见祖宗
• 优先级不要弄反

该部分代码：

#include <iostream>
#include <stack>
using namespace std;
typedef long long ll;
int gety(char op) { //返回一个运算符的优先级
    switch (op) {
        case '+' : return 1; break;
        case '-' : return 2; break;
        case '*' : return 3; break;
        case '^' : return 4; break;
    }
    return -1;
}
stack <char> st; //用于存储运算符和左括号的栈
void calc(string s) { //中缀转后缀的函数
    bool flag = 0; //正数 
    ll sum = 0;
    for (int i = 0; i < s.size(); i++) {
        if (s[i] == '-' && (s[i - 1] == '(' || i == 0)) {
            flag = 1; //负数
        } else if (s[i] >= '0' && s[i] <= '9') {
            sum = sum * 10 + s[i] - '0'; //与前面的数字是同一个数，合并
        } else if (s[i - 1] >= '0' && s[i - 1] <= '9'){ //数字部分结束
            if (flag == 1) sum = -sum;
            cout << sum << " ";
            flag = 0;
            sum = 0;
        }
        if (s[i] == ')') {
            while (st.top() != '(') {
                cout << st.top() << " ";
                st.pop();
            }
            st.pop();
        } else if (s[i] == '+' || (s[i] == '-' && s[i - 1] != '(' && i != 0) || s[i] == '*' || s[i] == '^') {
            if (st.size() != 0) {
                while (gety(st.top()) >= gety(s[i])) { //只有栈顶优先级小于待加入优先级才停止弹出
                    cout << st.top() << " ";
                    st.pop();
                    if (st.size() == 0) {
                        break;
                    }
                }
            }
            st.push(s[i]);
        } else if (s[i] == '(') {
            st.push(s[i]);
        }
    }
    while (st.size() != 0) { //弹出剩余运算符
        cout << st.top() << " ";
        st.pop();
    }
}
int main() {
    calc("1*2-3^4+5");
    return 0;
}

2.计算后缀表达式（这也是前言中 P1449 后缀表达式 的常规做法）

要计算后缀表达式，可对每个元素进行如下操作： （有一个“数栈”，用于存储数）

• 如果为数，直接加入“数栈”。
• 如果为运算符，先取出“数栈”栈顶元素 n2，弹出“数栈”栈顶，再取出此时“数栈”栈顶元素 n1，再次弹出“数栈”栈顶。将 n1, n2 做运算符所示运算，并将运算结果重新进栈。如运算符为 +，则做 n1 + n2 运算。

操作结束后，“数栈”栈顶即是所求数。

例如，要计算后缀表达式 1 2 * 3 4 ^ - 5 +，操作过程如下：

1. 第一个元素 1 为数。直接加入“数栈”。此时“数栈”为 1。
2. 第二个元素 2 为数。直接加入“数栈”。此时“数栈”为 1 2。
3. 第三个元素 * 为运算符。取出两栈顶元素，且 n1 = 1, n2 = 2，得到 n1 \times n2 = 2，将结果 2 进栈。此时“数栈”为 2。
4. 第四个元素 3 为数。直接加入“数栈”。此时“数栈”为 2 3。
5. 第五个元素 4 为数。直接加入“数栈”。此时“数栈”为 2 3 4。
6. 第六个元素 ^ 为运算符。取出两栈顶元素，且 n1 = 3, n2 = 4，得到 n1 ^ {n2} = 81，将结果 81 进栈。此时“数栈”为 2 81。
7. 第七个元素 - 为运算符。取出两栈顶元素，且 n1 = 2, n2 = 81，得到 n1 - n2 = -79，将结果 -79 进栈。此时“数栈”为 -79。
8. 第八个元素 5 为数。直接加入“数栈”。此时“数栈”为 -79 5。
9. 第九个元素 + 为运算符。取出两栈顶元素，且 n1 = -79, n2 = 5，得到 n1 + n2 = -74，将结果 -74 进栈。此时“数栈”为 -74。
10. 操作结束，“数栈”栈顶 -74 即是所求数。

前文写到的所有部分综合代码：

#include <iostream>
#include <stack>
using namespace std;
typedef long long ll;
int gety(char op) {
    switch (op) {
        case '+' : return 1; break;
        case '-' : return 2; break;
        case '*' : return 3; break;
        case '^' : return 4; break;
    }
    return -1;
}
stack <ll> ans;
stack <char> st;
ll pow(ll a, ll b) {
    ll p = 1;
    for (int i = 1; i <= b; i++) {
        p = (p * a);
    }
    return p;
}
void cz(char op) {
    if (op == '(') {
        return;
    }
    ll n2 = ans.top();
    ans.pop();
    ll n1 = ans.top();
    ans.pop();
    switch (op) {
        case '+' : ans.push(n1 + n2); break;
        case '-' : ans.push(n1 - n2); break;
        case '*' : ans.push(n1 * n2); break;
        case '^' : ans.push(pow(n1, n2)); break;
    }
}
ll calc(string s) {
    s += '@'; //防止找不到表达式结束标志
    bool flag = 0; //正数 
    ll sum = 0;
    for (int i = 0; i < s.size(); i++) {
        if (s[i] == '-' && (s[i - 1] == '(' || i == 0)) {
            flag = 1;
        } else if (s[i] == 'a') {
            sum = 1145;
            if (flag == 1) sum = -sum;
            ans.push(sum);
            flag = 0;
            sum = 0;
        } else if (s[i] >= '0' && s[i] <= '9') {
            sum = sum * 10 + s[i] - '0';
        } else if (s[i - 1] >= '0' && s[i - 1] <= '9'){
            if (flag == 1) sum = -sum;
            ans.push(sum);
            flag = 0;
            sum = 0;
        }
        if (s[i] == ')') {
            while (st.top() != '(') {
                cz(st.top());
                st.pop();
            }
            st.pop();
        } else if (s[i] == '+' || (s[i] == '-' && s[i - 1] != '(' && i != 0) || s[i] == '*' || s[i] == '^') {
            if (st.size() != 0) {
                while (gety(st.top()) >= gety(s[i])) { 
                    cz(st.top());
                    st.pop();
                    if (st.size() == 0) {
                        break;
                    }
                }
            }
            st.push(s[i]);
        } else if (s[i] == '(') {
            st.push(s[i]);
        }
    }
    while (st.size() != 0) {
        cz(st.top());
        st.pop();
    }
    return ans.top();
}
int main() {
    cout << calc("1*2-3^4+5");
    return 0;
}

三、其他细节

由于本题输入的表达式中可能含有空格，所以不可简单地使用 cin 或 scanf 来读入数据。容易想到使用 getline，但是这样会导致无法正确读入第二行的数 n。考虑到 gets 不安全，可能会出现问题，因此，我们使用 getchar 来读入数据。

读入部分的代码：

string s;
int n;
char c = getchar();
while (c != '\n' && c != '\r') { //输入第一行表达式
    if (c != ' ') {
        s += c;
    }
    c = getchar();
}
cin >> n;
for (int i = 1; i <= n; i++) {
    s = ""; //表达式清空
    c = getchar();
    while (c == '\n' || c == '\r') { //过滤多余换行符
        c = getchar();
    }
    while (c != '\n' && c != '\r') { //输入选项中的表达式
        if (c != ' ') {
            s += c;
        }
        c = getchar();
    }
}

又因为本题数据实在刁钻，运算过程中和结果爆 long long，需要模一个模数（如 1e9+7）。
还有可能出现负数，所以运算符运算时需要加上一个模数再取模。
注意：

• 求幂时每一步运算后也需要取模。

Update on 2025-11-29
能看到这里的读者应该能够知道，本篇题解的原理是将 a 代入一个特殊值（如 1145），分别计算每个选项的数值，与题干的表达式的数值相等则认为两表达式等价。
但是这样做有一个弊端，如下样例：

1145
2
a
1145

这份代码会输出 AB，然而表达式 a 与表达式 1145 并不总是相等。要解决这个问题，可以分别代入两个特殊值作为 a 的值，只有当两次代入后表达式的值都吻合时才认定两表达式等价。例如先代入 a = 11451（没错，多了个 1），再代入 a = 19198，即可认定两表达式相等。

又注意到：

如果某个选项出现不合法的表达式（如括号不匹配），忽略这个选项。

如何解决？
不合法的表达式无外乎三种情形：

1. 判断有没有 0~9, +, -, *, ^, (, ), 空格, a 之外的符号（应当是 讨论 1 的内容）
2. 判断 () 是否匹配（应当是 讨论 1 的内容）
3. 判断 () 是否紧挨在一起（讨论 2 的内容）

   bool isr(string s) {
   int cntleft = 0, cntright = 0;
   for (int i = 0; i < s.size(); i++) {
       if (s[i] >= '0' && s[i] <= '9') continue;
       if (s[i] == '+' || s[i] == '-' || s[i] == '*' || s[i] == '^' || s[i] == ' ' || s[i] == 'a') continue;
       if (s[i] == '(') {
           if (i != s.size() - 1) {
               if (s[i + 1] == ')') {
                   return 0; //情形 3
               }
           }
           cntleft++;
       } else if (s[i] == ')') {
           cntright++;
           if (cntright > cntleft) {
               return 0; //情形 2
           }
       } else {
           return 0; //情形 1
       }
   }
   if (cntleft == cntright) {
       return 1;
   }
   return 0; //情形 2
   }

至此，本题终于 AC 了。

代码

#include <iostream>
#include <stack>
using namespace std;
typedef long long ll;
void init(string &s) {
    int l = 0, r = 0;
    for (int i = 0; i < s.size(); i++) {
        if (s[i] == '(') l++;
        else if (s[i] == ')') r++;
        if (l < r) {
            s.erase(i, 1);
            r--;
        }
    }
    s += '@';
}
int gety(char op) {
    switch (op) {
        case '+' : return 1; break;
        case '-' : return 2; break;
        case '*' : return 3; break;
        case '^' : return 4; break;
    }
    return -1;
}
stack <ll> ans;
stack <char> st;
bool isr(string s) {
    /*
    1. 判断有没有 0~9, +, -, *, ^, (, ), 空格, a 之外的符号
    2. 判断 () 是否匹配
    3. 判断 () 是否紧挨在一起
    */
    int cntleft = 0, cntright = 0;
    for (int i = 0; i < s.size(); i++) {
        if (s[i] >= '0' && s[i] <= '9') continue;
        if (s[i] == '+' || s[i] == '-' || s[i] == '*' || s[i] == '^' || s[i] == ' ' || s[i] == 'a') continue;
        if (s[i] == '(') {
            if (i != s.size() - 1) {
                if (s[i + 1] == ')') {
                    return 0;
                }
            }
            cntleft++;
        } else if (s[i] == ')') {
            cntright++;
            if (cntright > cntleft) {
                return 0;
            }
        } else {
            return 0;
        }
    }
    if (cntleft == cntright) {
        return 1;
    }
    return 0;
}
ll pow(ll a, ll b) {
    ll p = 1;
    for (int i = 1; i <= b; i++) {
        p = (p * a);
    }
    return p;
}
void cz(char op) {
    if (op == '(') {
        return;
    }
    ll n2 = ans.top();
    ans.pop();
    ll n1 = ans.top();
    ans.pop();
    switch (op) {
        case '+' : ans.push(n1 + n2); break;
        case '-' : ans.push(n1 - n2); break;
        case '*' : ans.push(n1 * n2); break;
        case '^' : ans.push(pow(n1, n2)); break;
    }
}
ll calc(string s, int val) {
    init(s);
    bool flag = 0; //正数 
    ll sum = 0;
    for (int i = 0; i < s.size(); i++) {
        if (s[i] == '-' && (s[i - 1] == '(' || i == 0)) {
            flag = 1;
        } else if (s[i] == 'a') {
            sum = val;
            if (flag == 1) sum = -sum;
            ans.push(sum);
            flag = 0;
            sum = 0;
        } else if (s[i] >= '0' && s[i] <= '9') {
            sum = sum * 10 + s[i] - '0';
        } else if (s[i - 1] >= '0' && s[i - 1] <= '9'){
            if (flag == 1) sum = -sum;
            ans.push(sum);
            flag = 0;
            sum = 0;
        }
        if (s[i] == ')') {
            while (st.top() != '(') {
                cz(st.top());
                st.pop();
            }
            st.pop();
        } else if (s[i] == '+' || (s[i] == '-' && s[i - 1] != '(' && i != 0) || s[i] == '*' || s[i] == '^') {
            if (st.size() != 0) {
                while (gety(st.top()) >= gety(s[i])) { 
                    cz(st.top());
                    st.pop();
                    if (st.size() == 0) {
                        break;
                    }
                }
            }
            st.push(s[i]);
        } else if (s[i] == '(') {
            st.push(s[i]);
        }
    }
    while (st.size() != 0) {
        cz(st.top());
        st.pop();
    }
    return ans.top();
}
int main() {
    string s;
    int n;
    char c = getchar();
    while (c != '\n' && c != '\r') {
        if (c != ' ') {
            s += c;
        }
        c = getchar();
    }
    ll p1 = calc(s, 1145);
    ll p2 = calc(s, 19198);
    cin >> n;
    for (int i = 1; i <= n; i++) {
        s = "";
        c = getchar();
        while (c == '\n' || c == '\r') {
            c = getchar();
        }
        while (c != '\n' && c != '\r') {
            if (c != ' ') {
                s += c;
            }
            c = getchar();
        }
        if (!isr(s)) {
            continue;
        }
        if (calc(s, 1145) == p1 && calc(s, 19198) == p2) {
            cout << char('A' + i - 1);
        }
    }
    return 0;
}

后记

这题可以用毒瘤形容了。坑点非常之多。除了一些神犇，要想独立 AC 这题几乎不太可能。
2024-12-21 完成题解。
2025-11-29 由于

如果某个选项出现不合法的表达式（如括号不匹配），忽略这个选项。

被叉了两次：
第一次被叉（但又不完全被叉，因为输出似乎正确，也没有 MLE, RE, TLE 之类）。为了保证严谨，来修补一下。
第二次被叉（容易发现两篇帖子之间有一个多小时，在这段时间里我发现了这个错误并已经修改完成：评测 Link，于是开始修改题解。修题解期间发现了这篇帖子，和我的想法竟不谋而合）。

深觉此题毒瘤。