点击蓝字关注赵码匠

洛谷题单链接https://www.luogu.com.cn/training/109#problems（复制到浏览器打开）

外星密码

题目描述

算法解析

首先明确输入的字符只有数字、大写字母、"["和"]"，因此直接对4种字符进行判断即可。遇到 "["说明与匹配的"]"中间字符串需要解压缩。

这里有三种解决的思路：

1、利用字符串函数模拟

根据题意，我们需要首先找到最内侧的一对括号，对里面的字符串进行解压。

为了找到最后一个左括号"["，需要从后往前遍历字符串：

再从left开始向右寻找，一定能找到与之匹配的右括号：

接下来取出两个括号的中间部分，并进行解压。取出中间部分可以使用substr函数：

对其进行处理后，再将从左括号到右括号的所有字符替换掉，需要用到字符串的replace函数：

最后就需要实现fun()函数的功能：解压缩子字符串，并返回解压后的字符串。

在fun()函数中，可以使用isdigit()找出子串中的数字cnt，isalpha()找出子串中的字符串。

判断出来后，将子串中的字母组成的字符串循环cnt遍，返回该结果即可。具体的fun()函数如下：

完整的代码，还请读者们理解思路后自行编写，这里赵码匠就不展示了。

2、使用栈进行模拟

由于程序运行与括号有关，想到可以使用栈结构来存储数据。

在读入整个字符串后，一个一个字符进行判断，遇到"["和大写字母，全都压入栈，当遇到"]"时进行字符串处理：

（1）先弹出前几位字母，还原成原本的子串X;

（2）再弹出前几位数字，还原成原本的正数D;

（3）注意多弹出一个"["；

（4）为了类型统一，解压后需要将字符串一个一个字符压入栈；

这里要特别注意，出栈顺序与原顺序相比是倒序的，在拼接字符串和数字时要注意转换。

由于题目中限定解压后的字符串长度不超过20000，因此可以采用栈来存放。如果长度过长，这个方法会导致栈溢出。

代码展示：

（3）使用递归思想

考虑到最终结果是纯大写字母的字符串，不妨分析一下字母会出现在哪："[]"的外面和里面，其中，在"[]"里面的字符串，又分为外面的字符串和内部"[]"中的字符串。

因此我们可以将问题分解成各个子任务："[]"外部的字符串原样组合，"[]"内部的字符串进行解压。递推公式可以表示为：

f("A[DX]")="A"+"D*f("X")（其中，A为[]外字符串，D为正数，X为内部压缩的字符串）

边界条件为：f(A)=A，即没有括号的话，就原样输出。

在代码实现时，可以充分利用cin的特点，一边输入一边递归，最终递归函数的返回值就是答案。

代码展示：

运行结果

【 原创声明 】原创文章制作不易欢迎大家分享到微信群、朋友圈等社交圈如需转载，可后台留言开通白名单注：未经允许不得私自搬运到其他平台如果觉得写的不错的话还请帮忙点赞、在看、关注谢谢!

点分享点收藏点在看点点赞