C++信奥之径，锻炼思维，扎实算法——递推与递归(4)
外星密码
题目描述
算法解析
首先明确输入的字符只有数字、大写字母、"["和"]"，因此直接对4种字符进行判断即可。遇到 "["说明与匹配的"]"中间字符串需要解压缩。
这里有三种解决的思路：
1、利用字符串函数模拟
根据题意，我们需要首先找到最内侧的一对括号，对里面的字符串进行解压。
为了找到最后一个左括号"["，需要从后往前遍历字符串：
for(int i=s.size()-1;i>=0;i--){
if(s[i]=="["){
left=i;
break;
}
}再从left开始向右寻找，一定能找到与之匹配的右括号：
for(int i=left+1;i<=s.size()-1;i++){
if(s[i]=="]"){
right=i;
break;
}
}接下来取出两个括号的中间部分，并进行解压。取出中间部分可以使用substr函数：
string zistr = substr(s,left+1,right-left-1); //zistr是子字符串对其进行处理后，再将从左括号到右括号的所有字符替换掉，需要用到字符串的replace函数：
s.replace(left,right-left+1,fun(zistr));最后就需要实现fun()函数的功能：解压缩子字符串，并返回解压后的字符串。
在fun()函数中，可以使用isdigit()找出子串中的数字cnt，isalpha()找出子串中的字符串。其他的字符判断函数，读者们可以点击下方文章了解：
C++信奥之径，锻炼思维，扎实算法——模拟与高精度算法（8）
判断出来后，将子串中的字母组成的字符串循环cnt遍，返回该结果即可。具体的fun()函数如下：
string fun(string s){
int cnt=0,i=0;
while(isdigit(s[i])){
cnt=cnt*10+s[i]-'0';//将数字字符拼接成真正的数字
i++;
}
string x="",y="";
for( ;i<s.size();i++){
x+=s[i];
}
while(cnt--)y+=x;
return y;
}完整的代码，还请读者们理解思路后自行编写，这里就不展示了。
2、使用栈进行模拟
由于程序运行与括号有关，想到可以使用栈结构来存储数据。
在读入整个字符串后，一个一个字符进行判断，遇到"["和大写字母，全都压入栈，当遇到"]"时进行字符串处理：
（1）先弹出前几位字母，还原成原本的子串X;
（2）再弹出前几位数字，还原成原本的正数D;
（3）注意多弹出一个"["；
（4）为了类型统一，解压后需要将字符串一个一个字符压入栈；
这里要特别注意，出栈顺序与原顺序相比是倒序的，在拼接字符串和数字时要注意转换。
由于题目中限定解压后的字符串长度不超过20000，因此可以采用栈来存放。如果长度过长，这个方法会导致栈溢出。
代码展示：
#include<iostream>
#include<stack>
#include<string>
using namespace std;
stack<char> st;
string ans="",x=""; //x临时存放括号中的字符串
string d=""; //d临时存放压缩的数字
int main(){
string s;
cin>>s;
for(int i=0;i<s.size();i++){
if(s[i]==']'){
x=""; //x先清空
while(st.top()>='A'){
x=st.top()+x; //注意倒序的拼接
st.pop();
}
//cout<<x<<endl;
d=""; //临时数字先清空
while(st.top()!='['){
d=st.top()+d; //同样注意倒序
st.pop();
}
int n=stoi(d); //使用stoi()函数直接字符串转数字
//cout<<d<<endl;
st.pop(); //记得多弹出一个'['
for(int j=0;j<n;j++){
for(int k=0;k<x.size();k++){
st.push(x[k]); //要一个一个字符再压回去
}
}
}
else st.push(s[i]);
}
while(!st.empty()){ //最后栈里所有元素拼成答案
ans=st.top()+ans;
st.pop();
}
cout<<ans;
return 0;
}（3）使用递归思想
考虑到最终结果是纯大写字母的字符串，不妨分析一下字母会出现在哪："[]"的外面和里面，其中，在"[]"里面的字符串，又分为外面的字符串和内部"[]"中的字符串。
因此我们可以将问题分解成各个子任务："[]"外部的字符串原样组合，"[]"内部的字符串进行解压。递推公式可以表示为：
f("A[DX]")="A"+"D*f("X")（其中，A为[]外字符串，D为正数，X为内部压缩的字符串）
边界条件为：f(A)=A，即没有括号的话，就原样输出。
在代码实现时，可以充分利用cin的特点，一边输入一边递归，最终递归函数的返回值就是答案。
代码展示：
#include<iostream>
using namespace std;
string fun(){
int num;
char ch;
string s="",tmp="";
while(cin>>ch){
if(ch=='['){ //如果有 '['，准备递归
cin>>num; //利用cin的缓冲机制直接读入数字
tmp=fun(); //递归处理后续的字符串
while(num--){
s+=tmp; //解压：字符串复制num次
}
}
else if(ch==']'){ //到']'，解压完毕，返回[]中解压的结果
return s;
}
else{
s+=ch; //[]外面的字符，直接累加进答案
}
}
return s;
}
int main(){
string ans=fun();
cout<<ans<<endl;
return 0;
}运行结果
