首页 > 试题广场 >

解压字符串

[编程题]解压字符串
  • 热度指数：1180 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解
猿辅导APP需要下发一些宣传文本给学生，工程师们使用了一种字符压缩算法，为简单起见，假设被压缩的字符全部为大写字母序列，A,B,C,D....Z,压缩规则如下：
1.AAAB可以压缩为A3B (单字符压缩不加括号)
2.ABABA可以压缩为(AB)2A （多字符串压缩才加括号）

输入数据保证不会出现冗余括号，且表示重复的数字一定合法且大于1，即不会出现：
1.（A)2B   ------- （应为：A2B）
2.  ((AB))2C,-----(应为：（AB)2C  )
3. （A)B  ----- （应为：AB）
4.   A1B，（AB)1C，（应为 AB，ABC）

注意：数字可能出现多位数即A11B或者(AB)10C或者A02这种情况。
A11B = AAAAAAAAAAAB
(AB)10C = ABABABABABABABABABABC
A02 = AA

数据分布：
对于60%的数据，括号不会出现嵌套，即不会有 ((AB)2C)2这种结构。
对于80%的数据，括号最多只嵌套一层，即不会有 (((AB)2C)2D)99 这种结构。
对于100%的数据，括号可以嵌套任意层。

输入描述:
第一行是正整数C(C <= 100)，表示下面有C组数据。之后C行，每行为一组数据，每组数据为一个字符串。

每个字符串由A-Z,数字0-9和(,)组成表示一个压缩后的串，保证输入数据一定合法且字符串长度小于50。


输出描述:
输出C行，每行对应一个数据的输出结果，表示压缩前的字符串，保证每个字符串展开后的长度不超过10^6。
示例1

输入

5
A11B
(AA)2A
((A2B)2)2G
(YUANFUDAO)2JIAYOU
A2BC4D2

输出

AAAAAAAAAAAB
AAAAA
AABAABAABAABG
YUANFUDAOYUANFUDAOJIAYOU
AABCCCCDD
算法知识视频讲解
添加回答
Python
沙漠青鸟头像 沙漠青鸟
编程语言：python3
方法：对于每一个待处理字符串，从左到右扫描整个字符串，构造一个列表t作为栈。每遇到一个左括号将t扩充一个字符串元素用来保存括号内的元素；每遇到一个右括号先找到其后的完整数字转为int后用u来保存，并pop出栈t最后新加的字符串元素且将此元素乘以u加入到pop后的t的最后一个元素中；每遇到一个数字时，将整个数字完整的找到后再把t[-1][-1]乘以这个数字减1再并入t[-1]中；每遇到一个普通字母时，只需将其直接并入t[-1]。最后t[0]即是output。 

n=int(input())
st=[]
for i in range(n):
    st.append(input())
     
for s in st:
    t=['']
    j=0
    while j<len(s):
        if s[j]=='(':
            t.append('')
            j+=1
        elif s[j]==')':
            k=j+1
            j+=1
            while j<len(s) and ord(s[j])>=ord('0') and ord(s[j])<=ord('9'):
                j+=1
            u=int(s[k:j])
            v=t.pop()
            t[-1]+=v*u
        elif ord(s[j])>=ord('0') and ord(s[j])<=ord('9'):
            k=j
            j+=1
            while j<len(s) and ord(s[j])>=ord('0') and ord(s[j])<=ord('9'):
                j+=1
            u=int(s[k:j])
            t[-1]+=t[-1][-1]*(u-1)
        else:
            t[-1]+=s[j]
            j+=1
    print(t[0])


发表于 2020-04-02 20:17:31 回复(0)
提交观点

问题信息

C++工程师 iOS工程师 安卓工程师 运维工程师 前端工程师 算法工程师 测试工程师 PHP工程师 安全工程师 c#工程师 数据库工程师 猿辅导 2020 大数据开发工程师 Java工程师
上传者：小小
难度：
1条回答 5636浏览

热门推荐

通过挑战的用户

相关试题

解压字符串

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号