字符串展开(递归)- 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

#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;
}

原文发布于微信公众号 - ACM算法日常(acm-clan)

原文发表时间:2018-01-13

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏人工智能LeadAI

为什么算法容易忘记之插入排序

在学习常用的排序算法时,常有这样的感觉,一看就懂,过眼就忘。原因在于没有将排序的基本思想与代码中各个循环控制变量的意义联系起来进行理解记忆。 插入排序 首先,我...

36250
来自专栏Python小屋

Python求解进制问题(阿里巴巴2015笔试题)

问题描述:用十进制计算30的阶乘,然后把结果转换成三进制表示,那么该进制表示的结果末尾会有多少个连续0? 解析:作为笔试题的话,要想按照题意先把阶乘结果计算出来...

40970
来自专栏小古哥的博客园

秒懂JS对象、构造器函数和原型对象之间的关系

学习JS的过程中,想要掌握面向对象的程序设计风格,对象模型(原型和继承)是其中的重点和难点,拜读了各类经典书籍和各位前辈的技术文章,感觉都太过高深,花费了不少时...

34070
来自专栏带你撸出一手好代码

深入理解final关键字

通常我们对Java中final关键字的理解是“用final修饰的变量是不可变的”,如果尝试对final变量多次赋值,编译器将报错。似乎final的作用就是保证变...

36350
来自专栏jeremy的技术点滴

排序算法python实现

40090
来自专栏强仔仔

Java基础知识-基本数据类型相互转型

这是我第一次系统性的总结java这门语言的基础知识用法,因本人经验有限,所以在总结的过程中如果有错误或者有歧义等等之类的问题,都可以联系我QQ:20801753...

20680
来自专栏java一日一条

JavaScript 函数式编程中的 curry 实现

最近在学习javascript函数式编程,对其中大名鼎鼎的curry十分感兴趣,curry函数可以接受一个函数,我们暂且称之为原始函数,返回的也是一个函数,柯里...

9340
来自专栏诸葛青云的专栏

C语言入门基础学习函数?来看我就告诉你!

在前面我们已经讲过了一些简单的函数,如程序的主函数main()、标准输出函数printf()。在C语言中,大多数功能都是依靠函数来实现的。But,你知道什么是函...

14830
来自专栏小詹同学

LeetCode 系列——双指针问题 。

关于 LeetCode 系列有段时间没有逐题更新了 ,还是想到一题一题的刷有些凌乱 。如前段时间的推文所说 ,准备系统的讲讲数据结构相关知识点 。

28620
来自专栏程序员互动联盟

【面试宝典】static 关键字

面试官:static关键字你了解吗?说一下你的认识。 小白:啊.....有点晕呀,这么宽泛的问题,我该从哪回答呢?头脑一片空白。让我想想...... 面试官:没...

37560

扫码关注云+社区

领取腾讯云代金券