自动搬运

查看原文

来自洛谷，原作者为

	sunyizhe 这家伙是个热衷于研究PVZ/Minecraft的蒟蒻，什么有用的都没留下

搬运于2025-08-24 21:22:05，当前版本为作者最后更新于2022-08-27 17:18:40，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

这题难度并不是很大，就是模拟，只是代码很长而已。只要思路明确，就可通过此题。

题目传送门

一、题意

1. 写出给定字符串的后缀表达式。

2. 写出计算过程。

二、数据范围

• 字符只有 0123456789+-\*/^ 几种。

• 基本数字只有一位数，不会出现多位数。

• 输入数字不会出现负数，中间一切结果为整数。

• 字符串长度小于 $100$。

三、思路

3.1 第一问

3.1.1 认识后缀表达式的转换方法

首先，我们要知道如何手算得出后缀表达式。下面是题目样例的后缀表达式转换方法。

8 - (3 + 2 * 6) / 5 + 4
8 - (3 + 2 6 *) / 5 + 4
8 - 3 2 6 * + / 5 + 4 （去括号）
8 - 3 2 6 * + 5 / + 4 
8 3 2 6 * + 5 / - + 4
8 3 2 6 * + 5 / - 4 +

那么如何用编程来实现呢？

3.1.2 程序基本实现

用字符串 $s$ 存储中缀表达式。

我们定义一个函数来判断运算符的优先级。如下：

int check(char c)
{
	switch(c)
	{
		case '+':return 1;
		case '-':return 1;
		case '*':return 2;
		case '/':return 2;
		case '^':return 3;
		case '(':return 0;
		case ')':return 0;
		default:return -1;//程序不会执行这句，保险起见要加上
	}
}

定义两个栈 $dat$ 和 $op$，它们存的分别是后缀表达式和符号。

来看例子：2 + 3 * 4

模拟一下：

栈dat	栈op	操作
2	Null	将 2 入栈
	+	op 栈为空，将 + 入栈
3 2		将 3 入栈
	* +	* 比 + 优先级高，入栈
4 3 2	* +	将 4 入栈
+ * 4 3 2	Null	弹空 op 栈，依次进入 dat 栈

这时，逆序输出栈 $dat$，得到式子的后缀表达式 2 3 4 * +。

再看一个：2 * 4 + 3

栈dat	栈op	操作
2	Null	将 2 入栈
	*	op 栈为空，将 * 入栈
4 2		将 4 入栈
* 4 2	+	+ 比 * 优先级低，将 * 弹出
3 * 4 2	* +	将 3 入栈
+ 3 * 4 2	Null	弹空 op 栈，依次进入 dat 栈

这时，逆序输出栈 $dat$，得到式子的后缀表达式 2 4 * 3 +。

经过尝试和拼凑，我们发现：

• $s_i$ 为数字时，直接压进 $dat$ 栈。

• $s_i$ 为运算符时，优先级若比 $op$ 栈栈顶符号高（是 $>$ 而不是 $\ge$，可以自己模拟看看），就压进栈，否则就弹出 $op$ 的栈顶元素到 $dat$ 栈里，直到比栈顶符号优先级高或栈空。

• 最后，将 $op$ 栈里的剩余元素弹出到 $dat$ 栈。

上面这些是最基本的情况。但如果有括号呢？

3.1.3 特殊情况

当 $s_i$ 为左括号时，可以直接压进 $op$ 栈里。当 $s_i$ 为右括号时，一直弹出 $op$ 栈栈顶到 $dat$ 里，直到栈顶为左括号，再弹出左括号。这些也可以通过模拟得出答案。

看例子：2 + (3 + 4) * 3

栈 dat	栈 op	操作
2	Null	将 2 压进栈
	+	op 栈空，将 + 压进栈
	( +	将左括号压进栈
3 2		将 3 压进栈
	+ ( +	+ 比 ( 优先级高，将 + 压进栈
4 3 2		将 4 压进栈
+ 4 3 2	+	将右括号与左括号之间的 + 弹出到 dat 栈
	* +	* 比 + 优先级高，将 * 压进栈
3 + 4 3 2		将 3 压进栈
+ * 3 + 4 3 2	Null	将 op 栈里的元素压进 dat 栈

最后逆序输出 $dat$ 栈，得到：2 3 4 + 3 * +。

当然，我们不能忽略题目中特殊的乘方运算。模拟样例 2：2 ^ 2 ^ 3。如下：

栈 dat	栈 op	操作
2	Null	将 2 压进栈
	^	op 栈空，将 ^ 压进栈
2 2		将 3 压进栈
	^ ^	^ 与 ^相同，将 ^ 压进栈（特殊）
3 2 2		将 3 压进栈
^ ^ 3 2 2	Null	将 op 栈里的元素压进 dat 栈

我们得到：2 2 3 ^ ^

所以，当 $s_i$ 为乘方运算符时且 $op$ 栈栈顶也是乘方运算符时，也可直接压进栈中。

3.1.4 表达式输出

如果你用的是数组版栈，直接遍历即可。但如果你跟我一样用的是 STL 版栈，可以把栈 $op$ 用来临时存放数据。先把 $dat$ 里的元素全部压进 $op$ 栈，再倒回来，同时输出字符即可。输出记得换行。这样，第一问就结束了。

3.2 第二问

第二问相对简单，我们同样可以定义 $calc$ 函数完成第二问。

3.2.1 基本运算

为了方便，定义函数用来计算两个数的计算结果。这个很简单，代码如下：

int js(int x,int y,char t)//x和y为计算的两个数，t为运算符
{
	switch(t)
	{
		case '+':return x+y;
		case '-':return x-y;
		case '*':return x*y;
		case '/':return x/y;
		case '^':return pow(x,y);
		default:return -0x3f3f3f3f;//程序不会执行到这里，同样为了保险
	}
}

3.2.2 后缀表达式计算

定义两个栈 $num$ 与 $dat2$，$num$ 存储计算过程，$dat2$ 用来临时存放数据，之前的 $dat$ 和 $op$ 可以继续使用。

把 $dat$ 全部弹出到 $op$ 里，接下来进行计算。

1. 变量 $t$ 获取 $op$ 栈顶，$op$ 弹出。

2. 若 $t$ 为数字，减去 '0' 再进入 $num$。若 $t$ 为运算符，弹出 $num$ 栈顶 $2$ 个元素并记录，将运算结果压进栈，同时输出过程。

3. 重复 1 和 2 两个步骤，直到 $op$ 为空。

3.2.3 过程输出

输出过程时，反序输出 $num$，正序输出 $op$。

同样利用 $dat2$ 与 $dat$，反序与正序差不多，只是前者在倒回来时输出，后者在倒出去时输出。最后记得换行。

四、代码

#include <bits/stdc++.h>
using namespace std;
stack<char> dat,op;
stack<int> num,dat2;
int check(char c)
{
	switch(c)
	{
		case '+':return 1;
		case '-':return 1;
		case '*':return 2;
		case '/':return 2;
		case '^':return 3;
		case '(':return 0;
		case ')':return 0;
		default:return -1;
	}
}
int js(int x,int y,char t)
{
	switch(t)
	{
		case '+':return x+y;
		case '-':return x-y;
		case '*':return x*y;
		case '/':return x/y;
		case '^':return pow(x,y);
		default:return -0x3f3f3f3f;
	}
}
void change(string s)
{
	int len=s.size();
	for(int i=0;i<len;i++)
	{
		if(isdigit(s[i]))dat.push(s[i]);
		else if(s[i]=='(')op.push(s[i]);
		else if(s[i]==')')
		{
			char t=op.top();
			while(t!='(')
			{
				op.pop();
				dat.push(t);
				t=op.top();
			}
			op.pop();//要弹出左括号
		}
		else if(check(s[i])>=1&&check(s[i])<=3)//为运算符
		{
			if(!op.empty())
			{
				char t=op.top();
				while(!op.empty()&&check(s[i])<=check(t))
				{
					if(check(s[i])==check(t)&&s[i]=='^')break;//在s[i]与栈顶都是^号时也能进栈
					op.pop();
					dat.push(t);
					if(!op.empty())t=op.top();
				}
			}
			op.push(s[i]);
		}
	}
	while(!op.empty())
	{
		char t=op.top();
		op.pop();
		dat.push(t);
	}
	while(!dat.empty())
	{
		char t=dat.top();
		dat.pop();
		op.push(t);
	}
	while(!op.empty())
	{
		char t=op.top();
		cout<<t<<' ';
		op.pop();
		dat.push(t);
	}
	cout<<endl;
}
void calc()
{
	while(!dat.empty())
	{
		char t=dat.top();
		dat.pop();
		op.push(t);
	}
	while(!op.empty())
	{
		char t=op.top();
		op.pop();
		if(isdigit(t))num.push(t-'0');
		else
		{
			int x=num.top();
			num.pop();
			int y=num.top();
			num.pop();
			num.push(js(y,x,t));//传参数时要把x和y反过来
			while(!num.empty())
			{
				int t=num.top();
				num.pop();
				dat2.push(t); 
			}
			while(!dat2.empty())
			{
				int t=dat2.top();
				cout<<t<<' ';
				dat2.pop();
				num.push(t);
			}
			while(!op.empty())
			{
				char t=op.top();
				cout<<t<<' ';
				op.pop();
				dat.push(t);
			}
			while(!dat.empty())
			{
				char t=dat.top();
				dat.pop();
				op.push(t);
			}
			cout<<endl;
		}
	}
}
int main()
{
	string s;
	cin>>s;   
	change(s);
	calc();
	return 0;
}

P.S. 表格不知道咋回事，为什么没有线啊……