算法8——字符串展开

PD:

用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：如果是字母， 直接输出

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

annotation:

   本文转载自微信公众号《ACM算法日常》，原文链接：https://mp.weixin.qq.com/s/26zMPoG5dMAkfsSilu6U3g

源代码：C++  0ms

#include <stdio.h>

//便于可读性写成函数，实际比赛使用宏
//是否是数字
int is_digit(char c) {
    return c >= '0' && c <= '9';
}

//是否是字母
int is_alpha(char c)
{
    return c >= 'a' && c <= 'z';
}

//解析字符串
//注意返回值是解析完成后字符串的位置
/*
思路：
1、一次遍历解决问题，仅使用自增操作进行遍历
2、做题前先思考如何规划问题的情况
本题中，对于字符串：1(1a2b1(ab)1c(ab))
我们先将数字抽象为符号D，字母抽象为符号s，那么指针在移动的时候会遇到4中情况，
分别是：
D(
s
Ds
s(
*/
char * parse(char * s)
{
    char * p = s;

    //特殊情况处理
    if (*p == 0 || *p == ')') {
        return p;
    }

    //每次前进一个位置
    for (p = s; *p; p++) {
        if (*p == ')') {
            return p;
        }
        //情况1、s
        if (is_alpha(*p)) {
            printf("%c", *p);
            continue;
        }

        int D = 0;
        while (is_digit(*p)) {
            D = D * 10 + (*p - '0');
            p++;
        }
        //情况4、s(
        D = D ? D : 1;

        if (*p == '(') {
            //情况2 D(
            char * n = 0;
            //输出n次
            for (int i = 0; i < D; ++i) {
                n = parse(p + 1);
            }
            //记得返回最后的位置
            p = n;
        } else {
            //情况3 Ds
            for (int i = 0; i < D; ++i) {
                printf("%c", *p);
            }
        }
    }
}

int main()
{
    int n = 0;
    char s[251];
    scanf("%d", &n);

    while (n--) {
        scanf("%s", s);
        parse(s);
        printf("\n");
    }

    return 0;
}