1 条题解

  • 0
    @ 2025-8-24 21:20:24

    自动搬运

    查看原文

    来自洛谷，原作者为

    avatar ClV_Csy
    逸一时，误一世，逸久逸久罢已龄。个人网站：clv.ct.ws

    搬运于2025-08-24 21:20:23，当前版本为作者最后更新于2024-12-21 13:18:31，作者可能在搬运后再次修改，您可在原文处查看最新版

    自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

    以下是正文

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

    前言

    做题顺序建议：

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

    注意：

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

    题意

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

    思路

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

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

    二、如何计算表达式

    （这也是前言中 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 后缀表达式 的常规做法）

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

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

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

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

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

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

    #include <iostream>
#include <stack>
using namespace std;
typedef long long ll;
void init(string &s) {
	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;
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) {
	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 = 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，但是这样会导致无法正确读入第二行的数 nn。考虑到 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();
	}
}

    又因为数据刁钻，左右括号可能不匹配，所以需要去除多余的右括号（多余的左括号不去除没有影响）。
    代码：

    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 += '@';
}

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

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

    至此，本题终于 AC 了。

    代码

    #include <iostream>
#include <stack>
using namespace std;
typedef long long ll;
ll mod = 1e9 + 7;
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;
ll pow(ll a, ll b) {
	ll p = 1;
	for (int i = 1; i <= b; i++) {
		p = (p * a) % mod;
	}
	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) + mod) % mod); break;
		case '-' : ans.push(((n1 - n2) + mod) % mod); break;
		case '*' : ans.push(((n1 * n2) + mod) % mod); break;
		case '^' : ans.push((((ll)pow(n1, n2)) + mod) % mod); break;
	}
}
ll calc(string s) {
	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 = 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() % mod;
}
int main() {
	string s;
	int n;
	char c = getchar();
	while (c != '\n' && c != '\r') {
		if (c != ' ') {
			s += c;
		}
		c = getchar();
	}
	ll p = calc(s);
	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 (calc(s) == p) {
			cout << char('A' + i - 1);
		}
	}
	return 0;
}
    • 1

    [NOIP 2005 提高组] 等价表达式

    信息

    ID
    56
    时间
    1000ms
    内存
    125MiB
    难度
    5
    标签
    递交数
    1
    已通过
    1
    上传者
    1. 关于
    2. 联系我们
    3. 隐私
    4. 服务条款
    5. Language
    6. 主题
    3. Worker 0, 24ms