P1928-外星密码[递归过程的剖析]

递归的思路和解法

设 $S=a[numb]=a+num?b$

其中:

$S$ 为最终答案 ,也为$read()$ 函数的返回值

$a[numb]$ 为题目字符串的格式

$a$ 表示纯字符串

$b$为 $b=S^{\prime }=a^{\prime }[nu{m}^{\prime }{b}^{\prime }]$ 下一层$read()$ 函数

综合起来看
$$\begin{gathered} S=a[numb]=a+num?b \\ b=S^{\prime }=a^{\prime }[nu{m}^{\prime }{b}^{\prime }] \end{gathered}$$

往后推

递归的精髓就在与栈:

递的过程就相当于在建一个栈;

? $S$ 为$read()$ 函数的返回值,而一旦经过 $b$ 就进入$read()$ 函数 递归往上面建栈

归 的过程就相当于在压栈,从上往后一直压倒最下面,当最上面那一个函数有返回值时它会逐渐一层一层的往下压
$$\begin{array}{ccccc}& & & & ?\\ & & & b^{\prime }& =S^{\prime \prime }=a^{\prime \prime }[nu{m}^{\prime \prime }{b}^{\prime \prime }]\\ & & & ?& \\ & b& =S^{\prime }=a^{\prime }[nu{m}^{\prime }& b^{\prime }& ]=a^{\prime }+nu{m}^{\prime }?b^{\prime }\\ & ?& & & \\ S=a[num& b& ]=a+num?b& & \end{array}$$

很多人对递归时产生的变量有点区分不清,所以我用 ’ 来做区别,它们时不同的变量,每个变量都是在函数内部定义,都为局部变量所以是不同的,而把他们连接起来的桥梁就是$b$

#include<iostream>
#include<string>
using namespace std;
string read(){
	int num;
	string s, b;
	char a;
	while (cin >> a){
		if (a == '['){
			cin >> num;//读入数字;
			b = read();          //从这里开始断(建栈),read()函数完成前后面的句子都不会执行
			while (num--) s += b;//num个read()的返回值b
		}
		else if (a == ']'){
			return s;      //此为递归的返回值,但是并非这一层的返回值,在后面的某层栈上,会返回,要分清,每一层的s 都不是同一个s
		}
		else{
			s += a;
		}
	}
	return s;//这句话,按理来说是不用加的,在洛谷上交题如果开启O2优化就必须要加上这句话,否则会出现全RE 的情况
}
int main(){
	cout << read();
	return 0;
}

递归但是不用while(cin>>a)

用while(cin>>a),自己往往不好调试,在最后总是要自己输入^$ Z $ 才可以结束

但是我们可以提前用一个字符串先把输入值存起来,(不过这种方法有很多的细节要注意)

#include<iostream>
#include<string>
using namespace std;
string m;
int p = 0;
string read() {
	string s;
	string b;
	char a;
	while (p<m.length()) {
		a = m[p++];//字符串挨个历遍
		if (a == '[') {
            
			int num=0;
			while (m[p] <= '9' && m[p] >= '0') {  //由于是字符串要注意数字的读入
				num += (m[p++] - '0');
				num *= 10;
			}
			num /= 10;
            
			b = read();
			while (num--) {
				s += b;
			}
		}
		else if (a == ']') {
			return s;
		}
		else {
			s += a;
		}
	}
	return s;
}
int main() {
	cin >> m;
	cout << read();
	return 0;
}

模拟栈来做

想法:既然递归的核心就是栈那么能不能直接用栈?当然是可以的,不过这样要处理的细节就特别的多

用栈的话就是纯模拟,

#include<iostream>
#include<string>
#include<cstring>
using namespace std;
const long long N = 2e5 + 9;
char s[N];
int num[N];//用来记录num的栈
int main()
{
	memset(num, 0, sizeof(num));
	char c;
	string m;
	cin >> m;
	int top1 = 0;//栈顶
	int top2 = 0;
	for (int i = 0; i < m.length(); i++) {
		if (m[i] == '[') {
			s[++top1] = m[i];//把'['也存入是为了方便找到起始位置,后面在丢掉就好
			i++;top2++;
			num[top2] = 0;//记得归0，当--，然后又++回来后，num[top2],是不会自动归0的
			while (m[i] <= '9' && m[i] >= '0') {
				num[top2] += (m[i ] - '0');
				num[top2] *= 10;
				i++;
			}
             num[top2] /= 10;//最后会多乘一个10;除去
			i--; //在for循环中,for循环还会i++;所以要减去一个
			
		}
		else if (m[i] == ']') {
			string s1;
			while (s[top1] != '[') {
				s1 += s[top1--];
			}
			top1--;//去除'['
            
			for (int k = 0; k < num[top2]; k++) {
				for (int j = s1.length()-1; j >= 0; j--) {
					s[++top1] = s1[j];//把字符串倍增后又存入栈中
				}
			}
			top2--;//用掉一个num
		}
		else {
			s[++top1] = m[i];//往栈s中加入字母
		}
	}

	for (int i = 1; i <= top1; i++) {//这就是没直接用栈的原因,用栈的话最后不好输出
		cout << s[i];
	}

	return 0;
}

---

欢迎大家提出见解.