字符串展开-HDU 1274

Problem Description

常用纱线的品种一般不会超过25种，分别可以用小写字母表示不同的纱线，例如：abc表示三根纱线的排列；重复可以用数字和括号表示，例如：2(abc)表示abcabc；1(a)=1a表示a;2ab表示aab;如果括号前面没有表示重复的数字出现，则就可认为是1被省略了，如：cd(abc)=cd1(abc)=cdabc;这种表示方法非常简单紧凑，也易于理解；但是计算机却不能理解。为了使计算机接受，就必须将简单紧凑的表达方式展开。某ACM队接受了此项任务。现在你就是该ACM队的一员，请你把这个程序编写完成。

已知条件：输入的简单紧凑表达方式的长度不超过250个字符；括号前表示重复的数不超过1000；不会出现除了数字、括号、小写字母以外的任何其他字符；不会出现括号不配对等错误的情况。

Input

本题有多个测试数据组，第一行输入的就是数据组数N，接着就是N行表达式，表达式是按照前面介绍的意义书写的。

Output

输出时含有N行，每行对应一个输入的表达式。

Sample Input

2

1(1a2b1(ab)1c)

3(ab2(4ab))

Sample Output

abbabc

abaaaabaaaababaaaabaaaababaaaabaaaab

关于递归：

递归是比较难于理解的，但又是一种重要的思想。如果一个问题可以转化成一个结构相同，规模更小的问题，则可以通过递归来解决。

递归是一种分析方法，可以帮助我们看清楚事物的本质。

如果确定了用递归法解题，思考的重点应该放到建立原问题和子问题之间的联系上面。

本题中对于左括号的出现就是递归方法运用的契机。而右括号出现后需要将当前位置返回给父函数则是父子函数间的纽带。

解题思路：

数据量并不大，我们只需模拟即可，分两种策略

step1: 如果是数字， 代表需要循环输出， 此时又分两种策略

1：如果后面是“（”， 则需要循环一个字符串， 即递归即可

2：如果后面是单个字母， 只需把后面的一个字母循环输出多次即可

step2：如果是字母， 直接输出

也就是说我们写的函数就是要输出后面字符串需要的次数，如果碰到了数字， 我们循环几次这个函数即可， 这就需要我们知道从哪个地方开始输出， 而且这个函数结束之后我们要知道已经进行到哪里了。因为后面的循环了之后，不需要再找了， 已经循环输出了。

本题解法的目标除了完成功能，还要求只允许一次字符串指针遍历，不使用strlen和strcpy之类的字符串函数，不使用额外数组，性能极优。

请看源码仔细体会。

源代码：G++ 0ms