题解 [email protected]洛谷 【表达式的转换】

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

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

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


思路:

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

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

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

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 个字符(本地统计),可以算是一个中模拟。

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

完结撒花!